Class S2EdgeQuery

java.lang.Object
com.google.common.geometry.S2EdgeQuery

@GwtCompatible public class S2EdgeQuery extends 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 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.

  • Field Details

    • index

      private final S2ShapeIndex index
    • cells

      private final 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
      An Edges implementation that contains no edges.
  • Constructor Details

  • Method Details

    • 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 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 shape shape, returns a superset of the edges of shape that intersect AB. Consider using S2EdgeQuery.ShapeEdges instead, if the shape has few enough edges.
    • getCandidates

      public 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 using S2EdgeQuery.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, List<S2ShapeIndex.Cell> cells)
    • getCells

      boolean getCells(S2Point a, R2Vector aVector, S2Point b, R2Vector bVector, S2PaddedCell root, List<S2ShapeIndex.Cell> cells)
      Adds all cells to cells that might intersect the query edge from a to b and the cell root. The aVector and bVector parameters are cached R2 versions of the [A, B] edge projected onto the same cube face as root.
    • getCells

      private void getCells(S2PaddedCell pCell, R2Rect edgeBound, R2Vector aVector, R2Vector bVector)
      Computes the index cells intersected by the current edge that are descendants of pCell, and adds them to cells.

      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 cell pCell, 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 of pCell.
    • splitUBound

      private void splitUBound(R2Rect edgeBound, double u, R2Rect[] childBounds, R2Vector aVector, R2Vector bVector)
      Splits the current edge into two child edges at u 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 at v 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 and vEnd indicate which bound endpoints of child 1 will be updated.