Package com.google.common.geometry
Class S2EdgeQuery
java.lang.Object
com.google.common.geometry.S2EdgeQuery
S2EdgeQuery is used to find edges or shapes that are crossed by an edge. If you need to query
many edges, it is more efficient to declare a single S2EdgeQuery object and reuse it so that
temporary storage does not need to be reallocated each time.
Here is an example showing how to index a set of polylines, and then find the polylines that are crossed by a given edge AB:
void test(Collectionpolylines, S2Point a0, S2Point a1) { S2ShapeIndex index = new S2ShapeIndex(); for (int i = 0; i invalid input: '<' polylines.size(); ++i) { index.add(polylines[i]); } S2EdgeQuery query = new S2EdgeQuery(index); Mapinvalid input: '<'S2Shape, Edges> results = query.getCrossings(a, b); for (Map.Entryinvalid input: '<'S2Shape, Edges> entry : results.entrySet()) { S2Polyline polyline = (S2Polyline) entry.getKey(); for (Edges edges = entry.getValue(); !edges.isEmpty(); ) { int edge = edges.getNext(); S2Point b0 = polyline.vertex(edge); S2Point b1 = polyline.vertex(edge + 1); // Guaranteed that each resulting edge is either a crossing or a degenerate crossing. assertTrue(S2EdgeUtil.robustCrossing(a0, a1, b0, b1) >= 0); } } }
Note that if you need to query many edges, it is more efficient to declare a single S2EdgeQuery object and reuse it so that temporary storage does not need to be reallocated each time.
This class is not thread-safe.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static final classAn Edges implementation that filters edges of a shape to those that intersect the edge AB or have an endpoint on either A or B.static interfaceAn iterator over the sorted unique edge IDs of a shape that may intersect some query edge.private static final classAnEdgesimplementation optimized for merging edges from multiple S2ClippedShapes already in sorted order.static final classAnEdgesthat contains all the edges of a shape with the given number of edges.private static final classAnEdgesimplementation that includes all the edges of a clipped shape.private static final classTracks the current edge index within a clipped shape. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final List<S2ShapeIndex.Cell> Temporary list of cells that intersect the query edge AB.private static final S2EdgeQuery.EdgesAnEdgesimplementation that contains no edges.private final S2ShapeIndexprivate final S2Iterator<S2ShapeIndex.Cell> The following vectors are temporary storage used while processing a query. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate voidclipVAxis(R2Rect edgeBound, double center, int i, S2PaddedCell pCell, R2Vector aVector, R2Vector bVector) Given either the left (i = 0) or right (i = 1) side of a padded cellpCell, determines whether the current edge intersects the lower child, upper child, or both children, and calls getCells() recursively on those children.getCandidates(S2Point a, S2Point b) Given a query edge AB, returns a map from the indexed shapes to a superset of the edges for each shape that intersect AB.getCandidates(S2Point a, S2Point b, S2Shape shape) Given a query edge AB and a shapeshape, returns a superset of the edges ofshapethat intersect AB.private voidgetCells(S2PaddedCell pCell, R2Rect edgeBound, R2Vector aVector, R2Vector bVector) Computes the index cells intersected by the current edge that are descendants ofpCell, and adds them tocells.(package private) booleangetCells(S2Point a, R2Vector aVector, S2Point b, R2Vector bVector, S2PaddedCell root, List<S2ShapeIndex.Cell> cells) Adds all cells tocellsthat might intersect the query edge fromatoband the cellroot.private voidSets cells to the set of index cells intersected by an edge AB.booleangetCells(S2Point a, S2Point b, S2PaddedCell root, List<S2ShapeIndex.Cell> cells) Convenience method for callinggetCells(S2Point, R2Vector, S2Point, R2Vector, S2PaddedCell, List).getCrossings(S2Point a, S2Point b) Returns edges for each shape that either crosses AB or shares a vertex with AB.getCrossings(S2Point a, S2Point b, S2Shape shape) Returns edges from a given shape that either cross AB or share a vertex with AB.private voidsplitBound(R2Rect edgeBound, int uEnd, double u, int vEnd, double v, R2Rect[] childBounds) Splits the current edge into two child edges at the given point (u, v) and returns the bound for each child.private voidsplitUBound(R2Rect edgeBound, double u, R2Rect[] childBounds, R2Vector aVector, R2Vector bVector) Splits the current edge into two child edges atuand returns the bound for each child.private voidsplitVBound(R2Rect edgeBound, double v, R2Rect[] childBounds, R2Vector aVector, R2Vector bVector) Splits the current edge into two child edges atvand returns the bound for each child.
-
Field Details
-
index
-
cells
Temporary list of cells that intersect the query edge AB. Used while processing a query. -
iter
The following vectors are temporary storage used while processing a query. -
EMPTY_EDGE_LIST
AnEdgesimplementation that contains no edges.
-
-
Constructor Details
-
S2EdgeQuery
Constructor from anS2ShapeIndex.
-
-
Method Details
-
getCrossings
Returns edges from a given shape that either cross AB or share a vertex with AB. -
getCrossings
Returns edges for each shape that either crosses AB or shares a vertex with AB. -
getCandidates
Given a query edge AB and a shapeshape, returns a superset of the edges ofshapethat intersect AB. Consider usingS2EdgeQuery.ShapeEdgesinstead, if the shape has few enough edges. -
getCandidates
Given a query edge AB, returns a map from the indexed shapes to a superset of the edges for each shape that intersect AB. Consider usingS2EdgeQuery.ShapeEdgesinstead, if there is just one indexed shape with few enough edges.CAVEAT: This method may return shapes that have an empty set of candidate edges, i.e.
result.get(shape).isEmpty() == true. -
getCells
Sets cells to the set of index cells intersected by an edge AB. -
getCells
Convenience method for callinggetCells(S2Point, R2Vector, S2Point, R2Vector, S2PaddedCell, List). -
getCells
boolean getCells(S2Point a, R2Vector aVector, S2Point b, R2Vector bVector, S2PaddedCell root, List<S2ShapeIndex.Cell> cells) Adds all cells tocellsthat might intersect the query edge fromatoband the cellroot. TheaVectorandbVectorparameters are cached R2 versions of the [A, B] edge projected onto the same cube face asroot. -
getCells
Computes the index cells intersected by the current edge that are descendants ofpCell, and adds them tocells.WARNING: This function is recursive with a maximum depth of 30.
-
clipVAxis
private void clipVAxis(R2Rect edgeBound, double center, int i, S2PaddedCell pCell, R2Vector aVector, R2Vector bVector) Given either the left (i = 0) or right (i = 1) side of a padded cellpCell, determines whether the current edge intersects the lower child, upper child, or both children, and calls getCells() recursively on those children.centeris the v-coordinate at the center ofpCell. -
splitUBound
private void splitUBound(R2Rect edgeBound, double u, R2Rect[] childBounds, R2Vector aVector, R2Vector bVector) Splits the current edge into two child edges atuand returns the bound for each child. -
splitVBound
private void splitVBound(R2Rect edgeBound, double v, R2Rect[] childBounds, R2Vector aVector, R2Vector bVector) Splits the current edge into two child edges atvand returns the bound for each child. -
splitBound
private void splitBound(R2Rect edgeBound, int uEnd, double u, int vEnd, double v, R2Rect[] childBounds) Splits the current edge into two child edges at the given point (u, v) and returns the bound for each child.uEndandvEndindicate which bound endpoints of child 1 will be updated.
-