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
|
# Copyright (c) 2022, Manfred Moitzi
# License: MIT License
import random
import time
import pathlib
import ezdxf
from ezdxf.math import Vec2, convex_hull_2d, is_point_left_of_line
CWD = pathlib.Path("~/Desktop/Outbox").expanduser()
if not CWD.exists():
CWD = pathlib.Path(".")
SIZE = 100
ROUNDS = 2000
def old_convex_hull_2d(points):
"""Returns 2D convex hull for `points`.
Args:
points: iterable of points as :class:`Vec3` compatible objects,
z-axis is ignored
"""
def _convexhull(hull):
while len(hull) > 2:
# the last three points
start_point, check_point, destination_point = hull[-3:]
# curve not turns right
if not is_point_left_of_line(
check_point, start_point, destination_point
):
# remove the penultimate point
del hull[-2]
else:
break
return hull
points = sorted(set(Vec2.generate(points))) # remove duplicate points
if len(points) < 3:
raise ValueError(
"Convex hull calculation requires 3 or more unique points."
)
upper_hull = points[:2] # first two points
for next_point in points[2:]:
upper_hull.append(next_point)
upper_hull = _convexhull(upper_hull)
lower_hull = [points[-1], points[-2]] # last two points
for next_point in reversed(points[:-2]):
lower_hull.append(next_point)
lower_hull = _convexhull(lower_hull)
upper_hull.extend(lower_hull[1:-1])
return upper_hull
def random_points(n: int):
return [
Vec2(random.random() * SIZE, random.random() * SIZE) for _ in range(n)
]
def profile(func, points) -> float:
t0 = time.perf_counter()
for _ in range(ROUNDS):
func(points)
t1 = time.perf_counter()
return t1 - t0
def export_dxf(points):
doc = ezdxf.new()
msp = doc.modelspace()
for p in points:
msp.add_point(p, dxfattribs={"color": 1, "layer": "points"})
hull = old_convex_hull_2d(points)
msp.add_lwpolyline(hull, dxfattribs={"color": 2, "layer": "old_hull"})
hull = convex_hull_2d(points)
msp.add_lwpolyline(hull, dxfattribs={"color": 6, "layer": "new_hull"})
doc.saveas(CWD / "convexhull.dxf")
def main():
points = random_points(200)
old = profile(old_convex_hull_2d, points)
print(f"old convex hull function: {old:.3f}s")
new = profile(convex_hull_2d, points)
print(f"new convex hull function: {new:.3f}s")
print(f"ratio old/new: {old/new:.3f}")
export_dxf(points)
if __name__ == "__main__":
main()
|
