Class 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 calls doneCellId(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 if addShape(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 (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 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.
      • 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.
    • Method Detail

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