-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathTrapezoid.py
169 lines (147 loc) · 6.18 KB
/
Trapezoid.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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
from Point import Point
from LineSegment import LineSegment
from GraphObject import GraphObject
import DAGNode as dag
# from llist import dllistnode
class Trapezoid(GraphObject):
"""
Class representing a trapezoid with top, bottom, left_p and right_p
(2 line segments and 2 endpoints respectively)
"""
def __init__(self, left_p, right_p, top, bottom):
super().__init__()
assert isinstance(left_p, Point) and isinstance(right_p, Point), 'left_p and/or right_p is not a point'
assert isinstance(top, LineSegment) and isinstance(bottom,
LineSegment), 'top and/or bottom is not a line segment'
self.left_p = left_p
self.right_p = right_p
self.top = top
self.bottom = bottom
self.left_neighbors = set()
self.right_neighbors = set()
self._node = dag.DAGNode(self)
# self._dllistnode = dllistnode(self)
@property
def node(self):
return self._node
@node.setter
def node(self, node):
self._node.modify(node)
@property
def is_zero_width(self):
return self.left_p.x == self.right_p.x
def setLeftNeighbors(self, neighbors, auto=False):
assert isinstance(neighbors, set) and all(isinstance(n, Trapezoid) for n in neighbors)
# there are no left neighbors
if not neighbors or self.top.p == self.bottom.p:
return
if self.is_zero_width:
""" zero-width trapezoid """
y_high = self.left_p.y
y_low = self.right_p.y
elif self.left_p == self.top.p:
l = self.bottom
y_high = self.left_p.y
y_low = l.slope * self.left_p.x + l.intercept
elif self.left_p == self.bottom.p:
l = self.top
y_high = l.slope * self.left_p.x + l.intercept
y_low = self.left_p.y
else:
l = self.bottom
y_low = l.slope * self.left_p.x + l.intercept
l = self.top
y_high = l.slope * self.left_p.x + l.intercept
for n in neighbors:
# if the neighbor already exists or its not directly adjacent to self, then skip
if n in self.left_neighbors or self.left_p.x != n.right_p.x:
continue
if n.is_zero_width:
""" zero-width trapezoid """
ny_high = n.left_p.y
ny_low = n.right_p.y
elif n.right_p == n.top.q:
l = n.bottom
ny_high = n.right_p.y
ny_low = l.slope * n.right_p.x + l.intercept
elif n.right_p == n.bottom.q:
l = n.top
ny_high = l.slope * n.right_p.x + l.intercept
ny_low = n.right_p.y
else:
l = n.bottom
ny_low = l.slope * n.right_p.x + l.intercept
l = n.top
ny_high = l.slope * n.right_p.x + l.intercept
# sides overlap
if ny_low < y_high < ny_high or ny_low < y_low < ny_high \
or y_low < ny_low < y_high or y_low < ny_high < y_high \
or (y_low == ny_low and y_high == ny_high):
self.left_neighbors.add(n)
if not auto:
n.setRightNeighbors({self}, auto=True)
def setRightNeighbors(self, neighbors, auto=False):
assert isinstance(neighbors, set) and all(isinstance(n, Trapezoid) for n in neighbors)
# there are no right neighbors
if not neighbors or self.top.q == self.bottom.q:
return
if self.is_zero_width:
y_high = self.left_p.y
y_low = self.right_p.y
elif self.right_p == self.top.q:
l = self.bottom
y_high = self.right_p.y
y_low = l.slope * self.right_p.x + l.intercept
elif self.right_p == self.bottom.q:
l = self.top
y_high = l.slope * self.right_p.x + l.intercept
y_low = self.right_p.y
else:
l = self.bottom
y_low = l.slope * self.right_p.x + l.intercept
l = self.top
y_high = l.slope * self.right_p.x + l.intercept
for n in neighbors:
# if the neighbor already exists or its not directly adjacent to self, then skip
if n in self.right_neighbors or self.right_p.x != n.left_p.x:
continue
if n.is_zero_width:
""" zero-width trapezoid """
ny_high = n.left_p.y
ny_low = n.right_p.y
elif n.left_p == n.top.p:
l = n.bottom
ny_high = n.left_p.y
ny_low = l.slope * n.left_p.x + l.intercept
elif n.left_p == n.bottom.p:
l = n.top
ny_high = l.slope * n.left_p.x + l.intercept
ny_low = n.left_p.y
else:
l = n.bottom
ny_low = l.slope * n.left_p.x + l.intercept
l = n.top
ny_high = l.slope * n.left_p.x + l.intercept
# sides overlap
if ny_low < y_high < ny_high or ny_low < y_low < ny_high \
or y_low < ny_low < y_high or y_low < ny_high < y_high \
or (y_low == ny_low and y_high == ny_high):
self.right_neighbors.add(n)
if not auto:
n.setLeftNeighbors({self})
def __hash__(self):
return super().__hash__()
def __eq__(self, other):
"""Override the default Equals behavior"""
if isinstance(other, self.__class__):
return self.left_p == other.left_p and self.right_p == other.right_p \
and self.top == other.top and self.bottom == other.bottom
return super().__eq__(other)
def __ne__(self, other):
"""Define a non-equality test"""
if isinstance(other, self.__class__):
return not self == other
return NotImplemented
def __repr__(self):
return '<Trapezoid left_p:%s right_p:%s top:%s bottom:%s>' % (str(self.left_p), str(self.right_p),
str(self.top), str(self.bottom))