-
-
Notifications
You must be signed in to change notification settings - Fork 20
/
line_geometry.py
146 lines (123 loc) · 4.38 KB
/
line_geometry.py
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
def create_points(non_intersecting=True):
background(200)
done = False
while not done:
poly_points = [PVector(random(BORDER, width - BORDER),
random(BORDER, height - BORDER)
)
for _ in range(NUM)]
ed = edges(poly_points)
done = True
if non_intersecting:
for p1, p2 in ed[::-1]:
for p3, p4 in ed[2::]:
# test only non consecutive edges
if (p1 != p3) and (p2 != p3) and (p1 != p4):
if line_instersect(Line(p1, p2), Line(p3, p4)):
done = False
break
return poly_points
def is_inside(x, y, poly_points):
min_, max_ = min_max(poly_points)
if x < min_.x or y < min_.y or x > max_.x or y > max_.y:
return False
a = PVector(x, min_.y)
b = PVector(x, max_.y)
v_lines = inter_lines(Line(a, b), poly_points)
if not v_lines:
return False
a = PVector(min_.x, y)
b = PVector(max_.x, y)
h_lines = inter_lines(Line(a, b), poly_points)
if not h_lines:
return False
for v in v_lines:
for h in h_lines:
if line_instersect(v, h):
return True
return False
def inter_lines(L, poly_points):
inter_points = []
for p1, p2 in edges(poly_points):
inter = line_instersect(Line(p1, p2), L)
if inter:
inter_points.append(inter)
if not inter_points:
return []
inter_lines = []
if len(inter_points) > 1:
inter_points.sort()
pairs = zip(inter_points[::2], inter_points[1::2])
for p1, p2 in pairs:
if p2:
inter_lines.append(Line(PVector(p1.x, p1.y),
PVector(p2.x, p2.y)))
return inter_lines
class Line():
""" I should change this to a named tuple... """
def __init__(self, p1, p2):
self.p1 = p1
self.p2 = p2
def plot(self):
line(self.p1.x, self.p1.y, self.p2.x, self.p2.y)
def lerp(self, other, t):
p1 = PVector.lerp(self.p1, other.p1, t)
p2 = PVector.lerp(self.p2, other.p2, t)
return Line(p1, p2)
def line_instersect(line_a, line_b):
"""
code adapted from Bernardo Fontes
https://github.com/berinhard/sketches/
"""
x1, y1 = line_a.p1.x, line_a.p1.y
x2, y2 = line_a.p2.x, line_a.p2.y
x3, y3 = line_b.p1.x, line_b.p1.y
x4, y4 = line_b.p2.x, line_b.p2.y
try:
uA = ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));
uB = ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));
except ZeroDivisionError:
return
if not(0 <= uA <= 1 and 0 <= uB <= 1):
return
x = line_a.p1.x + uA * (line_a.p2.x - line_a.p1.x)
y = line_a.p1.y + uA * (line_a.p2.y - line_a.p1.y)
return PVector(x, y)
def edges(poly_points):
return pairwise(poly_points) + [(poly_points[-1], poly_points[0])]
def pairwise(iterable):
import itertools
"s -> (s0,s1), (s1,s2), (s2, s3), ..."
a, b = itertools.tee(iterable)
next(b, None)
return zip(a, b)
def min_max(points):
points = iter(points)
try:
p = points.next()
min_x, min_y = max_x, max_y = p.x, p.y
except StopIteration:
raise ValueError, "min_max requires at least one point"
for p in points:
if p.x < min_x:
min_x = p.x
elif p.x > max_x:
max_x = p.x
if p.y < min_y:
min_y = p.y
elif p.y > max_y:
max_y = p.y
return (PVector(min_x, min_y),
PVector(max_x, max_y))
def par_hatch(points, divisions, *sides):
vectors = [PVector(p.x, p.y) for p in points]
lines = []
if not sides: sides = [0]
for s in sides:
a, b = vectors[-1 + s], vectors[+0 + s]
d, c = vectors[-2 + s], vectors[-3 + s]
for i in range(1, divisions):
s0 = PVector.lerp(a, b, i/float(divisions))
s1 = PVector.lerp(d, c, i/float(divisions))
lines.append(Line(s0, s1))
return lines