Class S2ShapeIndex.InteriorTracker
- Enclosing class:
S2ShapeIndex
Initially the focus is S2.origin(), and therefore we can initialize the state of every shape to its containsOrigin() value. Next we advance the focus to the start of the S2CellId space- filling curve, by drawing a line segment between this point and S2.origin() and testing whether every edge of every shape intersects it. Then we visit all the cells that are being added to the S2ShapeIndex in increasing order of S2CellId.
For each cell, we draw two edges: one from the entry vertex to the center, and another from the center to the exit vertex (where "entry" and "exit" refer to the points where the space- filling curve enters and exits the cell). By counting edge crossings we can incrementally compute which shapes contain the cell center.
Note that the same set of shapes will always contain the exit point of one cell and the entry point of the next cell in the index, because either (a) these two points are actually the same, or (b) the intervening cells in S2CellId order are all empty, and therefore there are no edge crossings if we follow this path from one cell to the other.
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate S2EdgeUtil.EdgeCrosser
A temporary crosser from the old focus to the new focus.private int
The number of elements in 'focusedShapes' that are valid and in use.private final int[]
The set of shape ids (the indices of each shape in the S2ShapeIndex.shapes field) that contain the current focus.private boolean
Whether any shapes have an interior.private S2Point
The last exit vertex.private S2Point
The new focus point.private S2CellId
The ideal next cell ID such that the entry vertex of that cell would match the exit vertex of this cell.private S2Point
The prior focus point.private final S2ShapeIndex.S2ClippedShape[]
A temporary array in which to accumulate the clipped shapes for each cell. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
Adds a shape whose interior should be tracked.boolean
Returns true if the focus is already at the entry vertex of the given S2CellId (provided that the caller callsdoneCellId(S2CellId)
as each cell is processed).void
doneCellId
(S2CellId cellid) Indicates that the caller has finished processing the given S2CellId.void
Moves the focus to the given point.boolean
isActive()
Returns true ifaddShape(int, S2Shape)
has been called at least once.void
Moves the focus to the given point.void
Tests whether the given edge of the given shape may cross the line segment between the old and new focus locations (seedrawTo(S2Point)
), and if there is a crossing the shape's containment of the focus is toggled.private void
toggleShape
(int shapeId) Toggles the given shape ID from the list of shapes that contain the current focus; if the shape was not in the set, add it; if it was in the set, remove it.
-
Field Details
-
isActive
private boolean isActiveWhether any shapes have an interior. -
oldFocus
The prior focus point. -
newFocus
The new focus point. -
lastEnd
The last exit vertex. -
nextCellId
The ideal next cell ID such that the entry vertex of that cell would match the exit vertex of this cell. -
crosser
A temporary crosser from the old focus to the new focus. -
focusedShapes
private final int[] focusedShapesThe set of shape ids (the indices of each shape in the S2ShapeIndex.shapes field) that contain the current focus. Sorted by ID in ascending order. -
focusCount
private int focusCountThe number of elements in 'focusedShapes' that are valid and in use. -
tempClippedShapes
A temporary array in which to accumulate the clipped shapes for each cell.
-
-
Constructor Details
-
InteriorTracker
public InteriorTracker(int numShapes) Initializes the InteriorTracker. You must calladdShape(int, S2Shape)
for each shape that will be tracked before callingmoveTo(S2Point)
ordrawTo(S2Point)
.
-
-
Method Details
-
isActive
public boolean isActive()Returns true ifaddShape(int, S2Shape)
has been called at least once. -
addShape
Adds a shape whose interior should be tracked. This should be followed by callingtestEdge(int, S2Point, S2Point)
with every edge of the given shape. -
moveTo
Moves the focus to the given point. This method should only be used when it is known that there are no edge crossings between the old and new focus locations; otherwise usedrawTo(S2Point)
. -
drawTo
Moves the focus to the given point. After this method is called,testEdge(int, S2Point, S2Point)
should be called with all edges that may cross the line segment between the old and new focus locations. -
testEdge
Tests whether the given edge of the given shape may cross the line segment between the old and new focus locations (seedrawTo(S2Point)
), and if there is a crossing the shape's containment of the focus is toggled. -
doneCellId
Indicates that the caller has finished processing the given S2CellId. By using this method together withatCellId(S2CellId)
, the caller can avoid callingmoveTo(S2Point)
in cases where the exit vertex of the previous cell is the same as the entry vertex of the current cell. -
atCellId
Returns true if the focus is already at the entry vertex of the given S2CellId (provided that the caller callsdoneCellId(S2CellId)
as each cell is processed). -
toggleShape
private void toggleShape(int shapeId) Toggles the given shape ID from the list of shapes that contain the current focus; if the shape was not in the set, add it; if it was in the set, remove it.
-