Class S2ShapeIndex

java.lang.Object
com.google.common.geometry.S2ShapeIndex
All Implemented Interfaces:
Serializable
Direct Known Subclasses:
S2ShapeIndexCoder.EncodedS2ShapeIndex

@GwtCompatible public class S2ShapeIndex extends Object implements Serializable
See Also:
  • Field Details

    • serialVersionUID

      private static final long serialVersionUID
      See Also:
    • CELL_PADDING

      public static final double CELL_PADDING
      The amount in UV coordinates by which cells are "padded" to compensate for numerical errors when clipping line segments to cell boundaries. The total error when clipping an edge comes from two sources:
      1. Clipping the original spherical edge to a cube face (the "face edge"). The maximum error in this step is S2EdgeUtil.FACE_CLIP_ERROR_UV_COORD.
      2. Clipping the face edge to the u- or v-coordinate of a cell boundary. The maximum error in this step is S2EdgeUtil.EDGE_CLIP_ERROR_UV_COORD.

      Finally, since we encounter the same errors when clipping query edges, we double the total error so that we only need to pad edges during indexing and not at query time.

    • DEFAULT_MAX_EDGES_PER_CELL

      public static final int DEFAULT_MAX_EDGES_PER_CELL
      Default maximum number of edges per cell (not counting 'long' edges). Reasonable values range from 10 to 50. Small values makes queries faster, while large values make construction faster and use less memory.
      See Also:
    • DEFAULT_CELL_SIZE_TO_LONG_EDGE_RATIO

      public static final double DEFAULT_CELL_SIZE_TO_LONG_EDGE_RATIO
      Default maximum cell size, relative to an edge's length, for which that edge is considered 'long'. Long edges are not counted towards S2ShapeIndex.Options.maxEdgesPerCell. The size and speed of the index are typically not very sensitive to this parameter. Reasonable values range from 0.1 to 10, with smaller values causing more aggressive subdivision of long edges grouped closely together.
      See Also:
    • MIN_SHORT_EDGE_FRACTION

      static final double MIN_SHORT_EDGE_FRACTION
      The minimum fraction of 'short' edges that must be present in a cell in order for it to be subdivided. If this parameter is non-zero then the total index size and construction time are guaranteed to be linear in the number of input edges, where the constant of proportionality has the form (c1 + c2 * (1 - f) / f). Reasonable values range from 0.1 to perhaps 0.95. Values up to about 0.8 have almost no effect on 'normal' geometry except for a small increase in index construction time (proportional to f) for very large inputs. For worst-case geometry, larger parameter values result in indexes that are smaller and faster to construct but have worse query performance (due to having more edges per cell). Essentially this parameter provides control over a space-time trade-off that largely affects only pathological geometry.

      Specifically, the maximum index size is

      O((c1 + c2 * (1 - f) / f) * n)
      , where n is the number of input edges, f is this parameter value, and constant c2 is roughly 20 times larger than constant c1. The exact values of c1 and c2 depend on S2ShapeIndex.Options.cellSizeToLongEdgeRatio and S2ShapeIndex.Options.maxEdgesPerCell parameters and certain properties of the input geometry such as whether it consists of O(1) shapes, whether it includes polygons, and whether the polygon interiors are disjoint.

      The main factors to consider when choosing this parameter are:

      • For pathological geometry, larger values result in indexes that are smaller and faster to construct but have worse query performance, due to having more edges per cell. However, note that even a setting of 0.1 reduces the worst case by 100x compared with a setting of 0.001.
      • For normal geometry, values up to about 0.8 result in indexes that are virtually unchanged except for a slight increase in index construction time, proportional to the parameter value f, for very large inputs. With millions of edges, indexing time increases by about (15% * f), e.g. a parameter value of 0.5 slows down indexing for very large inputs by about 7.5%. Indexing time for small inputs is unaffected.
      • Values larger than about 0.8 start to affect index construction even for normal geometry, resulting in smaller indexes and faster construction times but gradually worse query performance.

      The default value of 0.2 was chosen to make index construction as fast as possible while still protecting against possible quadratic space usage.

      See Also:
    • CURRENT_ENCODING_VERSION

      public static final int CURRENT_ENCODING_VERSION
      The current encoding version. When adding a new encoding, be aware that old binaries will not be able to decode it.
      See Also:
    • options

      private final S2ShapeIndex.Options options
      The options supplied for this index.
    • shapes

      protected List<S2Shape> shapes
      Shapes currently in the index.
    • cells

      private List<S2ShapeIndex.Cell> cells
      Essentially a map from each non-overlapping cell id to the shapes that intersect that cell, clipped to include only the edges that intersect.

      Note that this field is updated lazily. Accessing the iterator is the most common way to construct the index.

    • pendingInsertionsBegin

      private int pendingInsertionsBegin
      The index of the first shape that has been queued for insertion but not processed yet.
    • pendingRemovals

      private final List<S2Shape> pendingRemovals
      The shapes that have been queued for removal but not processed yet (not yet used.)
    • isIndexFresh

      private volatile boolean isIndexFresh
      If true, the index is up to date. If false the index is updating or stale and requires an update. This is marked volatile to avoid memory consistency errors with this field, which allows us to avoid taking a lock when no update is required.
  • Constructor Details

    • S2ShapeIndex

      public S2ShapeIndex()
      Creates an S2ShapeIndex that uses the default options, S2ShapeIndex.Options.
    • S2ShapeIndex

      public S2ShapeIndex(S2ShapeIndex.Options options)
      Creates an S2ShapeIndex with the given options.
  • Method Details

    • options

      public S2ShapeIndex.Options options()
      Returns the options used for this index.
    • getShapes

      public List<S2Shape> getShapes()
      Returns an immutable list view of shapes in the index. When shapes are added or removed, the returned view is updated as well.
    • add

      public void add(S2Shape shape)
      Adds the given shape to this index. Invalidates all iterators and their associated data.
    • remove

      public void remove(S2Shape shape)
      Currently not implemented. Will eventually remove the given shape from the index, and invalidate all iterators and their associated data.
      Parameters:
      shape - the shape to remove
    • reset

      public void reset()
      Clears the contents of the index and resets it to its original state.
    • iterator

      public S2Iterator<S2ShapeIndex.Cell> iterator()
      Returns a new iterator over the cells of this index, positioned at the first cell in the index, after initializing any pending updates.
    • isFresh

      public boolean isFresh()
      Returns true if there are no pending updates that need to be applied. This can be useful to avoid building the index unnecessarily, or for choosing between two different algorithms depending on whether the index is available.
    • applyUpdates

      void applyUpdates()
      Ensures pending updates have been applied, returning immediately if the index is fresh as reported by isFresh(), and otherwise blocking while the index is built.

      This operation is thread safe, guarded by 'this'.

    • reserveSpace

      private void reserveSpace(int numEdges, List<List<S2ShapeIndex.FaceEdge>> allEdges)
      Reserves an appropriate amount of space for the top-level face edges. These lists are responsible for most of the temporary memory usage during index construction. Furthermore, if the arrays are grown via add() then a large fraction of the total run time consists of copying data as these arrays grow, or handling GC events since reallocating a large array generates objects that are difficult for the GC to reap cleanly without a stop-the-world collection.

      However, creating the lists of edges for each face with this method is about 1% slower than just using a List with smooth capacity increases. See S2ShapeIndex.ShardedList for details on the implementation, but note also that allocating single large lists is hard on the Java garbage collection environment, so not only is this method slower in the absence of GC measurements, it is significantly faster when you also consider the impact of very large array allocations on the garbage collector.

    • addShapeEdges

      private void addShapeEdges(int shapeId, List<List<S2ShapeIndex.FaceEdge>> allEdges, S2ShapeIndex.InteriorTracker tracker)
      Clips all edges of the given shape to the six cube faces, and adds the clipped edges to allEdges.
    • updateFaceEdges

      private void updateFaceEdges(int face, List<S2ShapeIndex.FaceEdge> faceEdges, S2ShapeIndex.InteriorTracker tracker)
      Given a face and a list of edges that intersect that face, insert or remove all the edges from the index. (An edge is inserted if shape(id) is not null, and removed otherwise.)
    • skipCellRange

      private void skipCellRange(S2CellId begin, S2CellId end, S2ShapeIndex.InteriorTracker tracker, S2ShapeIndex.EdgeAllocator alloc)
      Skips over the cells in the given range, creating index cells if we are currently in the interior of at least one shape.
    • makeIndexCell

      boolean makeIndexCell(S2PaddedCell pcell, List<S2ShapeIndex.ClippedEdge> edges, S2ShapeIndex.InteriorTracker tracker)
      Given a cell and a set of ClippedEdges whose bounding boxes intersect that cell, insert or remove all the edges from the index. Temporary space for edges that need to be subdivided is allocated from the given EdgeAllocator.
    • updateEdges

      private void updateEdges(S2PaddedCell pcell, List<S2ShapeIndex.ClippedEdge> edges, S2ShapeIndex.InteriorTracker tracker, S2ShapeIndex.EdgeAllocator alloc)
    • updateBound

      private static S2ShapeIndex.ClippedEdge updateBound(S2ShapeIndex.ClippedEdge edge, boolean uEnd, double u, boolean vEnd, double v, S2ShapeIndex.EdgeAllocator alloc)
      Given an edge and two bound endpoints that need to be updated, allocates and returns a new edge with the updated bound.
    • clipUBound

      private static S2ShapeIndex.ClippedEdge clipUBound(S2ShapeIndex.ClippedEdge edge, boolean uEnd, double u, S2ShapeIndex.EdgeAllocator alloc)
    • clipVBound

      private static S2ShapeIndex.ClippedEdge clipVBound(S2ShapeIndex.ClippedEdge edge, boolean vEnd, double v, S2ShapeIndex.EdgeAllocator alloc)
    • clipVAxis

      private static void clipVAxis(S2ShapeIndex.ClippedEdge edge, R1Interval middle, List<S2ShapeIndex.ClippedEdge> edges0, List<S2ShapeIndex.ClippedEdge> edges1, S2ShapeIndex.EdgeAllocator alloc)
    • getEdgeMaxLevel

      static final int getEdgeMaxLevel(S2Point va, S2Point vb, double cellSizeToLongEdgeRatio)
      Returns the first level for which the given edge will be considered "long", i.e. it will not count towards the S2ShapeIndex.Options.maxEdgesPerCell limit.
    • createList

      static final <T> List<T> createList(int maxSize)
      Creates a new list, using a SimpleList when the predicted maximum size is small, and a sharded list when the predicted size is large enough to be worth it.