-
Notifications
You must be signed in to change notification settings - Fork 1
/
LineSweep.py
320 lines (267 loc) · 13 KB
/
LineSweep.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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
from Polygon import Polygon, Point, LineSegment
from TrapezoidMap import TrapezoidMap, Trapezoid
from bintrees import AVLTree
class LineSweep:
def __init__(self, polygon):
assert isinstance(polygon, Polygon)
self.polygon = polygon
# the event structure
self.Q = []
# the status structure
self.S = AVLTree()
self.lineSweep()
def getTrapezoidalMap(self) -> TrapezoidMap:
return self.T
"""
Run the line sweep
"""
def lineSweep(self):
self.T = TrapezoidMap([])
# keeps track of edges that should be removed from S later on
self.clearBuffer = False
self.buffer = []
# first initialize the event structure
self.initEventStructure()
# now compute the bounding box
self.computeBoundingBox()
# now loop over the event points
for event in self.Q:
self.handleEventPoint(event)
# check if the buffer needs to be cleared
if (self.clearBuffer):
self.emptyBuffer()
# now just add the last trapezoid
self.T.addTrapezoid([Trapezoid(self.Q[-3][0], self.Q[-1][0], self.Q[-1][2], self.Q[-2][2])])
def handleEventPoint(self, event):
# if the event contains a point on the bounding box
if event[1] == "G":
if event[0] == event[2].p:
self.handleStartPoint(event[0], event[2], event[1])
else:
self.handleEndPoint(event[0], event[2], event[1])
else:
if event[0] == event[2].p:
self.handleStartPoint(event[0], event[2], event[1], event[3])
elif event[0] == event[2].q:
self.handleEndPoint(event[0], event[2], event[1], event[3])
else:
raise ValueError("point is not part of the linesegment")
if event[0] == event[3].p:
self.handleStartPoint(event[0], event[3], event[1], event[2])
elif event[0] == event[3].q:
self.handleEndPoint(event[0], event[3], event[1], event[2])
else:
raise ValueError("point is not part of the linesegment")
# removes all edges from the status that are in the buffer
def emptyBuffer(self):
for edge in self.buffer:
self.S.remove(edge)
self.buffer.clear()
self.clearBuffer = False
def handleStartPoint(self, point, linesegment, case=None, otherline=None):
assert isinstance(point, Point)
assert isinstance(linesegment, LineSegment)
# insert the segment into the status
if (not linesegment.isVertical):
self.S.insert(linesegment, linesegment)
pred = self.getPred(linesegment)
succ = self.getSucc(linesegment)
if case == "A":
pass
elif case == "B":
# first check the pred and succ of the current line
if pred == otherline:
# get a new predecessor
pred = self.getPred(otherline)
if succ == otherline:
# get a new successor
succ = self.getSucc(otherline)
# make trapezoids with pred and/or succ
if pred.p.x < succ.p.x:
self.T.addTrapezoid([Trapezoid(succ.p, point, succ, pred)])
else:
self.T.addTrapezoid([Trapezoid(pred.p, point, succ, pred)])
elif case == "C":
raise ValueError("This should not happen!")
elif case == "D":
pass
# TODO: is this really required?
elif case == "E":
raise ValueError("This should not happen!")
elif case == "F":
# we simply ignore this case
pass
else:
# the event point is on the bounding box
pass
def handleEndPoint(self, point, linesegment, case, otherline=None):
assert isinstance(point, Point)
assert isinstance(linesegment, LineSegment)
donotremove = False
if not linesegment.isVertical:
pred = self.getPred(linesegment)
succ = self.getSucc(linesegment)
if case == "A":
# make a trapezoid with the current linesegment
if pred.p.x <= linesegment.p.x:
self.T.addTrapezoid([Trapezoid(linesegment.p, linesegment.q, linesegment, pred)])
elif pred.p.x > linesegment.p.x and pred.p.x < linesegment.q.x:
self.T.addTrapezoid([Trapezoid(pred.p, linesegment.q, linesegment, pred)])
else:
# in this case we do not know bottom so do nothing
pass
# also consider successor
if succ.p.x <= linesegment.p.x:
self.T.addTrapezoid([Trapezoid(linesegment.p, linesegment.q, succ, linesegment)])
elif pred.p.x > linesegment.p.x and pred.p.x < linesegment.q.x:
self.T.addTrapezoid([Trapezoid(succ.p, linesegment.q, succ, linesegment)])
else:
# in this case we do not know bottom so do nothing
pass
elif case == "B":
raise ValueError("this should not be possible!")
elif case == "C":
# special case: keep getting predecessors until this does not hold anymore
while succ.p.x == point.x:
succ = self.getSucc(succ)
# special case: keep getting predecessors until this does not hold anymore
while pred.p.x == point.x:
pred = self.getPred(pred)
if (linesegment > otherline):
# the current line is the top line
# make a trapezoid to the left
if succ.p.x <= linesegment.p.x:
self.T.addTrapezoid([Trapezoid(linesegment.p, point, succ, linesegment)])
elif succ.p.x > linesegment.p.x and succ.p.x < linesegment.q.x:
self.T.addTrapezoid([Trapezoid(succ.p, point, succ, linesegment)])
if (linesegment < otherline):
# the current line is the bottom one
# make a trapezoid to the left
if pred.p.x <= linesegment.p.x:
self.T.addTrapezoid([Trapezoid(linesegment.p, point, linesegment, pred)])
elif pred.p.x > linesegment.p.x and succ.p.x < linesegment.q.x:
self.T.addTrapezoid([Trapezoid(pred.p, point, linesegment, pred)])
elif case == "D":
raise ValueError("This should not happen")
elif case == "E":
# special case: keep getting predecessors until this does not hold anymore
while pred.p.x == point.x:
pred = self.getPred(pred)
# line segment is the nonvertical one, we check if linesegment is connected to the bottom of the vertical edge
if (linesegment.aboveLine(otherline.q) and linesegment.aboveLine(otherline.p)):
self.buffer.append(linesegment)
donotremove = True
if succ.p.x <= linesegment.p.x:
self.T.addTrapezoid([Trapezoid(linesegment.p, linesegment.q, succ, linesegment)])
elif succ.p.x > linesegment.p.x and succ.p.x < linesegment.q.x:
self.T.addTrapezoid([Trapezoid(succ.p, linesegment.q, succ, linesegment)])
if pred.p.x <= linesegment.p.x:
self.T.addTrapezoid([Trapezoid(linesegment.p, linesegment.q, linesegment, pred)])
elif pred.p.x > linesegment.p.x and succ.p.x < linesegment.q.x:
self.T.addTrapezoid([Trapezoid(pred.p, linesegment.q, linesegment, pred)])
elif case == "F":
# we simply ignore this case
pass
else:
# the event point is on the bounding box
pass
# only if there are no edges in the buffer, remove the edge
if not donotremove:
# remove the linesegment from the status
self.S.remove(linesegment)
elif linesegment.isVertical:
# we wish to clear the buffer after this event point
self.clearBuffer = True
def getPred(self, linesegment) -> LineSegment:
assert (isinstance(linesegment, LineSegment))
try:
return self.S.prev_key(linesegment)
except KeyError:
return None
def getSucc(self, linesegment) -> LineSegment:
assert (isinstance(linesegment, LineSegment))
try:
return self.S.succ_key(linesegment)
except KeyError:
return None
def initEventStructure(self):
# the edge between the first and last point
lastEdge = LineSegment(self.polygon.V[0], self.polygon.V[-1])
# if points have the same x, the point with lowest y goes first
for i in range(len(self.polygon.V)):
eventPoint = []
eventPoint.append(self.polygon.V[i])
# the current point is not the first or last one
if i != 0:
# the edge between the current point and the previous one
eventPoint.append(LineSegment(self.polygon.V[i], self.polygon.V[i - 1]))
else:
eventPoint.append(lastEdge)
if i != (len(self.polygon.V) - 1):
# the edge between the current point and the next one
eventPoint.append(LineSegment(self.polygon.V[i], self.polygon.V[i + 1]))
else:
eventPoint.append(lastEdge)
# now also "sort" the edges of an event such that the edge where the point is the endpoint is done first
# if the point equals the endpoint (q) of the first edge, we are fine
if eventPoint[1].q == eventPoint[0]:
pass
elif eventPoint[2].q == eventPoint[0]:
# in this case we must swap eventPoint[1] and eventPoint[2]
eventPoint[1], eventPoint[2] = eventPoint[2], eventPoint[1]
# now we wish to determine the "case" we have here
eventPoint.insert(1, self.determineCase(eventPoint[0], eventPoint[1], eventPoint[2]))
self.Q.append(eventPoint)
self.Q.sort(key=lambda event: (event[0].x, event[0].y))
# given a point and two lines connected to this point, determine the configuration they are in
def determineCase(self, point, l1, l2):
assert (isinstance(point, Point))
assert (isinstance(l1, LineSegment))
assert (isinstance(l2, LineSegment))
if l1.isVertical and not l2.isVertical:
if l2.p == l1.p or l2.p == l1.q:
return "D"
elif l2.q == l1.p or l2.q == l1.q:
return "E"
elif l2.isVertical and not l1.isVertical:
if l1.p == l2.p or l1.p == l2.q:
return "D"
elif l1.q == l2.p or l1.q == l2.q:
return "E"
elif l1.isVertical and l2.isVertical:
return "F"
elif point == l1.p and point == l2.p:
return "B"
elif point == l1.q and point == l2.q:
return "C"
elif point == l1.q and point == l2.p:
return "A"
else:
raise ValueError("Case not defined")
def computeBoundingBox(self):
# find top right point to create a bounding box (bottom left is [0, 0])
topRight = Point(0, 0)
bottomLeft = Point(float("inf"), float("inf"))
for point in self.polygon.V:
# find top right
if point.get_x() >= topRight.get_x():
topRight.set_x(point.get_x() + 1)
if point.get_y() >= topRight.get_y():
topRight.set_y(point.get_y() + 1)
# find left bottom
if point.get_x() <= bottomLeft.get_x():
bottomLeft.set_x(point.get_x() - 1)
if point.get_y() <= bottomLeft.get_y():
bottomLeft.set_y(point.get_y() - 1)
# define bounding box edges
self.topEdge = LineSegment(Point(bottomLeft.x, topRight.y), Point(topRight.x, topRight.y))
self.bottomEdge = LineSegment(Point(bottomLeft.x, bottomLeft.y), Point(topRight.x, bottomLeft.y))
# based on the bounding box dimensions we add events to Q
# first insert the top left point of the bounding box since it should be the second event
self.Q.insert(0, [self.topEdge.p, "G", self.topEdge])
# then insert the bottom left point of the bounding box since it should be the first event
self.Q.insert(0, [self.bottomEdge.p, "G", self.bottomEdge])
# then append the bottom right point as it should be the second to last event
self.Q.append([self.bottomEdge.q, "G", self.bottomEdge])
# and finally append the top right point
self.Q.append([self.topEdge.q, "G", self.topEdge])