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
166
167
168
169
170
171
172
173
174
175
176
177
178
|
# Copyright (c) 2020-2024, Manfred Moitzi
# License: MIT License
import time
from ezdxf.math import Vec3, closest_point
from ezdxf.math.rtree import RTree
try:
import matplotlib.pyplot as plt
except ImportError:
plt = None
def random_points(n, size=1.0):
return [Vec3.random() * size for _ in range(n)]
def profile_build_time_random_rtree(count: int, points, max_node_size: int):
for _ in range(count):
RTree(points, max_node_size)
def profile_tree_contains_points(count, tree, points):
for _ in range(count):
for point in points:
assert tree.contains(point) is True
def profile_tree_nearest_neighbor(count, tree, points):
for _ in range(count):
for point in points:
assert isinstance(tree.nearest_neighbor(point)[0], Vec3)
def brute_force_contains(points, point):
for p in points:
if p.isclose(point):
return True
return False
def profile_brute_force_contains_points(count, points):
for _ in range(count):
for point in points:
assert brute_force_contains(points, point) is True
def profile_brute_force_closest_point(count, points, search_points):
for _ in range(count):
for point in search_points:
assert isinstance(closest_point(point, points), Vec3)
def profile(func, *args):
t0 = time.perf_counter()
func(*args)
t1 = time.perf_counter()
delta = t1 - t0
return delta
def profile_rtree_building(repeat: int, max_size: int):
log = []
for size in range(100, 2000, 100):
points = random_points(size, 50.0)
name = f"RTree({size}, {max_size})"
t0 = profile(profile_build_time_random_rtree, repeat, points, max_size)
time_str = f"{t0:6.2f}s"
print(f"Build random {name}, {repeat}x , {time_str}")
log.append((size, t0))
return log
def profile_rtree_contains_all_points(repeat: int, max_size: int):
log = []
for size in range(100, 2000, 100):
points = random_points(size, 50.0)
tree = RTree(points, max_size)
name = f"RTree({size}, {max_size})"
t0 = profile(profile_tree_contains_points, repeat, tree, points)
time_str = f"{t0:6.2f}s"
print(f"{name} contains all points, {repeat}x , {time_str}")
log.append((size, t0))
return log
def profile_rtree_nearest_neighbor(repeat: int, max_size: int):
log = []
for size in range(100, 2000, 100):
points = random_points(size, 50.0)
tree = RTree(points, max_size)
name = f"RTree({size}, {max_size})"
search_points = random_points(100, 50.0)
t0 = profile(profile_tree_nearest_neighbor, repeat, tree, search_points)
time_str = f"{t0:6.2f}s"
print(f"{name} nearest neighbor, {repeat}x , {time_str}")
log.append((size, t0))
return log
def profile_brute_force_contains_all_points(repeat: int):
log = []
for size in range(100, 2000, 100):
points = random_points(size, 50.0)
name = f"Brute Force({size})"
t0 = profile(profile_brute_force_contains_points, repeat, points)
time_str = f"{t0:6.2f}s"
print(f"{name} contains all points, {repeat}x , {time_str}")
log.append((size, t0))
return log
def profile_brute_force_nearest_neighbor(repeat: int):
log = []
for size in range(100, 2000, 100):
points = random_points(size, 50.0)
name = f"Brute Force({size})"
search_points = random_points(100, 50.0)
t0 = profile(profile_brute_force_closest_point, repeat, points, search_points)
time_str = f"{t0:6.2f}s"
print(f"{name} contains all points, {repeat}x , {time_str}")
log.append((size, t0))
return log
def show_log(log, name: str):
if plt is None:
return
x = []
y = []
for size, t0 in log:
x.append(size)
y.append(t0)
fig, ax = plt.subplots()
ax.plot(x, y)
ax.set(
xlabel="Size",
ylabel="Time",
title=name,
)
ax.grid()
plt.show()
PROFILE_RTREE_BUILD = True
PROFILE_RTREE_CONTAINS = True
PROFILE_RTREE_NEIGHBOR = True
PROFILE_BRUTE_FORCE_CONTAINS = True
PROFILE_BRUTE_FORCE_NEIGHBOR = True
if __name__ == "__main__":
max_size = 5
if PROFILE_RTREE_BUILD:
log = profile_rtree_building(10, max_size)
if plt:
show_log(log, f"Build Random RTree, max node size={max_size}")
if PROFILE_RTREE_CONTAINS:
log = profile_rtree_contains_all_points(10, max_size)
if plt:
show_log(
log,
f"Random RTree contains all points, max node size={max_size}",
)
if PROFILE_BRUTE_FORCE_CONTAINS:
log = profile_brute_force_contains_all_points(10)
if plt:
show_log(log, f"Brute force contains all points")
if PROFILE_RTREE_NEIGHBOR:
log = profile_rtree_nearest_neighbor(10, max_size)
if plt:
show_log(log, f"Random RTree nearest neighbor, max node size={max_size}")
if PROFILE_BRUTE_FORCE_NEIGHBOR:
log = profile_brute_force_nearest_neighbor(10)
if plt:
show_log(log, f"Brute force nearest neighbor")
|
