Class S2ShapeIndex

    • Field Detail

      • 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:
        Constant Field Values
      • 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:
        Constant Field Values
      • 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:
        Constant Field Values
      • 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:
        Constant Field Values
      • shapes

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

        private java.util.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 java.util.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 Detail

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

      • getShapes

        public java.util.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,
                                  java.util.List<java.util.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,
                                   java.util.List<java.util.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,
                                     java.util.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.)
      • makeIndexCell

        boolean makeIndexCell​(S2PaddedCell pcell,
                              java.util.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.
      • 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> java.util.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.