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 asVec3
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 theisclose()
method and not by the identity operatoris
.
- 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.