Class S2ShapeIndex.InteriorTracker

java.lang.Object
com.google.common.geometry.S2ShapeIndex.InteriorTracker
Enclosing class:
S2ShapeIndex

final class S2ShapeIndex.InteriorTracker extends 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
    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.
    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

    Modifier and Type
    Method
    Description
    void
    addShape(int shapeId, S2Shape shape)
    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 calls doneCellId(S2CellId) as each cell is processed).
    void
    Indicates that the caller has finished processing the given S2CellId.
    void
    drawTo(S2Point focus)
    Moves the focus to the given point.
    boolean
    Returns true if addShape(int, S2Shape) has been called at least once.
    void
    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 (see drawTo(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.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

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

  • Method Details

    • isActive

      public boolean isActive()
      Returns true if addShape(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 calling testEdge(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 use drawTo(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 (see drawTo(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 with atCellId(S2CellId), the caller can avoid calling moveTo(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 calls doneCellId(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.