Package com.google.common.geometry

Class 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.

    • Field Detail

      • cells

        private final java.util.List<S2ShapeIndex.Cell> cells
        Temporary list of cells that intersect the query edge AB. Used while processing a query.

      • EMPTY_EDGE_LIST

        private static final S2EdgeQuery.Edges EMPTY_EDGE_LIST
        An Edges implementation that contains no edges.

    • Method Detail

      • 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 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

        boolean getCells​(S2Point a,
                 R2Vector aVector,
                 S2Point b,
                 R2Vector bVector,
                 S2PaddedCell root,
                 java.util.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.