Class S2EdgeIndex
- java.lang.Object
-
- com.google.common.geometry.S2EdgeIndex
-
- Direct Known Subclasses:
S2Polygon.S2LoopSequenceIndex
@GwtCompatible public abstract class S2EdgeIndex extends java.lang.Object
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
S2EdgeIndex.DataEdgeIterator
An iterator on data edges that may cross a query edge (a,b).
-
Field Summary
Fields Modifier and Type Field Description private long[]
cells
The cell containing each edge, as given in the parallel arrayedges
.private int[]
edges
The edge contained by each cell, as given in the parallel arraycells
.private boolean
indexComputed
Has the index been computed already?private int
minimumS2LevelUsed
No cell strictly below this level appears in mapping.private int
queryCount
Number of queries so farprivate static double
THICKENING
Thicken the edge in all directions by roughly 1% of the edge length when thickenEdge is true.
-
Constructor Summary
Constructors Constructor Description S2EdgeIndex()
-
Method Summary
All Methods Static Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description private int
binarySearch(long cell, int edge)
void
clipEdge(S2Point a0, S2Point a1, boolean addSharedEdges, java.util.Collection<ParametrizedS2Point> intersections)
Adds points where the edge index intersects the edge[a0, a1]
tointersections
.private static int
compare(long cell1, int edge1, long cell2, int edge2)
Compares [cell1, edge1] to [cell2, edge2], by cell first and edge second.void
computeIndex()
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
.S2Edge
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, java.util.List<java.lang.Integer> candidateCrossings)
Appends to "candidateCrossings" all edge references which may cross the given edge.private int
getCovering(S2Point a, S2Point b, boolean thickenEdge, java.util.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, java.util.List<S2CellId> cover, java.util.Set<java.lang.Integer> candidateCrossings)
Appends to candidateCrossings the edges that are fully contained in an S2 covering of edge.private void
getEdgesInParentCells(java.util.List<S2CellId> cover, java.util.Set<java.lang.Integer> candidateCrossings)
Adds to candidateCrossings all the edges present in any ancestor of any cell of cover, down to minimumS2LevelUsed.abstract int
getNumEdges()
Returns the number of edges in this index.protected void
incrementQueryCount()
Tell the index that we just received a new request for candidates.boolean
isIndexComputed()
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
sortIndex()
Sorts the parallelcells
andedges
arrays.
-
-
-
Field Detail
-
THICKENING
private static final double THICKENING
Thicken the edge in all directions by roughly 1% of the edge length when thickenEdge is true.- See Also:
- Constant Field Values
-
cells
private long[] cells
The cell containing each edge, as given in the parallel arrayedges
.
-
edges
private int[] edges
The edge contained by each cell, as given in the parallel arraycells
.
-
minimumS2LevelUsed
private int minimumS2LevelUsed
No 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 indexComputed
Has the index been computed already?
-
queryCount
private int queryCount
Number of queries so far
-
-
Method Detail
-
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
public abstract S2Point edgeFrom(int index)
Returns the starting vertex of the edge at offsetindex
.
-
edgeTo
public abstract S2Point edgeTo(int index)
Returns the ending vertex of the edge at offsetindex
.
-
edgeFromTo
public S2Edge edgeFromTo(int index)
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
protected void findCandidateCrossings(S2Point a, S2Point b, java.util.List<java.lang.Integer> candidateCrossings)
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
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. The points don't need to be normalized.
-
containingCell
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. The points don't need to be normalized.
-
getCovering
private int getCovering(S2Point a, S2Point b, boolean thickenEdge, java.util.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
private void getEdgesInParentCells(java.util.List<S2CellId> cover, java.util.Set<java.lang.Integer> candidateCrossings)
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
private static boolean edgeIntersectsCellBoundary(S2Point a, S2Point b, S2Cell cell)
Returns true if the edge and the cell (including boundary) intersect.
-
getEdgesInChildrenCells
private void getEdgesInChildrenCells(S2Point a, S2Point b, java.util.List<S2CellId> cover, java.util.Set<java.lang.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, java.util.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.
-
-