Package org.opentrafficsim.core.geometry

Class Ots2dSet

java.lang.Object
org.opentrafficsim.core.geometry.Ots2dSet
All Implemented Interfaces:
Serializable, Iterable<org.djutils.draw.line.Polygon2d>, Collection<org.djutils.draw.line.Polygon2d>, Set<org.djutils.draw.line.Polygon2d>
public class Ots2dSet extends Object implements Set<org.djutils.draw.line.Polygon2d>, Serializable
Set of Polygon2d objects and provides methods for fast selection of those objects that intersect a Polygon2d.
An Ots2dSet internally stores the Polygon2ds in a quad tree. At time of construction the minimum cell size is defined. Node expansion is never performed on nodes that are smaller than this limit.
Each node (even the non-leaf nodes) store a set of Polygon2d. Non-leaf nodes locally store those shapes that completely cover the rectangular area of the node. Such shapes are not also stored in leaf nodes below that node. Polygon2ds that partially cover a non-leaf node are stored in each of the leaf nodes below that node that those Polygon2ds (partially) cover. Leaf nodes that cannot be expanded (because they are too small) also store all Polygon2ds that partially cover the area of the node.
If removal of a Polygon2d objects results in a leaf becoming empty, that leaf is removed from its parent (which may then itself become empty and removed in turn).

Copyright (c) 2013-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
BSD-style license. See OpenTrafficSim License.

Author:
Alexander Verbraeck, Peter Knoppers, Wouter Schakel
See Also:

  • Constructor Details

    • Ots2dSet

      public Ots2dSet(org.djutils.draw.bounds.Bounds2d boundingBox, double minimumCellSize) throws IllegalArgumentException
      Construct an empty Ots2dSet for a rectangular region. Objects that do not intersect this region will never be stored in this Ots2dSet. (Trying to add such a Polygon2d is not an error; the add method will return false, indicating that the set has not been modified.)
      Parameters:
      boundingBox - the region
      minimumCellSize - resolution of the underlying quad tree
      Throws:
      IllegalArgumentException - when the bounding box covers no surface or the minimum cell size is not above zero

  • Method Details

    • size

      public final int size()
      Specified by:
      size in interface Collection<org.djutils.draw.line.Polygon2d>
      Specified by:
      size in interface Set<org.djutils.draw.line.Polygon2d>

    • isEmpty

      public final boolean isEmpty()
      Specified by:
      isEmpty in interface Collection<org.djutils.draw.line.Polygon2d>
      Specified by:
      isEmpty in interface Set<org.djutils.draw.line.Polygon2d>

    • contains

      public final boolean contains(Object o)
      Specified by:
      contains in interface Collection<org.djutils.draw.line.Polygon2d>
      Specified by:
      contains in interface Set<org.djutils.draw.line.Polygon2d>

    • iterator

      public final Iterator<org.djutils.draw.line.Polygon2d> iterator()
      Specified by:
      iterator in interface Collection<org.djutils.draw.line.Polygon2d>
      Specified by:
      iterator in interface Iterable<org.djutils.draw.line.Polygon2d>
      Specified by:
      iterator in interface Set<org.djutils.draw.line.Polygon2d>

    • toArray

      public final Object[] toArray()
      Specified by:
      toArray in interface Collection<org.djutils.draw.line.Polygon2d>
      Specified by:
      toArray in interface Set<org.djutils.draw.line.Polygon2d>

    • toArray

      public final <T> T[] toArray(T[] a)
      Specified by:
      toArray in interface Collection<org.djutils.draw.line.Polygon2d>
      Specified by:
      toArray in interface Set<org.djutils.draw.line.Polygon2d>

    • add

      public final boolean add(org.djutils.draw.line.Polygon2d e)
      Specified by:
      add in interface Collection<org.djutils.draw.line.Polygon2d>
      Specified by:
      add in interface Set<org.djutils.draw.line.Polygon2d>

    • remove

      public final boolean remove(Object o)
      Specified by:
      remove in interface Collection<org.djutils.draw.line.Polygon2d>
      Specified by:
      remove in interface Set<org.djutils.draw.line.Polygon2d>

    • containsAll

      public final boolean containsAll(Collection<?> c)
      Specified by:
      containsAll in interface Collection<org.djutils.draw.line.Polygon2d>
      Specified by:
      containsAll in interface Set<org.djutils.draw.line.Polygon2d>

    • addAll

      public final boolean addAll(Collection<? extends org.djutils.draw.line.Polygon2d> c)
      Specified by:
      addAll in interface Collection<org.djutils.draw.line.Polygon2d>
      Specified by:
      addAll in interface Set<org.djutils.draw.line.Polygon2d>

    • retainAll

      public final boolean retainAll(Collection<?> c)
      Specified by:
      retainAll in interface Collection<org.djutils.draw.line.Polygon2d>
      Specified by:
      retainAll in interface Set<org.djutils.draw.line.Polygon2d>

    • removeAll

      public final boolean removeAll(Collection<?> c)
      Specified by:
      removeAll in interface Collection<org.djutils.draw.line.Polygon2d>
      Specified by:
      removeAll in interface Set<org.djutils.draw.line.Polygon2d>

    • clear

      public final void clear()
      Specified by:
      clear in interface Collection<org.djutils.draw.line.Polygon2d>
      Specified by:
      clear in interface Set<org.djutils.draw.line.Polygon2d>

    • intersectingShapes

      public final Set<org.djutils.draw.line.Polygon2d> intersectingShapes(org.djutils.draw.bounds.Bounds2d rectangle)
      Return the set of all shapes in this Ots2dSet that intersect the given rectangle.
      Parameters:
      rectangle - the rectangle
      Returns:
      the shapes that intersect the rectangle

    • toString

      final String toString(int recursionDepth)
      Recursively print this Ots2dSet.
      Parameters:
      recursionDepth - maximum depth to recurse
      Returns:
      String

    • toString

      public final String toString()
      Overrides:
      toString in class Object

    • intersectingShapes

      public final Set<org.djutils.draw.line.Polygon2d> intersectingShapes(org.djutils.draw.line.Polygon2d shape)
      Return all Polygon2ds in this Ots2dSet that intersect a given Polygon2d.
      Parameters:
      shape - the given Polygon2d
      Returns:
      all Polygon2ds in this Ots2dSet that intersect shape

    • toStringGraphic

      public final String toStringGraphic(int recursionDepth)
      Return an ASCII art rendering of this Ots2dSet.
      Parameters:
      recursionDepth - maximum recursion depth
      Returns:
      a somewhat human readable rendering of this Ots2dSet