Class S2ShapeIndex.InteriorTracker
- java.lang.Object
-
- com.google.common.geometry.S2ShapeIndex.InteriorTracker
-
- Enclosing class:
- S2ShapeIndex
final class S2ShapeIndex.InteriorTracker extends java.lang.Object
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. We use this to compute which shapes contain the center of every S2CellId in the index, by advancing the focus from one cell center to the next.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
Fields Modifier and Type Field Description private S2EdgeUtil.EdgeCrosser
crosser
A temporary crosser from the old focus to the new focus.private int
focusCount
The number of elements in 'focusedShapes' that are valid and in use.private int[]
focusedShapes
The set of shape ids (the indices of each shape in the S2ShapeIndex.shapes field) that contain the current focus.private boolean
isActive
Whether any shapes have an interior.private S2Point
lastEnd
The last exit vertex.private S2Point
newFocus
The new focus point.private S2CellId
nextCellId
The ideal next cell ID such that the entry vertex of that cell would match the exit vertex of this cell.private S2Point
oldFocus
The prior focus point.private S2ShapeIndex.S2ClippedShape[]
tempClippedShapes
A temporary array in which to accumulate the clipped shapes for each cell.
-
Constructor Summary
Constructors Constructor Description InteriorTracker(int numShapes)
Initializes the InteriorTracker.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
addShape(int shapeId, S2Shape shape)
Adds a shape whose interior should be tracked.boolean
atCellId(S2CellId cellid)
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
drawTo(S2Point focus)
Moves the focus to the given point.boolean
isActive()
Returns true ifaddShape(int, S2Shape)
has been called at least once.void
moveTo(S2Point b)
Moves the focus to the given point.void
testEdge(int shapeId, S2Point start, S2Point end)
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 Detail
-
isActive
private boolean isActive
Whether any shapes have an interior.
-
oldFocus
private S2Point oldFocus
The prior focus point.
-
newFocus
private S2Point newFocus
The new focus point.
-
lastEnd
private S2Point lastEnd
The last exit vertex.
-
nextCellId
private S2CellId nextCellId
The ideal next cell ID such that the entry vertex of that cell would match the exit vertex of this cell.
-
crosser
private S2EdgeUtil.EdgeCrosser crosser
A temporary crosser from the old focus to the new focus.
-
focusedShapes
private final int[] focusedShapes
The 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 focusCount
The number of elements in 'focusedShapes' that are valid and in use.
-
tempClippedShapes
private final S2ShapeIndex.S2ClippedShape[] tempClippedShapes
A temporary array in which to accumulate the clipped shapes for each cell.
-
-
Constructor Detail
-
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 Detail
-
isActive
public boolean isActive()
Returns true ifaddShape(int, S2Shape)
has been called at least once.
-
addShape
public void addShape(int shapeId, S2Shape shape)
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
public void moveTo(S2Point b)
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
public void drawTo(S2Point focus)
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
public void testEdge(int shapeId, S2Point start, S2Point end)
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
public void doneCellId(S2CellId cellid)
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
public boolean atCellId(S2CellId cellid)
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.
-
-