Package org.opentrafficsim.core.geometry

Class Ots2dSet

java.lang.Object

org.opentrafficsim.core.geometry.Ots2dSet

All Implemented Interfaces:

Serializable, Iterable<OtsShape>, Collection<OtsShape>, Set<OtsShape>

public class Ots2dSet
extends Object
implements Set<OtsShape>, Serializable

Set of OtsShape objects and provides methods for fast selection of those objects that intersect an OtsShape.
An Ots2dSet internally stores the OtsShapes 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 OtsShape. 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. OtsShapes that partially cover a non-leaf node are stored in each of the leaf nodes below that node that those OtsShapes (partially) cover. Leaf nodes that cannot be expanded (because they are too small) also store all OtsShapes that partially cover the area of the node.
If removal of an OtsShape 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-2023 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:

• Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
(package private) class	Ots2dSet.QuadTreeIterator	Iterator for quad tree.
(package private) class	Ots2dSet.QuadTreeNode	Spatial-aware storage for a set of OtsShape objects.

Constructor Summary

Constructors

Constructor	Description
Ots2dSet(Rectangle2D boundingBox, double minimumCellSize)	Construct an empty Ots2dSet for a rectangular region.

Method Summary

Modifier and Type	Method	Description
final boolean	add(OtsShape e)
final boolean	addAll(Collection<? extends OtsShape> c)
final void	clear()
final boolean	contains(Object o)
final boolean	containsAll(Collection<?> c)
final Set<OtsShape>	intersectingShapes(Rectangle2D rectangle)	Return the set of all shapes in this Ots2dSet that intersect the given rectangle.
final Set<OtsShape>	intersectingShapes(OtsShape shape)	Return all OtsShapes in this Ots2dSet that intersect a given OtsShape.
final boolean	isEmpty()
final Iterator<OtsShape>	iterator()
final boolean	remove(Object o)
final boolean	removeAll(Collection<?> c)
final boolean	retainAll(Collection<?> c)
final int	size()
final Object[]	toArray()
final <T> T[]	toArray(T[] a)
final String	toString()
(package private) final String	toString(int recursionDepth)	Recursively print this Ots2dSet.
final String	toStringGraphic(int recursionDepth)	Return an ASCII art rendering of this Ots2dSet.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Collection

parallelStream, removeIf, stream, toArray

Methods inherited from interface java.lang.Iterable

forEach

Methods inherited from interface java.util.Set

equals, hashCode, spliterator

Constructor Details

Ots2dSet

public Ots2dSet(Rectangle2D boundingBox,
 double minimumCellSize)
         throws OtsGeometryException

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 an OtsShape is not an error; the add method will return false, indicating that the set has not been modified.)

Parameters:

boundingBox - Rectangle2D; the region

minimumCellSize - double; resolution of the underlying quad tree

Throws:

OtsGeometryException - when the bounding box covers no surface

Method Details

size

public final int size()

Specified by:

size in interface Collection<OtsShape>

Specified by:

size in interface Set<OtsShape>

isEmpty

public final boolean isEmpty()

Specified by:

isEmpty in interface Collection<OtsShape>

Specified by:

isEmpty in interface Set<OtsShape>

contains

public final boolean contains(Object o)

Specified by:

contains in interface Collection<OtsShape>

Specified by:

contains in interface Set<OtsShape>

iterator

public final Iterator<OtsShape> iterator()

Specified by:

iterator in interface Collection<OtsShape>

Specified by:

iterator in interface Iterable<OtsShape>

Specified by:

iterator in interface Set<OtsShape>

toArray

public final Object[] toArray()

Specified by:

toArray in interface Collection<OtsShape>

Specified by:

toArray in interface Set<OtsShape>

toArray

public final <T> T[] toArray(T[] a)

Specified by:

toArray in interface Collection<OtsShape>

Specified by:

toArray in interface Set<OtsShape>

add

public final boolean add(OtsShape e)

Specified by:

add in interface Collection<OtsShape>

Specified by:

add in interface Set<OtsShape>

remove

public final boolean remove(Object o)

Specified by:

remove in interface Collection<OtsShape>

Specified by:

remove in interface Set<OtsShape>

containsAll

public final boolean containsAll(Collection<?> c)

Specified by:

containsAll in interface Collection<OtsShape>

Specified by:

containsAll in interface Set<OtsShape>

addAll

public final boolean addAll(Collection<? extends OtsShape> c)

Specified by:

addAll in interface Collection<OtsShape>

Specified by:

addAll in interface Set<OtsShape>

retainAll

public final boolean retainAll(Collection<?> c)

Specified by:

retainAll in interface Collection<OtsShape>

Specified by:

retainAll in interface Set<OtsShape>

removeAll

public final boolean removeAll(Collection<?> c)

Specified by:

removeAll in interface Collection<OtsShape>

Specified by:

removeAll in interface Set<OtsShape>

clear

public final void clear()

Specified by:

clear in interface Collection<OtsShape>

Specified by:

clear in interface Set<OtsShape>

intersectingShapes

public final Set<OtsShape> intersectingShapes(Rectangle2D rectangle)

Return the set of all shapes in this Ots2dSet that intersect the given rectangle.

Parameters:

rectangle - Rectangle2D; the rectangle

Returns:

Set<OtsShape>; the shapes that intersect the rectangle

toString

final String toString(int recursionDepth)

Recursively print this Ots2dSet.

Parameters:

recursionDepth - int; maximum depth to recurse

Returns:

String

toString

public final String toString()

Overrides:

toString in class Object

intersectingShapes

public final Set<OtsShape> intersectingShapes(OtsShape shape)

Return all OtsShapes in this Ots2dSet that intersect a given OtsShape.

Parameters:

shape - OtsShape; the given OtsShape

Returns:

Set<OtsShape>; all OtsShapes in this Ots2dSet that intersect shape

toStringGraphic

public final String toStringGraphic(int recursionDepth)

Return an ASCII art rendering of this Ots2dSet.

Parameters:

recursionDepth - int; maximum recursion depth

Returns:

String; a somewhat human readable rendering of this Ots2dSet