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 class
An 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 interface
An iterator over the sorted unique edge IDs of a shape that may intersect some query edge.private static final class
AnEdges
implementation optimized for merging edges from multiple S2ClippedShapes already in sorted order.static final class
AnEdges
that contains all the edges of a shape with the given number of edges.private static final class
AnEdges
implementation that includes all the edges of a clipped shape.private static final class
Tracks 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.Edges
AnEdges
implementation that contains no edges.private final S2ShapeIndex
private final S2Iterator
<S2ShapeIndex.Cell> The following vectors are temporary storage used while processing a query. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate 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.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 ofshape
that intersect AB.private void
getCells
(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) boolean
getCells
(S2Point a, R2Vector aVector, S2Point b, R2Vector bVector, S2PaddedCell root, List<S2ShapeIndex.Cell> cells) Adds all cells tocells
that might intersect the query edge froma
tob
and the cellroot
.private void
Sets cells to the set of index cells intersected by an edge AB.boolean
getCells
(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 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.private void
splitUBound
(R2Rect edgeBound, double u, R2Rect[] childBounds, R2Vector aVector, R2Vector bVector) Splits the current edge into two child edges atu
and returns the bound for each child.private void
splitVBound
(R2Rect edgeBound, double v, R2Rect[] childBounds, R2Vector aVector, R2Vector bVector) Splits the current edge into two child edges atv
and 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
AnEdges
implementation 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 ofshape
that intersect AB. Consider usingS2EdgeQuery.ShapeEdges
instead, 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.ShapeEdges
instead, 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 tocells
that might intersect the query edge froma
tob
and the cellroot
. TheaVector
andbVector
parameters 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.center
is 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 atu
and 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 atv
and 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.uEnd
andvEnd
indicate which bound endpoints of child 1 will be updated.
-