1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165
|
# Copyright (c) 2022, Manfred Moitzi
# License: MIT License
import pytest
from ezdxf.math import Vec2, Vec3, BoundingBox, spherical_envelope
from ezdxf.math import rtree
from ezdxf.math.rtree import RTree
def test_can_not_build_empty_tree():
with pytest.raises(ValueError):
RTree([])
class TestFirstLevel:
def test_from_one_point(self):
tree = RTree([Vec3(1, 2, 3)])
assert len(tree) == 1
def test_contains_point(self):
point = Vec3(1, 2, 3)
tree = RTree([point])
assert tree.contains(point)
def test_iter_tree(self):
point = Vec3(1, 2, 3)
tree = RTree([point])
assert list(tree) == [point]
def test_from_two_points(self):
tree = RTree([Vec3(1, 2, 3), Vec3(3, 2, 1)])
assert len(tree) == 2
def test_store_duplicate_points(self):
p = Vec3(1, 2, 3)
tree = RTree([p, p])
assert len(tree) == 2
class TestBiggerTree:
@pytest.fixture(scope="class")
def tree(self):
return RTree([Vec3(x, 0, 0) for x in range(100)], max_node_size=5)
def test_setup_is_correct(self, tree):
assert len(tree) == 100
@pytest.mark.parametrize(
"point", [Vec3(0, 0, 0), Vec3(1, 0, 0), Vec3(99, 0, 0)]
)
def test_known_point_is_present(self, tree, point):
assert tree.contains(point) is True
def test_contains_all_random_points(self):
points = [Vec3.random(50) for _ in range(100)]
tree = RTree(points, 5)
for point in points:
assert tree.contains(point) is True
@pytest.mark.parametrize(
"n, point",
[
(Vec3(0.1, 0, 0), Vec3(0, 0, 0)),
(Vec3(1, 0.1, 0), Vec3(1, 0, 0)),
(Vec3(99, 0, 0.1), Vec3(99, 0, 0)),
],
)
def test_nearest_neighbor(self, tree, n, point):
result, distance = tree.nearest_neighbor(n)
assert result.isclose(point)
assert distance == pytest.approx(0.1)
def test_find_points_in_sphere(self, tree):
points = list(tree.points_in_sphere(Vec3(50, 0, 0), radius=5))
assert len(points) == 11
expected_x_coords = set(range(45, 56))
x_coords = set(int(p.x) for p in points)
assert x_coords == expected_x_coords
def test_find_points_in_bbox(self, tree):
bbox = BoundingBox([(45, 0, 0), (55, 0, 0)])
points = list(tree.points_in_bbox(bbox))
assert len(points) == 11
expected_x_coords = set(range(45, 56))
x_coords = set(int(p.x) for p in points)
assert x_coords == expected_x_coords
def test_iter_tree(self, tree):
points = list(tree)
assert len(points) == 100
assert len(points) == len(tree)
def test_avg_spherical_envelope_radius(self, tree):
assert tree.avg_spherical_envelope_radius() == pytest.approx(1.5)
def test_avg_leaf_size(self, tree):
assert tree.avg_leaf_size() == pytest.approx(3.0)
def test_avg_nn_distance(self, tree):
assert tree.avg_nn_distance() == pytest.approx(1.0)
def test_Vec2_compatibility():
tree = RTree([Vec2(x, 0) for x in range(100)], max_node_size=5)
bbox = BoundingBox([(45, 0, 0), (55, 0, 0)])
points = list(tree.points_in_bbox(bbox))
assert len(points) == 11
expected_x_coords = set(range(45, 56))
x_coords = set(int(p.x) for p in points)
assert x_coords == expected_x_coords
assert any(isinstance(p, Vec2) for p in points)
@pytest.mark.parametrize("strategy", [rtree.box_split])
def test_split_strategies(strategy):
points = [Vec3.random(100) for _ in range(100)]
nodes = strategy(points, 5)
assert len(nodes) == 5
for node in nodes:
assert len(node) == 20
assert isinstance(node, rtree.InnerNode) is True
assert len(node.children) == 5
def test_collect_leafs():
tree = RTree([Vec3.random(100) for _ in range(100)])
assert sum(len(leaf) for leaf in rtree.collect_leafs(tree._root)) == 100
def test_average_leaf_size_of_random_points():
tree = RTree([Vec3.random(100) for _ in range(100)])
size = tree.avg_leaf_size()
assert size > 10.0
def test_avg_spherical_envelope_radius_of_random_points():
tree = RTree([Vec3.random(100) for _ in range(100)])
radius = tree.avg_spherical_envelope_radius()
assert radius > 10.0
def test_avg_nn_distance_of_random_points():
tree = RTree([Vec3.random(100) for _ in range(100)])
nn_dist = tree.avg_nn_distance()
assert nn_dist > 10.0
def test_avg_methods_return_0_for_too_small_trees():
tree = RTree([Vec3()])
assert tree.avg_leaf_size() == 0.0
assert tree.avg_spherical_envelope_radius() == 0.0
assert tree.avg_nn_distance() == 0.0
def test_spherical_envelope():
from ezdxf.render.forms import cube
center, radius = spherical_envelope(cube(center=True).vertices)
assert center.isclose((0, 0, 0))
assert radius == pytest.approx(0.8660254037844386)
if __name__ == "__main__":
pytest.main([__file__])
|