Class S2EdgeIndex
- Direct Known Subclasses:
S2Polygon.S2LoopSequenceIndex
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic class
An iterator on data edges that may cross a query edge (a,b). -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate long[]
The cell containing each edge, as given in the parallel arrayedges
.private int[]
The edge contained by each cell, as given in the parallel arraycells
.private boolean
Has the index been computed already?private int
No cell strictly below this level appears in mapping.private int
Number of queries so farprivate static final double
Thicken the edge in all directions by roughly 1% of the edge length when thickenEdge is true. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate int
binarySearch
(long cell, int edge) void
clipEdge
(S2Point a0, S2Point a1, boolean addSharedEdges, Collection<ParametrizedS2Point> intersections) Adds points where the edge index intersects the edge[a0, a1]
tointersections
.private static final int
compare
(long cell1, int edge1, long cell2, int edge2) Compares [cell1, edge1] to [cell2, edge2], by cell first and edge second.final void
Computes the index (if it has not been previously done).private static S2CellId
containingCell
(S2Point pa, S2Point pb) Returns the smallest cell containing both points, or Sentinel if they are not all on the same face.private static S2CellId
containingCell
(S2Point pa, S2Point pb, S2Point pc, S2Point pd) Returns the smallest cell containing all four points, orS2CellId.sentinel()
if they are not all on the same face.abstract S2Point
edgeFrom
(int index) Returns the starting vertex of the edge at offsetindex
.edgeFromTo
(int index) Return both vertices of the givenindex
in one call.private static boolean
edgeIntersectsCellBoundary
(S2Point a, S2Point b, S2Cell cell) Returns true if the edge and the cell (including boundary) intersect.abstract S2Point
edgeTo
(int index) Returns the ending vertex of the edge at offsetindex
.protected void
findCandidateCrossings
(S2Point a, S2Point b, List<Integer> candidateCrossings) Appends to "candidateCrossings" all edge references which may cross the given edge.private int
getCovering
(S2Point a, S2Point b, boolean thickenEdge, ArrayList<S2CellId> edgeCovering) Computes a cell covering of an edge.private int[]
getEdges
(long cell1, long cell2) Filters a list of entries down to the inclusive range defined by the given cells, inO(log N)
time.private void
getEdgesInChildrenCells
(S2Point a, S2Point b, List<S2CellId> cover, Set<Integer> candidateCrossings) Appends to candidateCrossings the edges that are fully contained in an S2 covering of edge.private void
getEdgesInParentCells
(List<S2CellId> cover, Set<Integer> candidateCrossings) Adds to candidateCrossings all the edges present in any ancestor of any cell of cover, down to minimumS2LevelUsed.abstract int
Returns the number of edges in this index.protected final void
Tell the index that we just received a new request for candidates.final boolean
final void
predictAdditionalCalls
(int n) If the index hasn't been computed yet, looks at how much work has gone into iterating using the brute force method, and how much more work is planned as defined by 'cost'.void
reset()
Empties the index in case it already contained something.private void
Sorts the parallelcells
andedges
arrays.
-
Field Details
-
THICKENING
private static final double THICKENINGThicken the edge in all directions by roughly 1% of the edge length when thickenEdge is true.- See Also:
-
cells
private long[] cellsThe cell containing each edge, as given in the parallel arrayedges
. -
edges
private int[] edgesThe edge contained by each cell, as given in the parallel arraycells
. -
minimumS2LevelUsed
private int minimumS2LevelUsedNo cell strictly below this level appears in mapping. Initially leaf level, that's the minimum level at which we will ever look for test edges. -
indexComputed
private boolean indexComputedHas the index been computed already? -
queryCount
private int queryCountNumber of queries so far
-
-
Constructor Details
-
S2EdgeIndex
public S2EdgeIndex()
-
-
Method Details
-
reset
public void reset()Empties the index in case it already contained something. -
compare
private static final int compare(long cell1, int edge1, long cell2, int edge2) Compares [cell1, edge1] to [cell2, edge2], by cell first and edge second.- Returns:
- -1 if [cell1, edge1] is less than [cell2, edge2], 1 if [cell1, edge1] is greater than [cell2, edge2], 0 otherwise.
-
computeIndex
public final void computeIndex()Computes the index (if it has not been previously done). -
sortIndex
private void sortIndex()Sorts the parallelcells
andedges
arrays. -
isIndexComputed
public final boolean isIndexComputed() -
incrementQueryCount
protected final void incrementQueryCount()Tell the index that we just received a new request for candidates. Useful to compute when to switch to quad tree. -
predictAdditionalCalls
public final void predictAdditionalCalls(int n) If the index hasn't been computed yet, looks at how much work has gone into iterating using the brute force method, and how much more work is planned as defined by 'cost'. If it were to have been cheaper to use a quad tree from the beginning, then compute it now. This guarantees that we will never use more than twice the time we would have used had we known in advance exactly how many edges we would have wanted to test. It is the theoretical best.The value 'n' is the number of iterators we expect to request from this edge index.
If we have m data edges and n query edges, then the brute force cost is m * n * testCost where testCost is taken to be the cost of EdgeCrosser.robustCrossing, measured to be about 30ns at the time of this writing.
If we compute the index, the cost becomes: m * costInsert + n * costFind(m)
- costInsert can be expected to be reasonably stable, and was measured at 1200ns with the BM_QuadEdgeInsertionCost benchmark.
- costFind depends on the length of the edge . For m=1000 edges, we got timings ranging from 1ms (edge the length of the polygon) to 40ms. The latter is for very long query edges, and needs to be optimized. We will assume for the rest of the discussion that costFind is roughly 3ms.
When doing one additional query, the differential cost is m * testCost - costFind(m) With the numbers above, it is better to use the quad tree (if we have it) if m >= 100.
If m = 100, 30 queries will give m*n*testCost = m * costInsert = 100ms, while the marginal cost to find is 3ms. Thus, this is a reasonable thing to do.
-
getNumEdges
public abstract int getNumEdges()Returns the number of edges in this index. -
edgeFrom
Returns the starting vertex of the edge at offsetindex
. -
edgeTo
Returns the ending vertex of the edge at offsetindex
. -
edgeFromTo
Return both vertices of the givenindex
in one call. Can be overridden by some subclasses to more efficiently retrieve both edge points at once, which makes a difference in performance, especially for small loops. -
findCandidateCrossings
Appends to "candidateCrossings" all edge references which may cross the given edge. This is done by covering the edge and then finding all references of edges whose coverings overlap this covering. Parent cells are checked level by level. Child cells are checked all at once by taking advantage of the natural ordering of S2CellIds. -
containingCell
Returns the smallest cell containing all four points, orS2CellId.sentinel()
if they are not all on the same face. The points don't need to be normalized. -
containingCell
Returns the smallest cell containing both points, or Sentinel if they are not all on the same face. The points don't need to be normalized. -
getCovering
private int getCovering(S2Point a, S2Point b, boolean thickenEdge, ArrayList<S2CellId> edgeCovering) Computes a cell covering of an edge. Clears edgeCovering and returns the level of the s2 cells used in the covering (only one level is ever used for each call).If thickenEdge is true, the edge is thickened and extended by 1% of its length.
It is guaranteed that no child of a covering cell will fully contain the covered edge.
-
getEdges
private int[] getEdges(long cell1, long cell2) Filters a list of entries down to the inclusive range defined by the given cells, inO(log N)
time.- Parameters:
cell1
- One side of the inclusive query range.cell2
- The other side of the inclusive query range.- Returns:
- An array of length 2, containing the start/end indices.
-
binarySearch
private int binarySearch(long cell, int edge) -
getEdgesInParentCells
Adds to candidateCrossings all the edges present in any ancestor of any cell of cover, down to minimumS2LevelUsed. The cell->edge map is in the variable mapping. -
edgeIntersectsCellBoundary
Returns true if the edge and the cell (including boundary) intersect. -
getEdgesInChildrenCells
private void getEdgesInChildrenCells(S2Point a, S2Point b, List<S2CellId> cover, Set<Integer> candidateCrossings) Appends to candidateCrossings the edges that are fully contained in an S2 covering of edge. The covering of edge used is initially cover, but is refined to eliminate quickly subcells that contain many edges but do not intersect with edge. -
clipEdge
public void clipEdge(S2Point a0, S2Point a1, boolean addSharedEdges, Collection<ParametrizedS2Point> intersections) Adds points where the edge index intersects the edge[a0, a1]
tointersections
. Each intersection is paired with at
-value indicating the fractional geodesic rotation of the intersection from 0 (ata0
) to 1 (ata1
).- Parameters:
a0
- First vertex of the edge to clip.a1
- Second vertex of the edge to clip.addSharedEdges
- Whether an exact duplicate of[a0, a1]
in the index should count as an intersection or not.intersections
- The resulting list of intersections.
-