Package com.google.common.geometry
Class S2EdgeQuery
- java.lang.Object
-
- com.google.common.geometry.S2EdgeQuery
-
@GwtCompatible public class S2EdgeQuery extends java.lang.Object
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(Collection
polylines, S2Point a0, S2Point a1) { S2ShapeIndex index = new S2ShapeIndex(); for (int i = 0; i < polylines.size(); ++i) { index.add(polylines[i]); } S2EdgeQuery query = new S2EdgeQuery(index); Map results = query.getCrossings(a, b); for (Map.Entry 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 Classes Modifier and Type Class Description private static class
S2EdgeQuery.CrossingFilter
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
S2EdgeQuery.Edges
An iterator over the sorted unique edge IDs of a shape that may intersect some query edge.private static class
S2EdgeQuery.MergedEdges
AnEdges
implementation optimized for merging edges from multiple S2ClippedShapes already in sorted order.static class
S2EdgeQuery.ShapeEdges
AnEdges
that contains all the edges of a shape with the given number of edges.private static class
S2EdgeQuery.SimpleEdges
AnEdges
implementation that includes all the edges of a clipped shape.private static class
S2EdgeQuery.Stepper
Tracks the current edge index within a clipped shape.
-
Field Summary
Fields Modifier and Type Field Description private java.util.List<S2ShapeIndex.Cell>
cells
Temporary list of cells that intersect the query edge AB.private static S2EdgeQuery.Edges
EMPTY_EDGE_LIST
AnEdges
implementation that contains no edges.private S2ShapeIndex
index
private S2Iterator<S2ShapeIndex.Cell>
iter
The following vectors are temporary storage used while processing a query.
-
Constructor Summary
Constructors Constructor Description S2EdgeQuery(S2ShapeIndex index)
Constructor from anS2ShapeIndex
.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description 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.java.util.Map<S2Shape,S2EdgeQuery.Edges>
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.S2EdgeQuery.Edges
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, java.util.List<S2ShapeIndex.Cell> cells)
Adds all cells tocells
that might intersect the query edge froma
tob
and the cellroot
.private void
getCells(S2Point a, S2Point b)
Sets cells to the set of index cells intersected by an edge AB.boolean
getCells(S2Point a, S2Point b, S2PaddedCell root, java.util.List<S2ShapeIndex.Cell> cells)
Convenience method for callinggetCells(S2Point, R2Vector, S2Point, R2Vector, S2PaddedCell, List)
.java.util.Map<S2Shape,S2EdgeQuery.Edges>
getCrossings(S2Point a, S2Point b)
Returns edges for each shape that either crosses AB or shares a vertex with AB.S2EdgeQuery.Edges
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 Detail
-
index
private final S2ShapeIndex index
-
cells
private final java.util.List<S2ShapeIndex.Cell> cells
Temporary list of cells that intersect the query edge AB. Used while processing a query.
-
iter
private final S2Iterator<S2ShapeIndex.Cell> iter
The following vectors are temporary storage used while processing a query.
-
EMPTY_EDGE_LIST
private static final S2EdgeQuery.Edges EMPTY_EDGE_LIST
AnEdges
implementation that contains no edges.
-
-
Constructor Detail
-
S2EdgeQuery
public S2EdgeQuery(S2ShapeIndex index)
Constructor from anS2ShapeIndex
.
-
-
Method Detail
-
getCrossings
public S2EdgeQuery.Edges getCrossings(S2Point a, S2Point b, S2Shape shape)
Returns edges from a given shape that either cross AB or share a vertex with AB.
-
getCrossings
public java.util.Map<S2Shape,S2EdgeQuery.Edges> getCrossings(S2Point a, S2Point b)
Returns edges for each shape that either crosses AB or shares a vertex with AB.
-
getCandidates
public S2EdgeQuery.Edges 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. Consider usingS2EdgeQuery.ShapeEdges
instead, if the shape has few enough edges.
-
getCandidates
public java.util.Map<S2Shape,S2EdgeQuery.Edges> 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. 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
private void getCells(S2Point a, S2Point b)
Sets cells to the set of index cells intersected by an edge AB.
-
getCells
public boolean getCells(S2Point a, S2Point b, S2PaddedCell root, java.util.List<S2ShapeIndex.Cell> cells)
Convenience method for callinggetCells(S2Point, R2Vector, S2Point, R2Vector, S2PaddedCell, List)
.
-
getCells
boolean getCells(S2Point a, R2Vector aVector, S2Point b, R2Vector bVector, S2PaddedCell root, java.util.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
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
.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.
-
-