Class S2ShapeIndex
- All Implemented Interfaces:
Serializable
- Direct Known Subclasses:
S2ShapeIndexCoder.EncodedS2ShapeIndex
- See Also:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic class
This class contains the set of clipped shapes within a particular index cell, sorted in increasing order of shape id.static enum
The possible relationships between a "target" cell and the cells of the S2ShapeIndex.private static class
ClippedEdge represents the portion of a FaceEdge that has been clipped to an S2Cell.private static final class
This class provides temporary storage for new ClippedEdges that are created during indexing.private static final class
FaceEdge stores temporary edge data while the index is being updated.(package private) final class
Given a set of shapes, InteriorTracker keeps track of which shapes contain a particular point (the "focus".) It provides an efficient way to move the focus from one point to another and incrementally update the set of shapes which contain it.static class
Options that affect construction of the S2ShapeIndex.static final class
RangeIterator is a wrapper over CellIterator that is specialized for merging shape indices.static class
S2ClippedShape represents the part of a shape that intersects an S2Cell.private static final class
A more complex append-only RandomAccess List that allocates space in shards of 256 elements each, avoiding reallocation as the list grows, and avoiding single allocations larger than 2KB.private static final class
A simple append-only RandomAccess List similar to (but about 10% faster than) ArrayList. -
Field Summary
FieldsModifier and TypeFieldDescriptionstatic final double
The amount in UV coordinates by which cells are "padded" to compensate for numerical errors when clipping line segments to cell boundaries.private List
<S2ShapeIndex.Cell> Essentially a map from each non-overlapping cell id to the shapes that intersect that cell, clipped to include only the edges that intersect.static final int
The current encoding version.static final double
Default maximum cell size, relative to an edge's length, for which that edge is considered 'long'.static final int
Default maximum number of edges per cell (not counting 'long' edges).private boolean
If true, the index is up to date.(package private) static final double
The minimum fraction of 'short' edges that must be present in a cell in order for it to be subdivided.private final S2ShapeIndex.Options
The options supplied for this index.private int
The index of the first shape that has been queued for insertion but not processed yet.The shapes that have been queued for removal but not processed yet (not yet used.)private static final long
Shapes currently in the index. -
Constructor Summary
ConstructorsConstructorDescriptionCreates an S2ShapeIndex that uses the default options,S2ShapeIndex.Options
.S2ShapeIndex
(S2ShapeIndex.Options options) Creates an S2ShapeIndex with the given options. -
Method Summary
Modifier and TypeMethodDescriptionvoid
Adds the given shape to this index.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 toallEdges
.(package private) void
Ensures pending updates have been applied, returning immediately if the index is fresh as reported byisFresh()
, and otherwise blocking while the index is built.private static S2ShapeIndex.ClippedEdge
clipUBound
(S2ShapeIndex.ClippedEdge edge, boolean uEnd, double u, S2ShapeIndex.EdgeAllocator alloc) private static void
clipVAxis
(S2ShapeIndex.ClippedEdge edge, R1Interval middle, List<S2ShapeIndex.ClippedEdge> edges0, List<S2ShapeIndex.ClippedEdge> edges1, S2ShapeIndex.EdgeAllocator alloc) private static S2ShapeIndex.ClippedEdge
clipVBound
(S2ShapeIndex.ClippedEdge edge, boolean vEnd, double v, S2ShapeIndex.EdgeAllocator alloc) (package private) 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.(package private) 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.Returns an immutable list view of shapes in the index.boolean
isFresh()
Returns true if there are no pending updates that need to be applied.iterator()
Returns a new iterator over the cells of this index, positioned at the first cell in the index, after initializing any pending updates.(package private) 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.options()
Returns the options used for this index.void
Currently not implemented.private void
reserveSpace
(int numEdges, List<List<S2ShapeIndex.FaceEdge>> allEdges) Reserves an appropriate amount of space for the top-level face edges.void
reset()
Clears the contents of the index and resets it to its original state.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.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.private void
updateEdges
(S2PaddedCell pcell, List<S2ShapeIndex.ClippedEdge> edges, S2ShapeIndex.InteriorTracker tracker, S2ShapeIndex.EdgeAllocator alloc) 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.
-
Field Details
-
serialVersionUID
private static final long serialVersionUID- See Also:
-
CELL_PADDING
public static final double CELL_PADDINGThe 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:- 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
. - 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.
- Clipping the original spherical edge to a cube face (the "face edge"). The maximum error
in this step is
-
DEFAULT_MAX_EDGES_PER_CELL
public static final int DEFAULT_MAX_EDGES_PER_CELLDefault 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_RATIODefault maximum cell size, relative to an edge's length, for which that edge is considered 'long'. Long edges are not counted towardsS2ShapeIndex.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_FRACTIONThe 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 onS2ShapeIndex.Options.cellSizeToLongEdgeRatio
andS2ShapeIndex.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_VERSIONThe current encoding version. When adding a new encoding, be aware that old binaries will not be able to decode it.- See Also:
-
options
The options supplied for this index. -
shapes
Shapes currently in the index. -
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 pendingInsertionsBeginThe index of the first shape that has been queued for insertion but not processed yet. -
pendingRemovals
The shapes that have been queued for removal but not processed yet (not yet used.) -
isIndexFresh
private volatile boolean isIndexFreshIf 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
Creates an S2ShapeIndex with the given options.
-
-
Method Details
-
options
Returns the options used for this index. -
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
Adds the given shape to this index. Invalidates all iterators and their associated data. -
remove
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
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 byisFresh()
, and otherwise blocking while the index is built.This operation is thread safe, guarded by 'this'.
-
reserveSpace
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 toallEdges
. -
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
Returns the first level for which the given edge will be considered "long", i.e. it will not count towards theS2ShapeIndex.Options.maxEdgesPerCell
limit. -
createList
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.
-