Class S2EdgeIndex

java.lang.Object
com.google.common.geometry.S2EdgeIndex
Direct Known Subclasses:
S2Polygon.S2PolygonIndex
@GwtCompatible public abstract class S2EdgeIndex extends Object

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

  • Constructor Summary

    Constructors
    Constructor
    Description
    S2EdgeIndex()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    clipEdge(S2Point a0, S2Point a1, boolean addSharedEdges, Collection<ParametrizedS2Point> intersections)
    Adds points where the edge index intersects the edge [a0, a1] to intersections.
    final void
    computeIndex()
    Computes the index (if it has not been previously done).
    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.
    abstract S2Point
    edgeTo(int index)
    Returns the ending vertex of the edge at offset index.
    protected void
    findCandidateCrossings(S2Point a, S2Point b, List<Integer> candidateCrossings)
    Appends to "candidateCrossings" all edge references which may cross the given edge.
    abstract int
    getNumEdges()
    Returns the number of edges in this index.
    protected final void
    incrementQueryCount()
    Tell the index that we just received a new request for candidates.
    final boolean
    isIndexComputed()
     
    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'.
    void
    reset()
    Empties the index in case it already contained something.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • S2EdgeIndex

      public S2EdgeIndex()

  • Method Details

    • reset

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

    • computeIndex

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

    • 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, List<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.

    • clipEdge

      public void clipEdge(S2Point a0, S2Point a1, boolean addSharedEdges, 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.