RTree

RTree module: ezdxf.math.rtree

class ezdxf.math.rtree.RTree(points: Iterable[T], max_node_size: int = 5)

Immutable spatial search tree loosely based on R-trees.

The search tree is buildup once at initialization and immutable afterwards, because rebuilding the tree after inserting or deleting nodes is very costly and makes the implementation very complex.

Without the ability to alter the content the restrictions which forces the tree balance at growing and shrinking of the original R-trees, are ignored, like the fixed minimum and maximum node size.

This class uses internally only 3D bounding boxes, but also supports Vec2 as well as Vec3 objects as input data, but point types should not be mixed in a search tree.

The point objects keep their type and identity and the returned points of queries can be compared by the is operator for identity to the input points.

The implementation requires a maximum node size of at least 2 and does not support empty trees!

Raises:

ValueError – max. node size too small or no data given

__len__()

Returns the count of points in the search tree.

__iter__() → Iterator[T]

Yields all points in the search tree.

contains(point: T) → bool

Returns True if point exists, the comparison is done by the isclose() method and not by the identity operator is.

nearest_neighbor(target: T) → tuple[T, float]

Returns the closest point to the target point and the distance between these points.

points_in_sphere(center: T, radius: float) → Iterator[T]

Returns all points in the range of the given sphere including the points at the boundary.

points_in_bbox(bbox: BoundingBox) → Iterator[T]

Returns all points in the range of the given bounding box including the points at the boundary.

avg_leaf_size(spread: float = 1.0) → float

Returns the average size of the leaf bounding boxes. The size of a leaf bounding box is the maximum size in all dimensions. Excludes outliers of sizes beyond mean + standard deviation * spread. Returns 0.0 if less than two points in tree.

avg_spherical_envelope_radius(spread: float = 1.0) → float

Returns the average radius of spherical envelopes of the leaf nodes. Excludes outliers with radius beyond mean + standard deviation * spread. Returns 0.0 if less than two points in tree.

avg_nn_distance(spread: float = 1.0) → float

Returns the average of the nearest neighbor distances inside (!) leaf nodes. Excludes outliers with a distance beyond the overall mean + standard deviation * spread. Returns 0.0 if less than two points in tree.

Warning

This is a brute force check with O(n!) for each leaf node, where n is the point count of the leaf node.