Class S2EdgeIndex

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      static class  S2EdgeIndex.DataEdgeIterator
      An iterator on data edges that may cross a query edge (a,b).
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private long[] cells
      The cell containing each edge, as given in the parallel array edges.
      private int[] edges
      The edge contained by each cell, as given in the parallel array cells.
      private boolean indexComputed
      Has the index been computed already?
      private int minimumS2LevelUsed
      No cell strictly below this level appears in mapping.
      private int queryCount
      Number of queries so far
      private static double THICKENING
      Thicken the edge in all directions by roughly 1% of the edge length when thickenEdge is true.
    • Constructor Summary

      Constructors 
      Constructor Description
      S2EdgeIndex()  
    • Method Summary

      All Methods Static Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      private int binarySearch​(long cell, int edge)  
      void clipEdge​(S2Point a0, S2Point a1, boolean addSharedEdges, java.util.Collection<ParametrizedS2Point> intersections)
      Adds points where the edge index intersects the edge [a0, a1] to intersections.
      private static int compare​(long cell1, int edge1, long cell2, int edge2)
      Compares [cell1, edge1] to [cell2, edge2], by cell first and edge second.
      void computeIndex()
      Computes the index (if it has not been previously done).
      private static S2CellId containingCell​(S2Point pa, S2Point pb)
      Returns the smallest cell containing both points, or Sentinel if they are not all on the same face.
      private static S2CellId containingCell​(S2Point pa, S2Point pb, S2Point pc, S2Point pd)
      Returns the smallest cell containing all four points, or S2CellId.sentinel() if they are not all on the same face.
      abstract S2Point edgeFrom​(int index)
      Returns the starting vertex of the edge at offset index.
      S2Edge edgeFromTo​(int index)
      Return both vertices of the given index in one call.
      private static boolean edgeIntersectsCellBoundary​(S2Point a, S2Point b, S2Cell cell)
      Returns true if the edge and the cell (including boundary) intersect.
      abstract S2Point edgeTo​(int index)
      Returns the ending vertex of the edge at offset index.
      protected void findCandidateCrossings​(S2Point a, S2Point b, java.util.List<java.lang.Integer> candidateCrossings)
      Appends to "candidateCrossings" all edge references which may cross the given edge.
      private int getCovering​(S2Point a, S2Point b, boolean thickenEdge, java.util.ArrayList<S2CellId> edgeCovering)
      Computes a cell covering of an edge.
      private int[] getEdges​(long cell1, long cell2)
      Filters a list of entries down to the inclusive range defined by the given cells, in O(log N) time.
      private void getEdgesInChildrenCells​(S2Point a, S2Point b, java.util.List<S2CellId> cover, java.util.Set<java.lang.Integer> candidateCrossings)
      Appends to candidateCrossings the edges that are fully contained in an S2 covering of edge.
      private void getEdgesInParentCells​(java.util.List<S2CellId> cover, java.util.Set<java.lang.Integer> candidateCrossings)
      Adds to candidateCrossings all the edges present in any ancestor of any cell of cover, down to minimumS2LevelUsed.
      abstract int getNumEdges()
      Returns the number of edges in this index.
      protected void incrementQueryCount()
      Tell the index that we just received a new request for candidates.
      boolean isIndexComputed()  
      void predictAdditionalCalls​(int n)
      If the index hasn't been computed yet, looks at how much work has gone into iterating using the brute force method, and how much more work is planned as defined by 'cost'.
      void reset()
      Empties the index in case it already contained something.
      private void sortIndex()
      Sorts the parallel cells and edges arrays.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • THICKENING

        private static final double THICKENING
        Thicken the edge in all directions by roughly 1% of the edge length when thickenEdge is true.
        See Also:
        Constant Field Values
      • cells

        private long[] cells
        The cell containing each edge, as given in the parallel array edges.
      • edges

        private int[] edges
        The edge contained by each cell, as given in the parallel array cells.
      • minimumS2LevelUsed

        private int minimumS2LevelUsed
        No cell strictly below this level appears in mapping. Initially leaf level, that's the minimum level at which we will ever look for test edges.
      • indexComputed

        private boolean indexComputed
        Has the index been computed already?
      • queryCount

        private int queryCount
        Number of queries so far
    • Constructor Detail

      • S2EdgeIndex

        public S2EdgeIndex()
    • Method Detail

      • reset

        public void reset()
        Empties the index in case it already contained something.
      • compare

        private static final int compare​(long cell1,
                                         int edge1,
                                         long cell2,
                                         int edge2)
        Compares [cell1, edge1] to [cell2, edge2], by cell first and edge second.
        Returns:
        -1 if [cell1, edge1] is less than [cell2, edge2], 1 if [cell1, edge1] is greater than [cell2, edge2], 0 otherwise.
      • computeIndex

        public final void computeIndex()
        Computes the index (if it has not been previously done).
      • sortIndex

        private void sortIndex()
        Sorts the parallel cells and edges arrays.
      • isIndexComputed

        public final boolean isIndexComputed()
      • incrementQueryCount

        protected final void incrementQueryCount()
        Tell the index that we just received a new request for candidates. Useful to compute when to switch to quad tree.
      • predictAdditionalCalls

        public final void predictAdditionalCalls​(int n)
        If the index hasn't been computed yet, looks at how much work has gone into iterating using the brute force method, and how much more work is planned as defined by 'cost'. If it were to have been cheaper to use a quad tree from the beginning, then compute it now. This guarantees that we will never use more than twice the time we would have used had we known in advance exactly how many edges we would have wanted to test. It is the theoretical best.

        The value 'n' is the number of iterators we expect to request from this edge index.

        If we have m data edges and n query edges, then the brute force cost is m * n * testCost where testCost is taken to be the cost of EdgeCrosser.robustCrossing, measured to be about 30ns at the time of this writing.

        If we compute the index, the cost becomes: m * costInsert + n * costFind(m)

        • costInsert can be expected to be reasonably stable, and was measured at 1200ns with the BM_QuadEdgeInsertionCost benchmark.
        • costFind depends on the length of the edge . For m=1000 edges, we got timings ranging from 1ms (edge the length of the polygon) to 40ms. The latter is for very long query edges, and needs to be optimized. We will assume for the rest of the discussion that costFind is roughly 3ms.

        When doing one additional query, the differential cost is m * testCost - costFind(m) With the numbers above, it is better to use the quad tree (if we have it) if m >= 100.

        If m = 100, 30 queries will give m*n*testCost = m * costInsert = 100ms, while the marginal cost to find is 3ms. Thus, this is a reasonable thing to do.

      • getNumEdges

        public abstract int getNumEdges()
        Returns the number of edges in this index.
      • edgeFrom

        public abstract S2Point edgeFrom​(int index)
        Returns the starting vertex of the edge at offset index.
      • edgeTo

        public abstract S2Point edgeTo​(int index)
        Returns the ending vertex of the edge at offset index.
      • edgeFromTo

        public S2Edge edgeFromTo​(int index)
        Return both vertices of the given index in one call. Can be overridden by some subclasses to more efficiently retrieve both edge points at once, which makes a difference in performance, especially for small loops.
      • findCandidateCrossings

        protected void findCandidateCrossings​(S2Point a,
                                              S2Point b,
                                              java.util.List<java.lang.Integer> candidateCrossings)
        Appends to "candidateCrossings" all edge references which may cross the given edge. This is done by covering the edge and then finding all references of edges whose coverings overlap this covering. Parent cells are checked level by level. Child cells are checked all at once by taking advantage of the natural ordering of S2CellIds.
      • containingCell

        private static S2CellId containingCell​(S2Point pa,
                                               S2Point pb)
        Returns the smallest cell containing both points, or Sentinel if they are not all on the same face. The points don't need to be normalized.
      • getCovering

        private int getCovering​(S2Point a,
                                S2Point b,
                                boolean thickenEdge,
                                java.util.ArrayList<S2CellId> edgeCovering)
        Computes a cell covering of an edge. Clears edgeCovering and returns the level of the s2 cells used in the covering (only one level is ever used for each call).

        If thickenEdge is true, the edge is thickened and extended by 1% of its length.

        It is guaranteed that no child of a covering cell will fully contain the covered edge.

      • getEdges

        private int[] getEdges​(long cell1,
                               long cell2)
        Filters a list of entries down to the inclusive range defined by the given cells, in O(log N) time.
        Parameters:
        cell1 - One side of the inclusive query range.
        cell2 - The other side of the inclusive query range.
        Returns:
        An array of length 2, containing the start/end indices.
      • binarySearch

        private int binarySearch​(long cell,
                                 int edge)
      • getEdgesInParentCells

        private void getEdgesInParentCells​(java.util.List<S2CellId> cover,
                                           java.util.Set<java.lang.Integer> candidateCrossings)
        Adds to candidateCrossings all the edges present in any ancestor of any cell of cover, down to minimumS2LevelUsed. The cell->edge map is in the variable mapping.
      • edgeIntersectsCellBoundary

        private static boolean edgeIntersectsCellBoundary​(S2Point a,
                                                          S2Point b,
                                                          S2Cell cell)
        Returns true if the edge and the cell (including boundary) intersect.
      • getEdgesInChildrenCells

        private void getEdgesInChildrenCells​(S2Point a,
                                             S2Point b,
                                             java.util.List<S2CellId> cover,
                                             java.util.Set<java.lang.Integer> candidateCrossings)
        Appends to candidateCrossings the edges that are fully contained in an S2 covering of edge. The covering of edge used is initially cover, but is refined to eliminate quickly subcells that contain many edges but do not intersect with edge.
      • clipEdge

        public void clipEdge​(S2Point a0,
                             S2Point a1,
                             boolean addSharedEdges,
                             java.util.Collection<ParametrizedS2Point> intersections)
        Adds points where the edge index intersects the edge [a0, a1] to intersections. Each intersection is paired with a t-value indicating the fractional geodesic rotation of the intersection from 0 (at a0) to 1 (at a1).
        Parameters:
        a0 - First vertex of the edge to clip.
        a1 - Second vertex of the edge to clip.
        addSharedEdges - Whether an exact duplicate of [a0, a1] in the index should count as an intersection or not.
        intersections - The resulting list of intersections.