1#=============================================================================== 2# # 3# Author : Angus Johnson # 4# Version : 5.1.6(b) # 5# Date : 1 June 2013 # 6# Website : http://www.angusj.com # 7# Copyright : Angus Johnson 2010-2013 # 8# # 9# License: # 10# Use, modification & distribution is subject to Boost Software License Ver 1. # 11# http://www.boost.org/LICENSE_1_0.txt # 12# # 13# Attributions: # 14# The code in this library is an extension of Bala Vatti's clipping algorithm: # 15# "A generic solution to polygon clipping" # 16# Communications of the ACM, Vol 35, Issue 7 (July 1992) PP 56-63. # 17# http://portal.acm.org/citation.cfm?id=129906 # 18# # 19# Computer graphics and geometric modeling: implementation and algorithms # 20# By Max K. Agoston # 21# Springer; 1 edition (January 4, 2005) # 22# http://books.google.com/books?q=vatti+clipping+agoston # 23# # 24# See also: # 25# "Polygon Offsetting by Computing Winding Numbers" # 26# Paper no. DETC2005-85513 PP. 565-575 # 27# ASME 2005 International Design Engineering Technical Conferences # 28# and Computers and Information in Engineering Conference (IDETC/CIE2005) # 29# September 24-28, 2005 , Long Beach, California, USA # 30# http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf # 31# # 32#=============================================================================== 33 34import math 35from collections import namedtuple 36 37horizontal = float('-inf') 38 39class ClipType: (Intersection, Union, Difference, Xor) = range(4) 40class PolyType: (Subject, Clip) = range(2) 41class PolyFillType: (EvenOdd, NonZero, Positive, Negative) = range(4) 42class JoinType: (Square, Round, Miter) = range(3) 43class EndType: (Closed, Butt, Square, Round) = range(4) 44class EdgeSide: (Left, Right) = range(2) 45class Protects: (Neither, Left, Right, Both) = range(4) 46class Direction: (LeftToRight, RightToLeft) = range(2) 47 48Point = namedtuple('Point', 'x y') 49FloatPoint = namedtuple('FloatPoint', 'x y') 50Rect = namedtuple('FloatPoint', 'left top right bottom') 51 52class LocalMinima(object): 53 leftBound = rightBound = nextLm = None 54 def __init__(self, y, leftBound, rightBound): 55 self.y = y 56 self.leftBound = leftBound 57 self.rightBound = rightBound 58 59class Scanbeam(object): 60 __slots__ = ('y','nextSb') 61 def __init__(self, y, nextSb = None): 62 self.y = y 63 self.nextSb = nextSb 64 def __repr__(self): 65 s = 'None' 66 if self.nextSb is not None: s = '<obj>' 67 return "(y:%i, nextSb:%s)" % (self.y, s) 68 69class IntersectNode(object): 70 __slots__ = ('e1','e2','pt','nextIn') 71 def __init__(self, e1, e2, pt): 72 self.e1 = e1 73 self.e2 = e2 74 self.pt = pt 75 self.nextIn = None 76 77class OutPt(object): 78 __slots__ = ('idx','pt','prevOp','nextOp') 79 def __init__(self, idx, pt): 80 self.idx = idx 81 self.pt = pt 82 self.prevOp = None 83 self.nextOp = None 84 85class OutRec(object): 86 __slots__ = ('idx','bottomPt','isHole','FirstLeft', 'pts','PolyNode') 87 def __init__(self, idx): 88 self.idx = idx 89 self.bottomPt = None 90 self.isHole = False 91 self.FirstLeft = None 92 self.pts = None 93 self.PolyNode = None 94 95class JoinRec(object): 96 __slots__ = ('pt1a','pt1b','poly1Idx','pt2a', 'pt2b','poly2Idx') 97 98class HorzJoin(object): 99 edge = None 100 savedIdx = 0 101 prevHj = None 102 nextHj = None 103 def __init__(self, edge, idx): 104 self.edge = edge 105 self.savedIdx = idx 106 107#=============================================================================== 108# Unit global functions ... 109#=============================================================================== 110def IntsToPoints(ints): 111 result = [] 112 for i in range(0, len(ints), 2): 113 result.append(Point(ints[i], ints[i+1])) 114 return result 115 116def Area(polygon): 117 # see http://www.mathopenref.com/coordpolygonarea2.html 118 highI = len(polygon) - 1 119 A = (polygon[highI].x + polygon[0].x) * (polygon[0].y - polygon[highI].y) 120 for i in range(highI): 121 A += (polygon[i].x + polygon[i+1].x) * (polygon[i+1].y - polygon[i].y) 122 return float(A) / 2 123 124def Orientation(polygon): 125 return Area(polygon) > 0.0 126 127#=============================================================================== 128# PolyNode & PolyTree classes (+ ancilliary functions) 129#=============================================================================== 130class PolyNode(object): 131 """Node of PolyTree""" 132 133 def __init__(self): 134 self.Contour = [] 135 self.Childs = [] 136 self.Parent = None 137 self.Index = 0 138 self.ChildCount = 0 139 140 def IsHole(self): 141 result = True 142 while (self.Parent is not None): 143 result = not result 144 self.Parent = self.Parent.Parent 145 return result 146 147 def GetNext(self): 148 if (self.ChildCount > 0): 149 return self.Childs[0] 150 else: 151 return self._GetNextSiblingUp() 152 153 def _AddChild(self, node): 154 self.Childs.append(node) 155 node.Index = self.ChildCount 156 node.Parent = self 157 self.ChildCount += 1 158 159 def _GetNextSiblingUp(self): 160 if (self.Parent is None): 161 return None 162 elif (self.Index == self.Parent.ChildCount - 1): 163 return self.Parent._GetNextSiblingUp() 164 else: 165 return self.Parent.Childs[self.Index +1] 166 167class PolyTree(PolyNode): 168 """Container for PolyNodes""" 169 170 def __init__(self): 171 PolyNode.__init__(self) 172 self._AllNodes = [] 173 174 def Clear(self): 175 self._AllNodes = [] 176 self.Childs = [] 177 self.ChildCount = 0 178 179 def GetFirst(self): 180 if (self.ChildCount > 0): 181 return self.Childs[0] 182 else: 183 return None 184 185 def Total(self): 186 return len(self._AllNodes) 187 188def _AddPolyNodeToPolygons(polynode, polygons): 189 """Internal function for PolyTreeToPolygons()""" 190 if (len(polynode.Contour) > 0): 191 polygons.append(polynode.Contour) 192 for i in range(polynode.ChildCount): 193 _AddPolyNodeToPolygons(polynode.Childs[i], polygons) 194 195def PolyTreeToPolygons(polyTree): 196 result = [] 197 _AddPolyNodeToPolygons(polyTree, result) 198 return result 199 200#=============================================================================== 201# Edge class 202#=============================================================================== 203 204class Edge(object): 205 206 def __init__(self): 207 self.Bot = Point(0,0) 208 self.Curr = Point(0,0) 209 self.Top = Point(0,0) 210 self.Delta = Point(0,0) 211 self.dx = float(0.0) 212 self.polyType = PolyType.Subject 213 self.side = EdgeSide.Left 214 self.windDelta, self.windCnt, self.windCnt2 = 0, 0, 0 215 self.outIdx = -1 216 self.nextE, self.prevE, self.nextInLML = None, None, None 217 self.prevInAEL, self.nextInAEL, self.prevInSEL, self.nextInSEL = None, None, None, None 218 219 def __repr__(self): 220 return "(%i,%i . %i,%i {dx:%0.2f} %i {%x})" % \ 221 (self.Bot.x, self.Bot.y, self.Top.x, self.Top.y, self.dx, self.outIdx, id(self)) 222 223#=============================================================================== 224# ClipperBase class (+ data structs & ancilliary functions) 225#=============================================================================== 226 227def _PointsEqual(pt1, pt2): 228 return (pt1.x == pt2.x) and (pt1.y == pt2.y) 229 230def _SlopesEqual(pt1, pt2, pt3, pt4 = None): 231 if pt4 is None: 232 return (pt1.y-pt2.y)*(pt2.x-pt3.x) == (pt1.x-pt2.x)*(pt2.y-pt3.y) 233 else: 234 return (pt1.y-pt2.y)*(pt3.x-pt4.x) == (pt1.x-pt2.x)*(pt3.y-pt4.y) 235 236def _SlopesEqual2(e1, e2): 237 return e1.Delta.y * e2.Delta.x == e1.Delta.x * e2.Delta.y 238 239def _SetDx(e): 240 e.Delta = Point(e.Top.x - e.Bot.x, e.Top.y - e.Bot.y) 241 if e.Delta.y == 0: e.dx = horizontal 242 else: e.dx = float(e.Delta.x)/float(e.Delta.y) 243 244def _SwapSides(e1, e2): 245 side = e1.side 246 e1.side = e2.side 247 e2.side = side 248 249def _SwapPolyIndexes(e1, e2): 250 idx = e1.outIdx 251 e1.outIdx = e2.outIdx 252 e2.outIdx = idx 253 254def _InitEdge(e, eNext, ePrev, pt, polyType): 255 e.nextE = eNext 256 e.prevE = ePrev 257 e.Curr = pt 258 if e.Curr.y >= e.nextE.Curr.y: 259 e.Bot = e.Curr 260 e.Top = e.nextE.Curr 261 e.windDelta = 1 262 else: 263 e.Top = e.Curr 264 e.Bot = e.nextE.Curr 265 e.windDelta = -1 266 _SetDx(e) 267 e.outIdx = -1 268 e.PolyType = polyType 269 270def _SwapX(e): 271 e.Curr = Point(e.Top.x, e.Curr.y) 272 e.Top = Point(e.Bot.x, e.Top.y) 273 e.Bot = Point(e.Curr.x, e.Bot.y) 274 275class ClipperBase(object): 276 277 def __init__(self): 278 self._EdgeList = [] # 2D array 279 self._LocalMinList = None # single-linked list of LocalMinima 280 self._CurrentLocMin = None 281 282 def _InsertLocalMinima(self, lm): 283 if self._LocalMinList is None: 284 self._LocalMinList = lm 285 elif lm.y >= self._LocalMinList.y: 286 lm.nextLm = self._LocalMinList 287 self._LocalMinList = lm 288 else: 289 tmp = self._LocalMinList 290 while tmp.nextLm is not None and lm.y < tmp.nextLm.y: 291 tmp = tmp.nextLm 292 lm.nextLm = tmp.nextLm 293 tmp.nextLm = lm 294 295 def _AddBoundsToLML(self, e): 296 e.nextInLML = None 297 e = e.nextE 298 while True: 299 if e.dx == horizontal: 300 if (e.nextE.Top.y < e.Top.y) and (e.nextE.Bot.x > e.prevE.Bot.x): break 301 if (e.Top.x != e.prevE.Bot.x): _SwapX(e) 302 e.nextInLML = e.prevE 303 elif e.Bot.y == e.prevE.Bot.y: break 304 else: e.nextInLML = e.prevE 305 e = e.nextE 306 307 if e.dx == horizontal: 308 if (e.Bot.x != e.prevE.Bot.x): _SwapX(e) 309 lm = LocalMinima(e.prevE.Bot.y, e.prevE, e) 310 elif (e.dx < e.prevE.dx): 311 lm = LocalMinima(e.prevE.Bot.y, e.prevE, e) 312 else: 313 lm = LocalMinima(e.prevE.Bot.y, e, e.prevE) 314 lm.leftBound.side = EdgeSide.Left 315 lm.rightBound.side = EdgeSide.Right 316 self._InsertLocalMinima(lm) 317 while True: 318 if e.nextE.Top.y == e.Top.y and e.nextE.dx != horizontal: break 319 e.nextInLML = e.nextE 320 e = e.nextE 321 if e.dx == horizontal and e.Bot.x != e.prevE.Top.x: _SwapX(e) 322 return e.nextE 323 324 def _Reset(self): 325 lm = self._LocalMinList 326 if lm is not None: self._CurrentLocMin = lm 327 while lm is not None: 328 e = lm.leftBound 329 while e is not None: 330 e.Curr = e.Bot 331 e.side = EdgeSide.Left 332 e.outIdx = -1 333 e = e.nextInLML 334 e = lm.rightBound 335 while e is not None: 336 e.Curr = e.Bot 337 e.side = EdgeSide.Right 338 e.outIdx = -1 339 e = e.nextInLML 340 lm = lm.nextLm 341 342 def AddPolygon(self, polygon, polyType): 343 ln = len(polygon) 344 if ln < 3: return False 345 pg = polygon[:] 346 j = 0 347 # remove duplicate points and co-linear points 348 for i in range(1, len(polygon)): 349 if _PointsEqual(pg[j], polygon[i]): 350 continue 351 elif (j > 0) and _SlopesEqual(pg[j-1], pg[j], polygon[i]): 352 if _PointsEqual(pg[j-1], polygon[i]): j -= 1 353 else: j += 1 354 pg[j] = polygon[i] 355 if (j < 2): return False 356 # remove duplicate points and co-linear edges at the loop around 357 # of the start and end coordinates ... 358 ln = j +1 359 while (ln > 2): 360 if _PointsEqual(pg[j], pg[0]): j -= 1 361 elif _PointsEqual(pg[0], pg[1]) or _SlopesEqual(pg[j], pg[0], pg[1]): 362 pg[0] = pg[j] 363 j -= 1 364 elif _SlopesEqual(pg[j-1], pg[j], pg[0]): j -= 1 365 elif _SlopesEqual(pg[0], pg[1], pg[2]): 366 for i in range(2, j +1): pg[i-1] = pg[i] 367 j -= 1 368 else: break 369 ln -= 1 370 if ln < 3: return False 371 edges = [] 372 for i in range(ln): 373 edges.append(Edge()) 374 edges[0].Curr = pg[0] 375 _InitEdge(edges[ln-1], edges[0], edges[ln-2], pg[ln-1], polyType) 376 for i in range(ln-2, 0, -1): 377 _InitEdge(edges[i], edges[i+1], edges[i-1], pg[i], polyType) 378 _InitEdge(edges[0], edges[1], edges[ln-1], pg[0], polyType) 379 e = edges[0] 380 eHighest = e 381 while True: 382 e.Curr = e.Bot 383 if e.Top.y < eHighest.Top.y: eHighest = e 384 e = e.nextE 385 if e == edges[0]: break 386 # make sure eHighest is positioned so the following loop works safely ... 387 if eHighest.windDelta > 0: eHighest = eHighest.nextE 388 if eHighest.dx == horizontal: eHighest = eHighest.nextE 389 # finally insert each local minima ... 390 e = eHighest 391 while True: 392 e = self._AddBoundsToLML(e) 393 if e == eHighest: break 394 self._EdgeList.append(edges) 395 396 def AddPolygons(self, polygons, polyType): 397 result = False 398 for p in polygons: 399 if self.AddPolygon(p, polyType): result = True 400 return result 401 402 def Clear(self): 403 self._EdgeList = [] 404 self._LocalMinList = None 405 self._CurrentLocMin = None 406 407 def _PopLocalMinima(self): 408 if self._CurrentLocMin is not None: 409 self._CurrentLocMin = self._CurrentLocMin.nextLm 410 411#=============================================================================== 412# Clipper class (+ data structs & ancilliary functions) 413#=============================================================================== 414def _IntersectPoint(edge1, edge2): 415 if _SlopesEqual2(edge1, edge2): 416 if (edge2.Bot.y > edge1.Bot.y): y = edge2.Bot.y 417 else: y = edge1.Bot.y 418 return Point(0, y), False 419 if edge1.dx == 0: 420 x = edge1.Bot.x 421 if edge2.dx == horizontal: 422 y = edge2.Bot.y 423 else: 424 b2 = edge2.Bot.y - float(edge2.Bot.x)/edge2.dx 425 y = round(float(x)/edge2.dx + b2) 426 elif edge2.dx == 0: 427 x = edge2.Bot.x 428 if edge1.dx == horizontal: 429 y = edge1.Bot.y 430 else: 431 b1 = edge1.Bot.y - float(edge1.Bot.x)/edge1.dx 432 y = round(float(x)/edge1.dx + b1) 433 else: 434 b1 = float(edge1.Bot.x) - float(edge1.Bot.y) * edge1.dx 435 b2 = float(edge2.Bot.x) - float(edge2.Bot.y) * edge2.dx 436 m = (b2-b1)/(edge1.dx - edge2.dx) 437 y = round(m) 438 if math.fabs(edge1.dx) < math.fabs(edge2.dx): 439 x = round(edge1.dx * m + b1) 440 else: 441 x = round(edge2.dx * m + b2) 442 if (y < edge1.Top.y) or (y < edge2.Top.y): 443 if (edge1.Top.y > edge2.Top.y): 444 return edge1.Top, _TopX(edge2, edge1.Top.y) < edge1.Top.x 445 else: 446 return edge2.Top, _TopX(edge1, edge2.Top.y) > edge2.Top.x 447 else: 448 return Point(x,y), True 449 450def _TopX(e, currentY): 451 if currentY == e.Top.y: return e.Top.x 452 elif e.Top.x == e.Bot.x: return e.Bot.x 453 else: return e.Bot.x + round(e.dx * float(currentY - e.Bot.y)) 454 455def _E2InsertsBeforeE1(e1,e2): 456 if (e2.Curr.x == e1.Curr.x): 457 if (e2.Top.y > e1.Top.y): 458 return e2.Top.x < _TopX(e1, e2.Top.y) 459 return e1.Top.x > _TopX(e2, e1.Top.y) 460 else: 461 return e2.Curr.x < e1.Curr.x 462 463def _IsMinima(e): 464 return e is not None and e.prevE.nextInLML != e and e.nextE.nextInLML != e 465 466def _IsMaxima(e, y): 467 return e is not None and e.Top.y == y and e.nextInLML is None 468 469def _IsIntermediate(e, y): 470 return e.Top.y == y and e.nextInLML is not None 471 472def _GetMaximaPair(e): 473 if not _IsMaxima(e.nextE, e.Top.y) or e.nextE.Top.x != e.Top.x: 474 return e.prevE 475 else: 476 return e.nextE 477 478def _GetnextInAEL(e, direction): 479 if direction == Direction.LeftToRight: return e.nextInAEL 480 else: return e.prevInAEL 481 482def _ProtectLeft(val): 483 if val: return Protects.Both 484 else: return Protects.Right 485 486def _ProtectRight(val): 487 if val: return Protects.Both 488 else: return Protects.Left 489 490def _GetDx(pt1, pt2): 491 if (pt1.y == pt2.y): return horizontal 492 else: return float(pt2.x - pt1.x)/float(pt2.y - pt1.y) 493 494def _Param1RightOfParam2(outRec1, outRec2): 495 while outRec1 is not None: 496 outRec1 = outRec1.FirstLeft 497 if outRec1 == outRec2: return True 498 return False 499 500def _FirstParamIsbottomPt(btmPt1, btmPt2): 501 p = btmPt1.prevOp 502 while _PointsEqual(p.pt, btmPt1.pt) and (p != btmPt1): p = p.prevOp 503 dx1p = abs(_GetDx(btmPt1.pt, p.pt)) 504 p = btmPt1.nextOp 505 while _PointsEqual(p.pt, btmPt1.pt) and (p != btmPt1): p = p.nextOp 506 dx1n = abs(_GetDx(btmPt1.pt, p.pt)) 507 508 p = btmPt2.prevOp 509 while _PointsEqual(p.pt, btmPt2.pt) and (p != btmPt2): p = p.prevOp 510 dx2p = abs(_GetDx(btmPt2.pt, p.pt)) 511 p = btmPt2.nextOp 512 while _PointsEqual(p.pt, btmPt2.pt) and (p != btmPt2): p = p.nextOp 513 dx2n = abs(_GetDx(btmPt2.pt, p.pt)) 514 return (dx1p >= dx2p and dx1p >= dx2n) or (dx1n >= dx2p and dx1n >= dx2n) 515 516def _GetBottomPt(pp): 517 dups = None 518 p = pp.nextOp 519 while p != pp: 520 if p.pt.y > pp.pt.y: 521 pp = p 522 dups = None 523 elif p.pt.y == pp.pt.y and p.pt.x <= pp.pt.x: 524 if p.pt.x < pp.pt.x: 525 dups = None 526 pp = p 527 else: 528 if p.nextOp != pp and p.prevOp != pp: dups = p 529 p = p.nextOp 530 if dups is not None: 531 while dups != p: 532 if not _FirstParamIsbottomPt(p, dups): pp = dups 533 dups = dups.nextOp 534 while not _PointsEqual(dups.pt, pp.pt): dups = dups.nextOp 535 return pp 536 537def _GetLowermostRec(outRec1, outRec2): 538 if (outRec1.bottomPt is None): 539 outPt1 = _GetBottomPt(outRec1.pts) 540 else: outPt1 = outRec1.bottomPt 541 if (outRec2.bottomPt is None): 542 outPt2 = _GetBottomPt(outRec2.pts) 543 else: outPt2 = outRec2.bottomPt 544 if (outPt1.pt.y > outPt2.pt.y): return outRec1 545 elif (outPt1.pt.y < outPt2.pt.y): return outRec2 546 elif (outPt1.pt.x < outPt2.pt.x): return outRec1 547 elif (outPt1.pt.x > outPt2.pt.x): return outRec2 548 elif (outPt1.nextOp == outPt1): return outRec2 549 elif (outPt2.nextOp == outPt2): return outRec1 550 elif _FirstParamIsbottomPt(outPt1, outPt2): return outRec1 551 else: return outRec2 552 553def _SetHoleState(e, outRec, polyOutList): 554 isHole = False 555 e2 = e.prevInAEL 556 while e2 is not None: 557 if e2.outIdx >= 0: 558 isHole = not isHole 559 if outRec.FirstLeft is None: 560 outRec.FirstLeft = polyOutList[e2.outIdx] 561 e2 = e2.prevInAEL 562 outRec.isHole = isHole 563 564def _PointCount(pts): 565 if pts is None: return 0 566 p = pts 567 result = 0 568 while True: 569 result += 1 570 p = p.nextOp 571 if p == pts: break 572 return result 573 574def _PointIsVertex(pt, outPts): 575 op = outPts 576 while True: 577 if _PointsEqual(op.pt, pt): return True 578 op = op.nextOp 579 if op == outPts: break 580 return False 581 582def _ReversePolyPtLinks(pp): 583 if pp is None: return 584 pp1 = pp 585 while True: 586 pp2 = pp1.nextOp 587 pp1.nextOp = pp1.prevOp 588 pp1.prevOp = pp2; 589 pp1 = pp2 590 if pp1 == pp: break 591 592def _FixupOutPolygon(outRec): 593 lastOK = None 594 outRec.bottomPt = None 595 pp = outRec.pts 596 while True: 597 if pp.prevOp == pp or pp.nextOp == pp.prevOp: 598 outRec.pts = None 599 return 600 if _PointsEqual(pp.pt, pp.nextOp.pt) or \ 601 _SlopesEqual(pp.prevOp.pt, pp.pt, pp.nextOp.pt): 602 lastOK = None 603 pp.prevOp.nextOp = pp.nextOp 604 pp.nextOp.prevOp = pp.prevOp 605 pp = pp.prevOp 606 elif pp == lastOK: break 607 else: 608 if lastOK is None: lastOK = pp 609 pp = pp.nextOp 610 outRec.pts = pp 611 612def _FixHoleLinkage(outRec): 613 if outRec.FirstLeft is None or \ 614 (outRec.isHole != outRec.FirstLeft.isHole and \ 615 outRec.FirstLeft.pts is not None): return 616 orfl = outRec.FirstLeft 617 while orfl is not None and \ 618 (orfl.isHole == outRec.isHole or orfl.pts is None): 619 orfl = orfl.FirstLeft 620 outRec.FirstLeft = orfl 621 622def _GetOverlapSegment(pt1a, pt1b, pt2a, pt2b): 623 # precondition: segments are co-linear 624 if abs(pt1a.x - pt1b.x) > abs(pt1a.y - pt1b.y): 625 if pt1a.x > pt1b.x: tmp = pt1a; pt1a = pt1b; pt1b = tmp 626 if pt2a.x > pt2b.x: tmp = pt2a; pt2a = pt2b; pt2b = tmp 627 if (pt1a.x > pt2a.x): pt1 = pt1a 628 else: pt1 = pt2a 629 if (pt1b.x < pt2b.x): pt2 = pt1b 630 else: pt2 = pt2b 631 return pt1, pt2, pt1.x < pt2.x 632 else: 633 if pt1a.y < pt1b.y: tmp = pt1a; pt1a = pt1b; pt1b = tmp 634 if pt2a.y < pt2b.y: tmp = pt2a; pt2a = pt2b; pt2b = tmp 635 if (pt1a.y < pt2a.y): pt1 = pt1a 636 else: pt1 = pt2a 637 if (pt1b.y > pt2b.y): pt2 = pt1b 638 else: pt2 = pt2b 639 return pt1, pt2, pt1.y > pt2.y 640 641 642def _FindSegment(outPt, pt1, pt2): 643 if outPt is None: return outPt, pt1, pt2, False 644 pt1a = pt1; pt2a = pt2 645 outPt2 = outPt 646 while True: 647 if _SlopesEqual(pt1a, pt2a, outPt.pt, outPt.prevOp.pt) and _SlopesEqual(pt1a, pt2a, outPt.pt): 648 pt1, pt2, overlap = _GetOverlapSegment(pt1a, pt2a, outPt.pt, outPt.prevOp.pt) 649 if overlap: return outPt, pt1, pt2, True 650 outPt = outPt.nextOp 651 if outPt == outPt2: return outPt, pt1, pt2, False 652 653def _Pt3IsBetweenPt1AndPt2(pt1, pt2, pt3): 654 if _PointsEqual(pt1, pt3) or _PointsEqual(pt2, pt3): return True 655 elif pt1.x != pt2.x: return (pt1.x < pt3.x) == (pt3.x < pt2.x) 656 else: return (pt1.y < pt3.y) == (pt3.y < pt2.y) 657 658def _InsertPolyPtBetween(outPt1, outPt2, pt): 659 if outPt1 == outPt2: raise Exception("JoinError") 660 result = OutPt(outPt1.idx, pt) 661 if outPt2 == outPt1.nextOp: 662 outPt1.nextOp = result 663 outPt2.prevOp = result 664 result.nextOp = outPt2 665 result.prevOp = outPt1 666 else: 667 outPt2.nextOp = result 668 outPt1.prevOp = result 669 result.nextOp = outPt1 670 result.prevOp = outPt2 671 return result 672 673def _PointOnLineSegment(pt, linePt1, linePt2): 674 return ((pt.x == linePt1.x) and (pt.y == linePt1.y)) or \ 675 ((pt.x == linePt2.x) and (pt.y == linePt2.y)) or \ 676 (((pt.x > linePt1.x) == (pt.x < linePt2.x)) and \ 677 ((pt.y > linePt1.y) == (pt.y < linePt2.y)) and \ 678 ((pt.x - linePt1.x) * (linePt2.y - linePt1.y) == \ 679 (linePt2.x - linePt1.x) * (pt.y - linePt1.y))) 680 681def _PointOnPolygon(pt, pp): 682 pp2 = pp; 683 while True: 684 if (_PointOnLineSegment(pt, pp2.pt, pp2.nextOp.pt)): 685 return True 686 pp2 = pp2.nextOp 687 if (pp2 == pp): return False 688 689def _PointInPolygon(pt, outPt): 690 result = False 691 outPt2 = outPt 692 while True: 693 if ((((outPt2.pt.y <= pt.y) and (pt.y < outPt2.prevOp.pt.y)) or \ 694 ((outPt2.prevOp.pt.y <= pt.y) and (pt.y < outPt2.pt.y))) and \ 695 (pt.x < (outPt2.prevOp.pt.x - outPt2.pt.x) * (pt.y - outPt2.pt.y) / \ 696 (outPt2.prevOp.pt.y - outPt2.pt.y) + outPt2.pt.x)): result = not result 697 outPt2 = outPt2.nextOp 698 if outPt2 == outPt: break 699 700def _Poly2ContainsPoly1(outPt1, outPt2): 701 pt = outPt1 702 if (_PointOnPolygon(pt.pt, outPt2)): 703 pt = pt.nextOp 704 while (pt != outPt1 and _PointOnPolygon(pt.pt, outPt2)): 705 pt = pt.nextOp 706 if (pt == outPt1): return True 707 return _PointInPolygon(pt.pt, outPt2) 708 709def _EdgesAdjacent(inode): 710 return (inode.e1.nextInSEL == inode.e2) or \ 711 (inode.e1.prevInSEL == inode.e2) 712 713def _UpdateOutPtIdxs(outrec): 714 op = outrec.pts 715 while True: 716 op.idx = outrec.idx 717 op = op.prevOp 718 if (op == outrec.pts): break 719 720class Clipper(ClipperBase): 721 722 def __init__(self): 723 ClipperBase.__init__(self) 724 725 self.ReverseSolution = False 726 self.ForceSimple = False 727 728 self._PolyOutList = [] 729 self._ClipType = ClipType.Intersection 730 self._Scanbeam = None 731 self._ActiveEdges = None 732 self._SortedEdges = None 733 self._IntersectNodes = None 734 self._ClipFillType = PolyFillType.EvenOdd 735 self._SubjFillType = PolyFillType.EvenOdd 736 self._ExecuteLocked = False 737 self._UsingPolyTree = False 738 self._JoinList = None 739 self._HorzJoins = None 740 741 def _Reset(self): 742 ClipperBase._Reset(self) 743 self._Scanbeam = None 744 self._PolyOutList = [] 745 lm = self._LocalMinList 746 while lm is not None: 747 self._InsertScanbeam(lm.y) 748 lm = lm.nextLm 749 750 def Clear(self): 751 self._PolyOutList = [] 752 ClipperBase.Clear(self) 753 754 def _InsertScanbeam(self, y): 755 if self._Scanbeam is None: 756 self._Scanbeam = Scanbeam(y) 757 elif y > self._Scanbeam.y: 758 self._Scanbeam = Scanbeam(y, self._Scanbeam) 759 else: 760 sb = self._Scanbeam 761 while sb.nextSb is not None and y <= sb.nextSb.y: 762 sb = sb.nextSb 763 if y == sb.y: return 764 newSb = Scanbeam(y, sb.nextSb) 765 sb.nextSb = newSb 766 767 def _PopScanbeam(self): 768 result = self._Scanbeam.y 769 self._Scanbeam = self._Scanbeam.nextSb 770 return result 771 772 def _SetWindingCount(self, edge): 773 e = edge.prevInAEL 774 while e is not None and e.PolyType != edge.PolyType: 775 e = e.prevInAEL 776 if e is None: 777 edge.windCnt = edge.windDelta 778 edge.windCnt2 = 0 779 e = self._ActiveEdges 780 elif self._IsEvenOddFillType(edge): 781 edge.windCnt = 1 782 edge.windCnt2 = e.windCnt2 783 e = e.nextInAEL 784 else: 785 if e.windCnt * e.windDelta < 0: 786 if (abs(e.windCnt) > 1): 787 if (e.windDelta * edge.windDelta < 0): edge.windCnt = e.windCnt 788 else: edge.windCnt = e.windCnt + edge.windDelta 789 else: 790 edge.windCnt = e.windCnt + e.windDelta + edge.windDelta 791 elif (abs(e.windCnt) > 1) and (e.windDelta * edge.windDelta < 0): 792 edge.windCnt = e.windCnt 793 elif e.windCnt + edge.windDelta == 0: 794 edge.windCnt = e.windCnt 795 else: 796 edge.windCnt = e.windCnt + edge.windDelta 797 edge.windCnt2 = e.windCnt2 798 e = e.nextInAEL 799 # update windCnt2 ... 800 if self._IsEvenOddAltFillType(edge): 801 while (e != edge): 802 if edge.windCnt2 == 0: edge.windCnt2 = 1 803 else: edge.windCnt2 = 0 804 e = e.nextInAEL 805 else: 806 while (e != edge): 807 edge.windCnt2 += e.windDelta 808 e = e.nextInAEL 809 810 def _IsEvenOddFillType(self, edge): 811 if edge.PolyType == PolyType.Subject: 812 return self._SubjFillType == PolyFillType.EvenOdd 813 else: 814 return self._ClipFillType == PolyFillType.EvenOdd 815 816 def _IsEvenOddAltFillType(self, edge): 817 if edge.PolyType == PolyType.Subject: 818 return self._ClipFillType == PolyFillType.EvenOdd 819 else: 820 return self._SubjFillType == PolyFillType.EvenOdd 821 822 def _IsContributing(self, edge): 823 if edge.PolyType == PolyType.Subject: 824 pft = self._SubjFillType 825 pft2 = self._ClipFillType 826 else: 827 pft = self._ClipFillType 828 pft2 = self._SubjFillType 829 if pft == PolyFillType.EvenOdd or pft == PolyFillType.NonZero: 830 if abs(edge.windCnt) != 1: return False 831 elif pft == PolyFillType.Positive: 832 if edge.windCnt != 1: return False 833 elif pft == PolyFillType.Negative: 834 if edge.windCnt != -1: return False 835 836 if self._ClipType == ClipType.Intersection: ########### 837 if pft2 == PolyFillType.EvenOdd or pft2 == PolyFillType.NonZero: 838 return edge.windCnt2 != 0 839 elif pft2 == PolyFillType.Positive: 840 return edge.windCnt2 > 0 841 else: 842 return edge.windCnt2 < 0 # Negative 843 elif self._ClipType == ClipType.Union: ########### 844 if pft2 == PolyFillType.EvenOdd or pft2 == PolyFillType.NonZero: 845 return edge.windCnt2 == 0 846 elif pft2 == PolyFillType.Positive: 847 return edge.windCnt2 <= 0 848 else: return edge.windCnt2 >= 0 # Negative 849 elif self._ClipType == ClipType.Difference: ########### 850 if edge.PolyType == PolyType.Subject: 851 if pft2 == PolyFillType.EvenOdd or pft2 == PolyFillType.NonZero: 852 return edge.windCnt2 == 0 853 elif edge.PolyType == PolyFillType.Positive: 854 return edge.windCnt2 <= 0 855 else: 856 return edge.windCnt2 >= 0 857 else: 858 if pft2 == PolyFillType.EvenOdd or pft2 == PolyFillType.NonZero: 859 return edge.windCnt2 != 0 860 elif pft2 == PolyFillType.Positive: 861 return edge.windCnt2 > 0 862 else: 863 return edge.windCnt2 < 0 864 else: # self._ClipType == ClipType.XOR: ########### 865 return True 866 867 def _AddEdgeToSEL(self, edge): 868 if self._SortedEdges is None: 869 self._SortedEdges = edge 870 edge.prevInSEL = None 871 edge.nextInSEL = None 872 else: 873 # add edge to front of list ... 874 edge.nextInSEL = self._SortedEdges 875 edge.prevInSEL = None 876 self._SortedEdges.prevInSEL = edge 877 self._SortedEdges = edge 878 879 def _CopyAELToSEL(self): 880 e = self._ActiveEdges 881 self._SortedEdges = e 882 while e is not None: 883 e.prevInSEL = e.prevInAEL 884 e.nextInSEL = e.nextInAEL 885 e = e.nextInAEL 886 887 def _InsertEdgeIntoAEL(self, edge): 888 edge.prevInAEL = None 889 edge.nextInAEL = None 890 if self._ActiveEdges is None: 891 self._ActiveEdges = edge 892 elif _E2InsertsBeforeE1(self._ActiveEdges, edge): 893 edge.nextInAEL = self._ActiveEdges 894 self._ActiveEdges.prevInAEL = edge 895 self._ActiveEdges = edge 896 else: 897 e = self._ActiveEdges 898 while e.nextInAEL is not None and \ 899 not _E2InsertsBeforeE1(e.nextInAEL, edge): 900 e = e.nextInAEL 901 edge.nextInAEL = e.nextInAEL 902 if e.nextInAEL is not None: e.nextInAEL.prevInAEL = edge 903 edge.prevInAEL = e 904 e.nextInAEL = edge 905 906 def _InsertLocalMinimaIntoAEL(self, botY): 907 while self._CurrentLocMin is not None and \ 908 self._CurrentLocMin.y == botY: 909 lb = self._CurrentLocMin.leftBound 910 rb = self._CurrentLocMin.rightBound 911 self._InsertEdgeIntoAEL(lb) 912 self._InsertScanbeam(lb.Top.y) 913 self._InsertEdgeIntoAEL(rb) 914 if self._IsEvenOddFillType(lb): 915 lb.windDelta = 1 916 rb.windDelta = 1 917 else: 918 rb.windDelta = -lb.windDelta 919 self._SetWindingCount(lb) 920 rb.windCnt = lb.windCnt 921 rb.windCnt2 = lb.windCnt2 922 if rb.dx == horizontal: 923 self._AddEdgeToSEL(rb) 924 self._InsertScanbeam(rb.nextInLML.Top.y) 925 else: 926 self._InsertScanbeam(rb.Top.y) 927 if self._IsContributing(lb): 928 self._AddLocalMinPoly(lb, rb, Point(lb.Curr.x, self._CurrentLocMin.y)) 929 930 if rb.outIdx >= 0 and rb.dx == horizontal and self._HorzJoins is not None: 931 hj = self._HorzJoins 932 while True: 933 dummy1, dummy2, overlap = _GetOverlapSegment(hj.edge.Bot, hj.edge.Top, rb.Bot, rb.Top) 934 if overlap: 935 self._AddJoin(hj.edge, rb, hj.savedIdx) 936 hj = hj.nextHj 937 if hj == self._HorzJoins: break 938 939 if (lb.nextInAEL != rb): 940 941 if rb.outIdx >= 0 and rb.prevInAEL.outIdx >= 0 and _SlopesEqual2(rb.prevInAEL, rb): 942 self._AddJoin(rb, rb.prevInAEL) 943 944 e = lb.nextInAEL 945 pt = lb.Curr 946 while e != rb: 947 self._IntersectEdges(rb, e, pt) 948 e = e.nextInAEL 949 self._PopLocalMinima() 950 951 def _SwapPositionsInAEL(self, e1, e2): 952 if e1.nextInAEL == e2: 953 nextE = e2.nextInAEL 954 if nextE is not None: nextE.prevInAEL = e1 955 prevE = e1.prevInAEL 956 if prevE is not None: prevE.nextInAEL = e2 957 e2.prevInAEL = prevE 958 e2.nextInAEL = e1 959 e1.prevInAEL = e2 960 e1.nextInAEL = nextE 961 elif e2.nextInAEL == e1: 962 nextE = e1.nextInAEL 963 if nextE is not None: nextE.prevInAEL = e2 964 prevE = e2.prevInAEL 965 if prevE is not None: prevE.nextInAEL = e1 966 e1.prevInAEL = prevE 967 e1.nextInAEL = e2 968 e2.prevInAEL = e1 969 e2.nextInAEL = nextE 970 else: 971 nextE = e1.nextInAEL 972 prevE = e1.prevInAEL 973 e1.nextInAEL = e2.nextInAEL 974 if e1.nextInAEL is not None: e1.nextInAEL.prevInAEL = e1 975 e1.prevInAEL = e2.prevInAEL 976 if e1.prevInAEL is not None: e1.prevInAEL.nextInAEL = e1 977 e2.nextInAEL = nextE 978 if e2.nextInAEL is not None: e2.nextInAEL.prevInAEL = e2 979 e2.prevInAEL = prevE 980 if e2.prevInAEL is not None: e2.prevInAEL.nextInAEL = e2 981 if e1.prevInAEL is None: self._ActiveEdges = e1 982 elif e2.prevInAEL is None: self._ActiveEdges = e2 983 984 def _SwapPositionsInSEL(self, e1, e2): 985 if e1.nextInSEL == e2: 986 nextE = e2.nextInSEL 987 if nextE is not None: nextE.prevInSEL = e1 988 prevE = e1.prevInSEL 989 if prevE is not None: prevE.nextInSEL = e2 990 e2.prevInSEL = prevE 991 e2.nextInSEL = e1 992 e1.prevInSEL = e2 993 e1.nextInSEL = nextE 994 elif e2.nextInSEL == e1: 995 nextE = e1.nextInSEL 996 if nextE is not None: nextE.prevInSEL = e2 997 prevE = e2.prevInSEL 998 if prevE is not None: prevE.nextInSEL = e1 999 e1.prevInSEL = prevE 1000 e1.nextInSEL = e2 1001 e2.prevInSEL = e1 1002 e2.nextInSEL = nextE 1003 else: 1004 nextE = e1.nextInSEL 1005 prevE = e1.prevInSEL 1006 e1.nextInSEL = e2.nextInSEL 1007 e1.nextInSEL = e2.nextInSEL 1008 if e1.nextInSEL is not None: e1.nextInSEL.prevInSEL = e1 1009 e1.prevInSEL = e2.prevInSEL 1010 if e1.prevInSEL is not None: e1.prevInSEL.nextInSEL = e1 1011 e2.nextInSEL = nextE 1012 if e2.nextInSEL is not None: e2.nextInSEL.prevInSEL = e2 1013 e2.prevInSEL = prevE 1014 if e2.prevInSEL is not None: e2.prevInSEL.nextInSEL = e2 1015 if e1.prevInSEL is None: self._SortedEdges = e1 1016 elif e2.prevInSEL is None: self._SortedEdges = e2 1017 1018 def _IsTopHorz(self, xPos): 1019 e = self._SortedEdges 1020 while e is not None: 1021 if (xPos >= min(e.Curr.x,e.Top.x)) and (xPos <= max(e.Curr.x,e.Top.x)): 1022 return False 1023 e = e.nextInSEL 1024 return True 1025 1026 def _ProcessHorizontal(self, horzEdge): 1027 if horzEdge.Curr.x < horzEdge.Top.x: 1028 horzLeft = horzEdge.Curr.x 1029 horzRight = horzEdge.Top.x 1030 direction = Direction.LeftToRight 1031 else: 1032 horzLeft = horzEdge.Top.x 1033 horzRight = horzEdge.Curr.x 1034 direction = Direction.RightToLeft 1035 eMaxPair = None 1036 if horzEdge.nextInLML is None: 1037 eMaxPair = _GetMaximaPair(horzEdge) 1038 e = _GetnextInAEL(horzEdge, direction) 1039 while e is not None: 1040 if (e.Curr.x == horzEdge.Top.x) and eMaxPair is None: 1041 if _SlopesEqual2(e, horzEdge.nextInLML): 1042 if horzEdge.outIdx >= 0 and e.outIdx >= 0: 1043 self._AddJoin(horzEdge.nextInLML, e, horzEdge.outIdx) 1044 break 1045 elif e.dx < horzEdge.nextInLML.dx: break 1046 eNext = _GetnextInAEL(e, direction) 1047 if eMaxPair is not None or \ 1048 ((direction == Direction.LeftToRight) and (e.Curr.x < horzRight)) or \ 1049 ((direction == Direction.RightToLeft) and (e.Curr.x > horzLeft)): 1050 if e == eMaxPair: 1051 if direction == Direction.LeftToRight: 1052 self._IntersectEdges(horzEdge, e, Point(e.Curr.x, horzEdge.Curr.y)) 1053 else: 1054 self._IntersectEdges(e, horzEdge, Point(e.Curr.x, horzEdge.Curr.y)) 1055 return 1056 elif e.dx == horizontal and not _IsMinima(e) and e.Curr.x <= e.Top.x: 1057 if direction == Direction.LeftToRight: 1058 self._IntersectEdges(horzEdge, e, Point(e.Curr.x, horzEdge.Curr.y), 1059 _ProtectRight(not self._IsTopHorz(e.Curr.x))) 1060 else: 1061 self._IntersectEdges(e, horzEdge, Point(e.Curr.x, horzEdge.Curr.y), 1062 _ProtectLeft(not self._IsTopHorz(e.Curr.x))) 1063 elif (direction == Direction.LeftToRight): 1064 self._IntersectEdges(horzEdge, e, Point(e.Curr.x, horzEdge.Curr.y), 1065 _ProtectRight(not self._IsTopHorz(e.Curr.x))) 1066 else: 1067 self._IntersectEdges(e, horzEdge, Point(e.Curr.x, horzEdge.Curr.y), 1068 _ProtectLeft(not self._IsTopHorz(e.Curr.x))) 1069 self._SwapPositionsInAEL(horzEdge, e) 1070 elif ((direction == Direction.LeftToRight and e.Curr.x >= horzRight) or \ 1071 (direction == Direction.RightToLeft and e.Curr.x <= horzLeft)): break 1072 e = eNext 1073 if horzEdge.nextInLML is not None: 1074 if horzEdge.outIdx >= 0: 1075 self._AddOutPt(horzEdge, horzEdge.Top) 1076 self._UpdateEdgeIntoAEL(horzEdge) 1077 else: 1078 if horzEdge.outIdx >= 0: 1079 self._IntersectEdges(horzEdge, eMaxPair, \ 1080 Point(horzEdge.Top.x, horzEdge.Curr.y), Protects.Both) 1081 if eMaxPair.outIdx >= 0: raise Exception("Clipper: Horizontal Error") 1082 self._DeleteFromAEL(eMaxPair) 1083 self._DeleteFromAEL(horzEdge) 1084 1085 def _ProcessHorizontals(self): 1086 while self._SortedEdges is not None: 1087 e = self._SortedEdges 1088 self._DeleteFromSEL(e) 1089 self._ProcessHorizontal(e) 1090 1091 def _AddJoin(self, e1, e2, e1OutIdx = -1, e2OutIdx = -1): 1092 jr = JoinRec() 1093 if e1OutIdx >= 0: jr.poly1Idx = e1OutIdx 1094 else: jr.poly1Idx = e1.outIdx 1095 jr.pt1a = e1.Curr 1096 jr.pt1b = e1.Top 1097 if e2OutIdx >= 0: jr.poly2Idx = e2OutIdx 1098 else: jr.poly2Idx = e2.outIdx 1099 jr.pt2a = e2.Curr 1100 jr.pt2b = e2.Top 1101 if self._JoinList is None: 1102 self._JoinList = [] 1103 self._JoinList.append(jr) 1104 1105 def _FixupJoinRecs(self, jr, outPt, startIdx): 1106 for i in range(startIdx, len(self._JoinList)): 1107 jr2 = self._JoinList[i] 1108 if jr2.poly1Idx == jr.poly1Idx and _PointIsVertex(jr2.pt1a, outPt): 1109 jr2.poly1Idx = jr.poly2Idx 1110 if jr2.poly2Idx == jr.poly1Idx and _PointIsVertex(jr2.pt2a, outPt): 1111 jr2.poly2Idx = jr.poly2Idx 1112 1113 def _AddHorzJoin(self, e, idx): 1114 hj = HorzJoin(e, idx) 1115 if self._HorzJoins == None: 1116 self._HorzJoins = hj 1117 hj.nextHj = hj 1118 hj.prevHj = hj 1119 else: 1120 hj.nextHj = self._HorzJoins 1121 hj.prevHj = self._HorzJoins.prevHj 1122 self._HorzJoins.prevHj.nextHj = hj 1123 self._HorzJoins.prevHj = hj 1124 1125 def _InsertIntersectNode(self, e1, e2, pt): 1126 newNode = IntersectNode(e1, e2, pt) 1127 if self._IntersectNodes is None: 1128 self._IntersectNodes = newNode 1129 elif newNode.pt.y > self._IntersectNodes.pt.y: 1130 newNode.nextIn = self._IntersectNodes 1131 self._IntersectNodes = newNode 1132 else: 1133 node = self._IntersectNodes 1134 while node.nextIn is not None and \ 1135 newNode.pt.y < node.nextIn.pt.y: 1136 node = node.nextIn 1137 newNode.nextIn = node.nextIn 1138 node.nextIn = newNode 1139 1140 def _ProcessIntersections(self, botY, topY): 1141 try: 1142 self._BuildIntersectList(botY, topY) 1143 if self._IntersectNodes is None: return True 1144 if self._IntersectNodes.nextIn is not None and \ 1145 not self._FixupIntersectionOrder(): return False 1146 self._ProcessIntersectList() 1147 return True 1148 finally: 1149 self._IntersectNodes = None 1150 self._SortedEdges = None 1151 1152 def _BuildIntersectList(self, botY, topY): 1153 e = self._ActiveEdges 1154 if e is None: return 1155 self._SortedEdges = e 1156 while e is not None: 1157 e.prevInSEL = e.prevInAEL 1158 e.nextInSEL = e.nextInAEL 1159 e.Curr = Point(_TopX(e, topY), e.Curr.y) 1160 e = e.nextInAEL 1161 while True: 1162 isModified = False 1163 e = self._SortedEdges 1164 while e.nextInSEL is not None: 1165 eNext = e.nextInSEL 1166 if e.Curr.x <= eNext.Curr.x: 1167 e = eNext 1168 continue 1169 pt, intersected = _IntersectPoint(e, eNext) 1170 if not intersected and e.Curr.x > eNext.Curr.x +1: 1171 raise Exception("Intersect Error") 1172 if pt.y > botY: 1173 pt = Point(_TopX(e, botY), botY) 1174 self._InsertIntersectNode(e, eNext, pt) 1175 self._SwapPositionsInSEL(e, eNext) 1176 isModified = True 1177 if e.prevInSEL is not None: 1178 e.prevInSEL.nextInSEL = None 1179 else: 1180 break 1181 if not isModified: break 1182 self._SortedEdges = None 1183 return 1184 1185 def _ProcessIntersectList(self): 1186 while self._IntersectNodes is not None: 1187 node = self._IntersectNodes 1188 self._IntersectEdges(node.e1, node.e2, node.pt, Protects.Both) 1189 self._SwapPositionsInAEL(node.e1, node.e2) 1190 self._IntersectNodes = node.nextIn 1191 1192 def _DeleteFromAEL(self, e): 1193 aelPrev = e.prevInAEL 1194 aelNext = e.nextInAEL 1195 if aelPrev is None and aelNext is None and e != self._ActiveEdges: 1196 return 1197 if aelPrev is not None: 1198 aelPrev.nextInAEL = aelNext 1199 else: 1200 self._ActiveEdges = aelNext 1201 if aelNext is not None: 1202 aelNext.prevInAEL = aelPrev 1203 e.nextInAEL = None 1204 e.prevInAEL = None 1205 1206 def _DeleteFromSEL(self, e): 1207 SELPrev = e.prevInSEL 1208 SELNext = e.nextInSEL 1209 if SELPrev is None and SELNext is None and e != self._SortedEdges: 1210 return 1211 if SELPrev is not None: 1212 SELPrev.nextInSEL = SELNext 1213 else: 1214 self._SortedEdges = SELNext 1215 if SELNext is not None: 1216 SELNext.prevInSEL = SELPrev 1217 e.nextInSEL = None 1218 e.prevInSEL = None 1219 1220 def _IntersectEdges(self, e1, e2, pt, protects = Protects.Neither): 1221 e1stops = protects & Protects.Left == 0 and \ 1222 e1.nextInLML is None and \ 1223 e1.Top.x == pt.x and e1.Top.y == pt.y 1224 e2stops = protects & Protects.Right == 0 and \ 1225 e2.nextInLML is None and \ 1226 e2.Top.x == pt.x and e2.Top.y == pt.y 1227 e1Contributing = e1.outIdx >= 0 1228 e2contributing = e2.outIdx >= 0 1229 1230 if e1.PolyType == e2.PolyType: 1231 if self._IsEvenOddFillType(e1): 1232 e1Wc = e1.windCnt 1233 e1.windCnt = e2.windCnt 1234 e2.windCnt = e1Wc 1235 else: 1236 if e1.windCnt + e2.windDelta == 0: e1.windCnt = -e1.windCnt 1237 else: e1.windCnt += e2.windDelta 1238 if e2.windCnt - e1.windDelta == 0: e2.windCnt = -e2.windCnt 1239 else: e2.windCnt -= e1.windDelta 1240 else: 1241 if not self._IsEvenOddFillType(e2): e1.windCnt2 += e2.windDelta 1242 elif e1.windCnt2 == 0: e1.windCnt2 = 1 1243 else: e1.windCnt2 = 0 1244 if not self._IsEvenOddFillType(e1): e2.windCnt2 -= e1.windDelta 1245 elif e2.windCnt2 == 0: e2.windCnt2 = 1 1246 else: e2.windCnt2 = 0 1247 1248 if e1.PolyType == PolyType.Subject: 1249 e1FillType = self._SubjFillType 1250 e1FillType2 = self._ClipFillType 1251 else: 1252 e1FillType = self._ClipFillType 1253 e1FillType2 = self._SubjFillType 1254 1255 if e2.PolyType == PolyType.Subject: 1256 e2FillType = self._SubjFillType 1257 e2FillType2 = self._ClipFillType 1258 else: 1259 e2FillType = self._ClipFillType 1260 e2FillType2 = self._SubjFillType 1261 1262 if e1FillType == PolyFillType.Positive: e1Wc = e1.windCnt 1263 elif e1FillType == PolyFillType.Negative: e1Wc = -e1.windCnt 1264 else: e1Wc = abs(e1.windCnt) 1265 1266 if e2FillType == PolyFillType.Positive: e2Wc = e2.windCnt 1267 elif e2FillType == PolyFillType.Negative: e2Wc = -e2.windCnt 1268 else: e2Wc = abs(e2.windCnt) 1269 1270 if e1Contributing and e2contributing: 1271 if e1stops or e2stops or \ 1272 (e1Wc != 0 and e1Wc != 1) or (e2Wc != 0 and e2Wc != 1) or \ 1273 (e1.PolyType != e2.PolyType and self._ClipType != ClipType.Xor): 1274 self._AddLocalMaxPoly(e1, e2, pt) 1275 else: 1276 self._AddOutPt(e1, pt) 1277 self._AddOutPt(e2, pt) 1278 _SwapSides(e1, e2) 1279 _SwapPolyIndexes(e1, e2) 1280 elif e1Contributing: 1281 if (e2Wc == 0 or e2Wc == 1): 1282 self._AddOutPt(e1, pt) 1283 _SwapSides(e1, e2) 1284 _SwapPolyIndexes(e1, e2) 1285 elif e2contributing: 1286 if (e1Wc == 0 or e1Wc == 1): 1287 self._AddOutPt(e2, pt) 1288 _SwapSides(e1, e2) 1289 _SwapPolyIndexes(e1, e2) 1290 1291 elif (e1Wc == 0 or e1Wc == 1) and (e2Wc == 0 or e2Wc == 1) and \ 1292 not e1stops and not e2stops: 1293 1294 e1FillType2 = e2FillType2 = PolyFillType.EvenOdd 1295 if e1FillType2 == PolyFillType.Positive: e1Wc2 = e1.windCnt2 1296 elif e1FillType2 == PolyFillType.Negative: e1Wc2 = -e1.windCnt2 1297 else: e1Wc2 = abs(e1.windCnt2) 1298 if e2FillType2 == PolyFillType.Positive: e2Wc2 = e2.windCnt2 1299 elif e2FillType2 == PolyFillType.Negative: e2Wc2 = -e2.windCnt2 1300 else: e2Wc2 = abs(e2.windCnt2) 1301 1302 if e1.PolyType != e2.PolyType: 1303 self._AddLocalMinPoly(e1, e2, pt) 1304 elif e1Wc == 1 and e2Wc == 1: 1305 if self._ClipType == ClipType.Intersection: 1306 if e1Wc2 > 0 and e2Wc2 > 0: 1307 self._AddLocalMinPoly(e1, e2, pt) 1308 elif self._ClipType == ClipType.Union: 1309 if e1Wc2 <= 0 and e2Wc2 <= 0: 1310 self._AddLocalMinPoly(e1, e2, pt) 1311 elif self._ClipType == ClipType.Difference: 1312 if (e1.PolyType == PolyType.Clip and e1Wc2 > 0 and e2Wc2 > 0) or \ 1313 (e1.PolyType == PolyType.Subject and e1Wc2 <= 0 and e2Wc2 <= 0): 1314 self._AddLocalMinPoly(e1, e2, pt) 1315 else: 1316 self._AddLocalMinPoly(e1, e2, pt) 1317 else: 1318 _SwapSides(e1, e2, self._PolyOutList) 1319 1320 if e1stops != e2stops and \ 1321 ((e1stops and e1.outIdx >= 0) or (e2stops and e2.outIdx >= 0)): 1322 _SwapSides(e1, e2, self._PolyOutList) 1323 _SwapPolyIndexes(e1, e2) 1324 if e1stops: self._DeleteFromAEL(e1) 1325 if e2stops: self._DeleteFromAEL(e2) 1326 1327 def _DoMaxima(self, e, topY): 1328 eMaxPair = _GetMaximaPair(e) 1329 x = e.Top.x 1330 eNext = e.nextInAEL 1331 while eNext != eMaxPair: 1332 if eNext is None: raise Exception("DoMaxima error") 1333 self._IntersectEdges(e, eNext, Point(x, topY), Protects.Both) 1334 self._SwapPositionsInAEL(e, eNext) 1335 eNext = e.nextInAEL 1336 if e.outIdx < 0 and eMaxPair.outIdx < 0: 1337 self._DeleteFromAEL(e) 1338 self._DeleteFromAEL(eMaxPair) 1339 elif e.outIdx >= 0 and eMaxPair.outIdx >= 0: 1340 self._IntersectEdges(e, eMaxPair, Point(x, topY)) 1341 else: 1342 raise Exception("DoMaxima error") 1343 1344 def _UpdateEdgeIntoAEL(self, e): 1345 if e.nextInLML is None: 1346 raise Exception("UpdateEdgeIntoAEL error") 1347 aelPrev = e.prevInAEL 1348 aelNext = e.nextInAEL 1349 e.nextInLML.outIdx = e.outIdx 1350 if aelPrev is not None: 1351 aelPrev.nextInAEL = e.nextInLML 1352 else: 1353 self._ActiveEdges = e.nextInLML 1354 if aelNext is not None: 1355 aelNext.prevInAEL = e.nextInLML 1356 e.nextInLML.side = e.side 1357 e.nextInLML.windDelta = e.windDelta 1358 e.nextInLML.windCnt = e.windCnt 1359 e.nextInLML.windCnt2 = e.windCnt2 1360 e = e.nextInLML 1361 e.prevInAEL = aelPrev 1362 e.nextInAEL = aelNext 1363 if e.dx != horizontal: 1364 self._InsertScanbeam(e.Top.y) 1365 return e 1366 1367 def _AddLocalMinPoly(self, e1, e2, pt): 1368 if e2.dx == horizontal or e1.dx > e2.dx: 1369 self._AddOutPt(e1, pt) 1370 e2.outIdx = e1.outIdx 1371 e1.side = EdgeSide.Left 1372 e2.side = EdgeSide.Right 1373 e = e1 1374 if e.prevInAEL == e2: prevE = e2.prevInAEL 1375 else: prevE = e1.prevInAEL 1376 else: 1377 self._AddOutPt(e2, pt) 1378 e1.outIdx = e2.outIdx 1379 e1.side = EdgeSide.Right 1380 e2.side = EdgeSide.Left 1381 e = e2 1382 if e.prevInAEL == e1: prevE = e1.prevInAEL 1383 else: prevE = e.prevInAEL 1384 1385 if prevE is not None and prevE.outIdx >= 0 and \ 1386 _TopX(prevE, pt.y) == _TopX(e, pt.y) and \ 1387 _SlopesEqual2(e, prevE): 1388 self._AddJoin(e, prevE) 1389 return 1390 1391 def _AddLocalMaxPoly(self, e1, e2, pt): 1392 self._AddOutPt(e1, pt) 1393 if e1.outIdx == e2.outIdx: 1394 e1.outIdx = -1 1395 e2.outIdx = -1 1396 elif e1.outIdx < e2.outIdx: 1397 self._AppendPolygon(e1, e2) 1398 else: 1399 self._AppendPolygon(e2, e1) 1400 1401 def _CreateOutRec(self): 1402 outRec = OutRec(len(self._PolyOutList)) 1403 self._PolyOutList.append(outRec) 1404 return outRec 1405 1406 def _AddOutPt(self, e, pt): 1407 toFront = e.side == EdgeSide.Left 1408 if e.outIdx < 0: 1409 outRec = self._CreateOutRec(); 1410 e.outIdx = outRec.idx 1411 op = OutPt(outRec.idx, pt) 1412 op.nextOp = op 1413 op.prevOp = op 1414 outRec.pts = op 1415 _SetHoleState(e, outRec, self._PolyOutList) 1416 else: 1417 outRec = self._PolyOutList[e.outIdx] 1418 op = outRec.pts 1419 if (toFront and _PointsEqual(pt, op.pt)) or \ 1420 (not toFront and _PointsEqual(pt, op.prevOp.pt)): return 1421 op2 = OutPt(outRec.idx, pt) 1422 op2.nextOp = op 1423 op2.prevOp = op.prevOp 1424 op.prevOp.nextOp = op2 1425 op.prevOp = op2 1426 if toFront: outRec.pts = op2 1427 1428 def _AppendPolygon(self, e1, e2): 1429 outRec1 = self._PolyOutList[e1.outIdx] 1430 outRec2 = self._PolyOutList[e2.outIdx] 1431 holeStateRec = None 1432 if _Param1RightOfParam2(outRec1, outRec2): holeStateRec = outRec2 1433 elif _Param1RightOfParam2(outRec2, outRec1): holeStateRec = outRec1 1434 else: holeStateRec = _GetLowermostRec(outRec1, outRec2) 1435 1436 p1_lft = outRec1.pts 1437 p2_lft = outRec2.pts 1438 p1_rt = p1_lft.prevOp 1439 p2_rt = p2_lft.prevOp 1440 newSide = EdgeSide.Left 1441 1442 if e1.side == EdgeSide.Left: 1443 if e2.side == EdgeSide.Left: 1444 # z y x a b c 1445 _ReversePolyPtLinks(p2_lft) 1446 p2_lft.nextOp = p1_lft 1447 p1_lft.prevOp = p2_lft 1448 p1_rt.nextOp = p2_rt 1449 p2_rt.prevOp = p1_rt 1450 outRec1.pts = p2_rt 1451 else: 1452 # x y z a b c 1453 p2_rt.nextOp = p1_lft 1454 p1_lft.prevOp = p2_rt 1455 p2_lft.prevOp = p1_rt 1456 p1_rt.nextOp = p2_lft 1457 outRec1.pts = p2_lft 1458 else: 1459 newSide = EdgeSide.Right 1460 if e2.side == EdgeSide.Right: 1461 # a b c z y x 1462 _ReversePolyPtLinks(p2_lft) 1463 p1_rt.nextOp = p2_rt 1464 p2_rt.prevOp = p1_rt 1465 p2_lft.nextOp = p1_lft 1466 p1_lft.prevOp = p2_lft 1467 else: 1468 # a b c x y z 1469 p1_rt.nextOp = p2_lft 1470 p2_lft.prevOp = p1_rt 1471 p1_lft.prevOp = p2_rt 1472 p2_rt.nextOp = p1_lft 1473 1474 outRec1.bottomPt = None 1475 if holeStateRec == outRec2: 1476 if outRec2.FirstLeft != outRec1: 1477 outRec1.FirstLeft = outRec2.FirstLeft 1478 outRec1.isHole = outRec2.isHole 1479 outRec2.pts = None 1480 outRec2.bottomPt = None 1481 outRec2.FirstLeft = outRec1 1482 OKIdx = outRec1.idx 1483 ObsoleteIdx = outRec2.idx 1484 1485 e1.outIdx = -1 1486 e2.outIdx = -1 1487 1488 e = self._ActiveEdges 1489 while e is not None: 1490 if e.outIdx == ObsoleteIdx: 1491 e.outIdx = OKIdx 1492 e.side = newSide 1493 break 1494 e = e.nextInAEL 1495 outRec2.idx = outRec1.idx 1496 1497 def _FixupIntersectionOrder(self): 1498 self._CopyAELToSEL() 1499 inode = self._IntersectNodes 1500 while inode is not None: 1501 if (not _EdgesAdjacent(inode)): 1502 nextNode = inode.nextIn 1503 while (nextNode and not _EdgesAdjacent(nextNode)): 1504 nextNode = nextNode.nextIn 1505 if (nextNode is None): return False 1506 e1 = inode.e1 1507 e2 = inode.e2 1508 p = inode.pt 1509 inode.e1 = nextNode.e1 1510 inode.e2 = nextNode.e2 1511 inode.pt = nextNode.pt 1512 nextNode.e1 = e1 1513 nextNode.e2 = e2 1514 nextNode.pt = p 1515 1516 self._SwapPositionsInSEL(inode.e1, inode.e2); 1517 inode = inode.nextIn 1518 return True 1519 1520 def _ProcessEdgesAtTopOfScanbeam(self, topY): 1521 e = self._ActiveEdges 1522 while e is not None: 1523 if _IsMaxima(e, topY) and _GetMaximaPair(e).dx != horizontal: 1524 ePrev = e.prevInAEL 1525 self._DoMaxima(e, topY) 1526 if ePrev is None: e = self._ActiveEdges 1527 else: e = ePrev.nextInAEL 1528 else: 1529 intermediateVert = _IsIntermediate(e, topY) 1530 if intermediateVert and e.nextInLML.dx == horizontal: 1531 if e.outIdx >= 0: 1532 self._AddOutPt(e, e.Top) 1533 hj = self._HorzJoins 1534 if hj is not None: 1535 while True: 1536 _1, _2, overlap = _GetOverlapSegment( 1537 hj.edge.Bot, hj.edge.Top, e.nextInLML.Bot, e.nextInLML.Top) 1538 if overlap: self._AddJoin(hj.edge, e.nextInLML, hj.savedIdx, e.outIdx) 1539 hj = hj.nextHj 1540 if hj == self._HorzJoins: break 1541 self._AddHorzJoin(e.nextInLML, e.outIdx) 1542 1543 e = self._UpdateEdgeIntoAEL(e) 1544 self._AddEdgeToSEL(e) 1545 else: 1546 e.Curr = Point(_TopX(e, topY), topY) 1547 if (self.ForceSimple and e.prevInAEL is not None and 1548 e.prevInAEL.Curr.x == e.Curr.x and 1549 e.outIdx >= 0 and e.prevInAEL.outIdx >= 0): 1550 if (intermediateVert): 1551 self._AddOutPt(e.prevInAEL, Point(e.Curr.x, topY)); 1552 else: 1553 self._AddOutPt(e, Point(e.Curr.x, topY)) 1554 e = e.nextInAEL 1555 1556 self._ProcessHorizontals() 1557 1558 e = self._ActiveEdges 1559 while e is not None: 1560 if _IsIntermediate(e, topY): 1561 if (e.outIdx >= 0) : 1562 self._AddOutPt(e, e.Top) 1563 e = self._UpdateEdgeIntoAEL(e) 1564 1565 ePrev = e.prevInAEL 1566 eNext = e.nextInAEL 1567 if ePrev is not None and ePrev.Curr.x == e.Bot.x and \ 1568 (ePrev.Curr.y == e.Bot.y) and (e.outIdx >= 0) and \ 1569 (ePrev.outIdx >= 0) and (ePrev.Curr.y > ePrev.Top.y) and \ 1570 _SlopesEqual2(e, ePrev): 1571 self._AddOutPt(ePrev, e.Bot) 1572 self._AddJoin(e, ePrev) 1573 elif eNext is not None and (eNext.Curr.x == e.Bot.x) and \ 1574 (eNext.Curr.y == e.Bot.y) and (e.outIdx >= 0) and \ 1575 (eNext.outIdx >= 0) and (eNext.Curr.y > eNext.Top.y) and \ 1576 _SlopesEqual2(e, eNext): 1577 self._AddOutPt(eNext, e.Bot) 1578 self._AddJoin(e, eNext) 1579 1580 e = e.nextInAEL 1581 1582 def _Area(self, pts): 1583 # see http://www.mathopenref.com/coordpolygonarea2.html 1584 result = 0.0 1585 p = pts 1586 while True: 1587 result += (p.pt.x + p.prevOp.pt.x) * (p.prevOp.pt.y - p.pt.y) 1588 p = p.nextOp 1589 if p == pts: break 1590 return result / 2 1591 1592 def _JoinPoints(self, jr): 1593 p1, p2 = None, None 1594 outRec1 = self._PolyOutList[jr.poly1Idx] 1595 outRec2 = self._PolyOutList[jr.poly2Idx] 1596 if outRec1 is None or outRec2 is None: return p1, p2, False 1597 pp1a = outRec1.pts; pp2a = outRec2.pts 1598 pt1 = jr.pt2a; pt2 = jr.pt2b 1599 pt3 = jr.pt1a; pt4 = jr.pt1b 1600 pp1a, pt1, pt2, result = _FindSegment(pp1a, pt1, pt2) 1601 if not result: return p1, p2, False 1602 if (outRec1 == outRec2): 1603 pp2a = pp1a.nextOp 1604 pp2a, pt3, pt4, result = _FindSegment(pp2a, pt3, pt4) 1605 if not result or pp2a == pp1a: return p1, p2, False 1606 else: 1607 pp2a, pt3, pt4, result = _FindSegment(pp2a, pt3, pt4) 1608 if not result: return p1, p2, False 1609 pt1, pt2, result = _GetOverlapSegment(pt1, pt2, pt3, pt4) 1610 if not result: return p1, p2, False 1611 1612 prevOp = pp1a.prevOp 1613 if _PointsEqual(pp1a.pt, pt1): p1 = pp1a 1614 elif _PointsEqual(prevOp.pt, pt1): p1 = prevOp 1615 else: p1 = _InsertPolyPtBetween(pp1a, prevOp, pt1) 1616 1617 if _PointsEqual(pp1a.pt, pt2): p2 = pp1a 1618 elif _PointsEqual(prevOp.pt, pt2): p2 = prevOp 1619 elif (p1 == pp1a) or (p1 == prevOp): 1620 p2 = _InsertPolyPtBetween(pp1a, prevOp, pt2) 1621 elif _Pt3IsBetweenPt1AndPt2(pp1a.pt, p1.pt, pt2): 1622 p2 = _InsertPolyPtBetween(pp1a, p1, pt2) 1623 else: p2 = _InsertPolyPtBetween(p1, prevOp, pt2) 1624 1625 prevOp = pp2a.prevOp 1626 if _PointsEqual(pp2a.pt, pt1): p3 = pp2a 1627 elif _PointsEqual(prevOp.pt, pt1): p3 = prevOp 1628 else: p3 = _InsertPolyPtBetween(pp2a, prevOp, pt1) 1629 if _PointsEqual(pp2a.pt, pt2): p4 = pp2a 1630 elif _PointsEqual(prevOp.pt, pt2): p4 = prevOp 1631 elif (p3 == pp2a) or (p3 == prevOp): 1632 p4 = _InsertPolyPtBetween(pp2a, prevOp, pt2) 1633 elif _Pt3IsBetweenPt1AndPt2(pp2a.pt, p3.pt, pt2): 1634 p4 = _InsertPolyPtBetween(pp2a, p3, pt2) 1635 else: p4 = _InsertPolyPtBetween(p3, prevOp, pt2) 1636 1637 if p1.nextOp == p2 and p3.prevOp == p4: 1638 p1.nextOp = p3 1639 p3.prevOp = p1 1640 p2.prevOp = p4 1641 p4.nextOp = p2 1642 return p1, p2, True 1643 elif p1.prevOp == p2 and p3.nextOp == p4: 1644 p1.prevOp = p3 1645 p3.nextOp = p1 1646 p2.nextOp = p4 1647 p4.prevOp = p2 1648 return p1, p2, True 1649 return p1, p2, False 1650 1651 def _FixupFirstLefts1(self, oldOutRec, newOutRec): 1652 for outRec in self._PolyOutList: 1653 if outRec.pts is not None and outRec.FirstLeft == oldOutRec: 1654 if _Poly2ContainsPoly1(outRec.pts, newOutRec.pts): 1655 outRec.FirstLeft = newOutRec 1656 1657 def _FixupFirstLefts2(self, oldOutRec, newOutRec): 1658 for outRec in self._PolyOutList: 1659 if outRec.FirstLeft == oldOutRec: outRec.FirstLeft = newOutRec 1660 1661 def _GetOutRec(self, idx): 1662 outrec = self._PolyOutList[idx] 1663 while (outrec != self._PolyOutList[outrec.idx]): 1664 outrec = self._PolyOutList[outrec.idx] 1665 return outrec 1666 1667 def _JoinCommonEdges(self): 1668 for i in range(len(self._JoinList)): 1669 jr = self._JoinList[i] 1670 outRec1 = self._GetOutRec(jr.poly1Idx) 1671 outRec2 = self._GetOutRec(jr.poly2Idx) 1672 if outRec1.pts is None or outRec2.pts is None: continue 1673 1674 if outRec1 == outRec2: holeStateRec = outRec1 1675 elif _Param1RightOfParam2(outRec1, outRec2): holeStateRec = outRec2 1676 elif _Param1RightOfParam2(outRec2, outRec1): holeStateRec = outRec1 1677 else: holeStateRec = _GetLowermostRec(outRec1, outRec2) 1678 1679 p1, p2, result = self._JoinPoints(jr) 1680 if not result: continue 1681 1682 if outRec1 == outRec2: 1683 outRec1.pts = p1 1684 outRec1.bottomPt = None 1685 outRec2 = self._CreateOutRec() 1686 outRec2.pts = p2 1687 jr.poly2Idx = outRec2.idx 1688 1689 if _Poly2ContainsPoly1(outRec2.pts, outRec1.pts): 1690 outRec2.isHole = not outRec1.isHole 1691 outRec2.FirstLeft = outRec1 1692 1693 self._FixupJoinRecs(jr, p2, i + 1) 1694 1695 if self._UsingPolyTree: self._FixupFirstLefts2(outRec2, outRec1) 1696 1697 _FixupOutPolygon(outRec1) 1698 _FixupOutPolygon(outRec2) 1699 1700 if (outRec2.isHole ^ self.ReverseSolution) == self._Area(outRec2) > 0.0: 1701 _ReversePolyPtLinks(outRec2.pts) 1702 1703 elif _Poly2ContainsPoly1(outRec1.pts, outRec2.pts): 1704 outRec2.isHole = outRec1.isHole 1705 outRec1.isHole = not outRec2.isHole 1706 outRec2.FirstLeft = outRec1.FirstLeft 1707 outRec1.FirstLeft = outRec2 1708 1709 self._FixupJoinRecs(jr, p2, i + 1) 1710 1711 if self._UsingPolyTree: self._FixupFirstLefts2(outRec1, outRec2) 1712 1713 _FixupOutPolygon(outRec1) 1714 _FixupOutPolygon(outRec2) 1715 1716 if (outRec1.isHole ^ self.ReverseSolution) == self._Area(outRec1) > 0.0: 1717 _ReversePolyPtLinks(outRec1.pts) 1718 else: 1719 outRec2.isHole = outRec1.isHole 1720 outRec2.FirstLeft = outRec1.FirstLeft 1721 1722 self._FixupJoinRecs(jr, p2, i + 1) 1723 if self._UsingPolyTree: self._FixupFirstLefts1(outRec1, outRec2) 1724 1725 _FixupOutPolygon(outRec1) 1726 _FixupOutPolygon(outRec2) 1727 else: 1728 _FixupOutPolygon(outRec1) 1729 outRec2.pts = None 1730 outRec2.bottomPt = None 1731 outRec2.idx = outRec1.idx 1732 1733 outRec1.isHole = holeStateRec.isHole 1734 if holeStateRec == outRec2: 1735 outRec1.FirstLeft = outRec2.FirstLeft 1736 outRec2.FirstLeft = outRec1 1737 1738 if self._UsingPolyTree: self._FixupFirstLefts2(outRec2, outRec1) 1739 return 1740 1741 def _DoSimplePolygons(self): 1742 i = 0; 1743 while i < len(self._PolyOutList): 1744 outrec = self._PolyOutList[i] 1745 i +=1 1746 op = outrec.pts 1747 if (op is None): continue 1748 while True: 1749 op2 = op.nextOp 1750 while (op2 != outrec.pts): 1751 if (_PointsEqual(op.pt, op2.pt) and op2.nextOp != op and op2.prevOp != op): 1752 #split the polygon into two ... 1753 op3 = op.prevOp 1754 op4 = op2.prevOp 1755 op.prevOp = op4 1756 op4.nextOp = op 1757 op2.prevOp = op3 1758 op3.nextOp = op2 1759 1760 outrec.pts = op 1761 outrec2 = self._CreateOutRec(); 1762 outrec2.pts = op2; 1763 _UpdateOutPtIdxs(outrec2) 1764 if (_Poly2ContainsPoly1(outrec2.pts, outrec.pts)): 1765 #OutRec2 is contained by OutRec1 ... 1766 outrec2.isHole = not outrec.isHole 1767 outrec2.FirstLeft = outrec 1768 1769 elif (_Poly2ContainsPoly1(outrec.pts, outrec2.pts)): 1770 #OutRec1 is contained by OutRec2 ... 1771 outrec2.isHole = outrec.isHole 1772 outrec.isHole = not outrec2.isHole 1773 outrec2.FirstLeft = outrec.FirstLeft 1774 outrec.FirstLeft = outrec2 1775 else: 1776 #the 2 polygons are separate ... 1777 outrec2.isHole = outrec.isHole; 1778 outrec2.FirstLeft = outrec.FirstLeft; 1779 op2 = op; # ie get ready for the next iteration 1780 op2 = op2.nextOp 1781 op = op.nextOp 1782 if op == outrec.pts: break 1783 return 1784 1785 def _ExecuteInternal(self): 1786# try: 1787 try: 1788 self._Reset() 1789 if self._Scanbeam is None: return True 1790 botY = self._PopScanbeam() 1791 while True: 1792 self._InsertLocalMinimaIntoAEL(botY) 1793 self._HorzJoins = None 1794 self._ProcessHorizontals() 1795 topY = self._PopScanbeam() 1796 if not self._ProcessIntersections(botY, topY): return False 1797 self._ProcessEdgesAtTopOfScanbeam(topY) 1798 botY = topY 1799 if self._Scanbeam is None and self._CurrentLocMin is None: break 1800 1801 for outRec in self._PolyOutList: 1802 if outRec.pts is None: continue 1803 _FixupOutPolygon(outRec) 1804 if outRec.pts is None: continue 1805 if ((outRec.isHole ^ self.ReverseSolution) == (self._Area(outRec.pts) > 0.0)): 1806 _ReversePolyPtLinks(outRec.pts) 1807 1808 if self._JoinList is not None: self._JoinCommonEdges() 1809 if self.ForceSimple: self._DoSimplePolygons() 1810 1811 return True 1812 finally: 1813 self._JoinList = None 1814 self._HorzJoins = None 1815# except: 1816# return False 1817 1818 def Execute( 1819 self, 1820 clipType, 1821 solution, 1822 subjFillType = PolyFillType.EvenOdd, 1823 clipFillType = PolyFillType.EvenOdd): 1824 if self._ExecuteLocked: return False 1825 try: 1826 self._ExecuteLocked = True 1827 self._UsingPolyTree = True 1828 del solution[:] 1829 self._SubjFillType = subjFillType 1830 self._ClipFillType = clipFillType 1831 self._ClipType = clipType 1832 result = self._ExecuteInternal() 1833 if result: self._BuildResult(solution) 1834 finally: 1835 self._ExecuteLocked = False 1836 self._UsingPolyTree = False 1837 return result 1838 1839 def Execute2( 1840 self, 1841 clipType, 1842 solutionTree, 1843 subjFillType = PolyFillType.EvenOdd, 1844 clipFillType = PolyFillType.EvenOdd): 1845 if self._ExecuteLocked: return False 1846 try: 1847 self._ExecuteLocked = True 1848 self._UsingPolyTree = True 1849 solutionTree.Clear() 1850 self._SubjFillType = subjFillType 1851 self._ClipFillType = clipFillType 1852 self._ClipType = clipType 1853 result = self._ExecuteInternal() 1854 if result: self._BuildResult2(solutionTree) 1855 finally: 1856 self._ExecuteLocked = False 1857 self._UsingPolyTree = False 1858 return result 1859 1860 def _BuildResult(self, polygons): 1861 for outRec in self._PolyOutList: 1862 if outRec is None: continue 1863 cnt = _PointCount(outRec.pts) 1864 if (cnt < 3): continue 1865 poly = [] 1866 op = outRec.pts 1867 for _ in range(cnt): 1868 poly.append(op.pt) 1869 op = op.prevOp 1870 polygons.append(poly) 1871 return 1872 1873 def _BuildResult2(self, polyTree): 1874 for outRec in self._PolyOutList: 1875 if outRec is None: continue 1876 cnt = _PointCount(outRec.pts) 1877 if (cnt < 3): continue 1878 _FixHoleLinkage(outRec) 1879 1880 # add nodes to _AllNodes list ... 1881 polyNode = PolyNode() 1882 polyTree._AllNodes.append(polyNode) 1883 outRec.PolyNode = polyNode 1884 op = outRec.pts 1885 while True: 1886 polyNode.Contour.append(op.pt) 1887 op = op.prevOp 1888 if op == outRec.pts: break 1889 # build the tree ... 1890 for outRec in self._PolyOutList: 1891 if outRec.PolyNode is None: continue 1892 if outRec.FirstLeft is None: 1893 polyTree._AddChild(outRec.PolyNode) 1894 else: 1895 outRec.FirstLeft.PolyNode._AddChild(outRec.PolyNode) 1896 return 1897 1898#=============================================================================== 1899# OffsetPolygons (+ ancilliary functions) 1900#=============================================================================== 1901 1902def _GetUnitNormal(pt1, pt2): 1903 if pt2.x == pt1.x and pt2.y == pt1.y: 1904 return FloatPoint(0.0, 0.0) 1905 dx = float(pt2.x - pt1.x) 1906 dy = float(pt2.y - pt1.y) 1907 f = 1.0 / math.hypot(dx, dy) 1908 dx = float(dx) * f 1909 dy = float(dy) * f 1910 return FloatPoint(dy, -dx) 1911 1912def _GetBounds(pts): 1913 left = None 1914 for poly in pts: 1915 for pt in poly: 1916 left = pt.x 1917 top = pt.y 1918 right = pt.x 1919 bottom = pt.y 1920 break 1921 break 1922 1923 for poly in pts: 1924 for pt in poly: 1925 if pt.x < left: left = pt.x 1926 if pt.x > right: right = pt.x 1927 if pt.y < top: top = pt.y 1928 if pt.y > bottom: bottom = pt.y 1929 if left is None: return Rect(0, 0, 0, 0) 1930 else: return Rect(left, top, right, bottom) 1931 1932def _GetLowestPt(poly): 1933 # precondition: poly must not be empty 1934 result = poly[0] 1935 for pt in poly: 1936 if pt.y > result.y or (pt.y == result.y and pt.x < result.x): 1937 result = pt 1938 return result 1939 1940def _StripDupPts(poly): 1941 if poly == []: return poly 1942 for i in range(1, len(poly)): 1943 if _PointsEqual(poly[i-1], poly[i]): poly.pop(i) 1944 i = len(poly) -1 1945 while i > 0 and _PointsEqual(poly[i], poly[0]): 1946 poly.pop(i) 1947 i -= 1 1948 return poly 1949 1950def _OffsetInternal(polys, isPolygon, delta, jointype = JoinType.Square, endtype = EndType.Square, limit = 0.0): 1951 1952 def _DoSquare(pt): 1953 # see offset_triginometry.svg in the documentation folder ... 1954 dx = math.tan(math.atan2(sinA, 1955 Normals[k].x * Normals[j].x + Normals[k].y * Normals[j].y)/4) 1956 result.append(Point( 1957 round(pt.x + delta * (Normals[k].x - Normals[k].y *dx)), 1958 round(pt.y + delta * (Normals[k].y + Normals[k].x *dx)))) 1959 result.append(Point( 1960 round(pt.x + delta * (Normals[j].x + Normals[j].y *dx)), 1961 round(pt.y + delta * (Normals[j].y - Normals[j].x *dx)))) 1962 return 1963 1964 def _DoMiter(pt, r): 1965 q = delta / r 1966 result.append(Point( 1967 round(pt.x + (Normals[k].x + Normals[j].x) * q), 1968 round(pt.y + (Normals[k].y + Normals[j].y) * q))) 1969 return 1970 1971 1972 def _DoRound(pt): 1973 a = math.atan2(sinA, 1974 Normals[k].x * Normals[j].x + Normals[k].y * Normals[j].y) 1975 steps = round(step360 * abs(a)); 1976 X,Y = Normals[k].x, Normals[k].y 1977 for _ in range(steps): 1978 result.append(Point( 1979 round(pt.x + X * delta), round(pt.y + Y * delta))) 1980 X2 = X 1981 X = X * mcos - msin * Y 1982 Y = X2 * msin + Y * mcos 1983 result.append(Point(round(pt.x + Normals[j].x * delta), 1984 round(pt.y + Normals[j].y * delta))); 1985 return 1986 1987 def GetSin(): 1988 result = (Normals[k].x * Normals[j].y - Normals[j].x * Normals[k].y) 1989 if (result > 1.0): result = 1.0 1990 elif (result < -1.0): result = -1.0 1991 return result 1992 1993 def _OffsetPoint(jointype): 1994 if (sinA * delta < 0): 1995 result.append(Point(round(pts[j].x + Normals[k].x * delta), 1996 round(pts[j].y + Normals[k].y * delta))) 1997 result.append(pts[j]) 1998 result.append(Point(round(pts[j].x + Normals[j].x * delta), 1999 round(pts[j].y + Normals[j].y * delta))) 2000 elif jointype == JoinType.Miter: 2001 r = 1.0 + (Normals[j].x * Normals[k].x + Normals[j].y * Normals[k].y) 2002 if (r >= miterLim): _DoMiter(pts[j], r) 2003 else: _DoSquare(pts[j]) 2004 elif jointype == JoinType.Square: _DoSquare(pts[j]) 2005 else: _DoRound(pts[j]) 2006 return j 2007 2008 if delta == 0: return polys 2009 if not isPolygon and delta < 0: delta = -delta 2010 2011 if jointype == JoinType.Miter: 2012 # miterLim: see offset_triginometry3.svg in the documentation folder ... 2013 if limit > 2: miterLim = 2 / (limit * limit) 2014 else: miterLim = 0.5 2015 if endtype == EndType.Round: limit = 0.25 2016 2017 if jointype == JoinType.Round or endtype == EndType.Round: 2018 if limit <= 0: limit = 0.25 2019 elif limit > abs(delta)*0.25: limit = abs(delta)*0.25 2020 # step360: see offset_triginometry2.svg in the documentation folder ... 2021 step360 = math.pi / math.acos(1 - limit / abs(delta)) 2022 msin = math.sin(2 * math.pi / step360) 2023 mcos = math.cos(2 * math.pi / step360) 2024 step360 /= math.pi * 2 2025 if delta < 0: msin = -msin 2026 2027 res = [] 2028 ppts = polys[:] 2029 for pts in ppts: 2030 Normals = [] 2031 result = [] 2032 cnt = len(pts) 2033 2034 if (cnt == 0 or cnt < 3 and delta <= 0): continue 2035 2036 if (cnt == 1): 2037 if jointype == JoinType.Round: 2038 X,Y = 1.0, 0.0 2039 for _ in range(round(step360 * 2 * math.pi)): 2040 result.append(Point(round(pts[0].x + X * delta), 2041 round(pts[0].y + Y * delta))) 2042 X2 = X 2043 X = X * mcos - msin * Y 2044 Y = X2 * msin + Y * mcos 2045 else: 2046 X,Y = -1.0, -1.0 2047 for _ in range(4): 2048 result.append(Point(round(pts[0].x + X * delta), 2049 round(pts[0].y + Y * delta))) 2050 if X < 0: X = 1 2051 elif Y < 0: Y = 1 2052 else: X = -1 2053 continue 2054 2055 forceClose = _PointsEqual(pts[0], pts[cnt - 1]) 2056 if (forceClose): cnt -=1 2057 2058 for j in range(cnt -1): 2059 Normals.append(_GetUnitNormal(pts[j], pts[j+1])) 2060 if isPolygon or forceClose: 2061 Normals.append(_GetUnitNormal(pts[cnt-1], pts[0])) 2062 else: 2063 Normals.append(Normals[cnt-2]) 2064 2065 2066 if (isPolygon or forceClose): 2067 k = cnt - 1 2068 for j in range(cnt): 2069 sinA = GetSin() 2070 k = _OffsetPoint(jointype) 2071 res.append(result) 2072 2073 if not isPolygon: 2074 result = [] 2075 delta = -delta 2076 k = cnt - 1 2077 for j in range(cnt): 2078 sinA = GetSin() 2079 k = _OffsetPoint(jointype) 2080 delta = -delta 2081 res.append(result[::-1]) 2082 2083 else: 2084 # offset the polyline going forward ... 2085 k = 0; 2086 for j in range(1, cnt-1): 2087 sinA = GetSin() 2088 k = _OffsetPoint(jointype) 2089 2090 # handle the end (butt, round or square) ... 2091 if (endtype == EndType.Butt): 2092 j = cnt - 1 2093 pt1 = Point(round(float(pts[j].x) + Normals[j].x * delta), \ 2094 round(float(pts[j].y) + Normals[j].y * delta)) 2095 result.append(pt1) 2096 pt1 = Point(round(float(pts[j].x) - Normals[j].x * delta), \ 2097 round(float(pts[j].y) - Normals[j].y * delta)) 2098 result.append(pt1) 2099 else: 2100 j = cnt - 1; 2101 k = cnt - 2; 2102 Normals[j] = FloatPoint(-Normals[j].x, -Normals[j].y) 2103 if (endtype == EndType.Square): _DoSquare(pts[j]) 2104 else: _DoRound(pts[j]) 2105 2106 # re-build Normals ... 2107 for j in range(cnt -1, 0, -1): 2108 Normals[j] = FloatPoint(-Normals[j -1].x, -Normals[j -1].y) 2109 Normals[0] = FloatPoint(-Normals[1].x, -Normals[1].y) 2110 2111 # offset the polyline going backward ... 2112 k = cnt -1; 2113 for j in range(cnt -2, 0, -1): 2114 sinA = GetSin() 2115 k = _OffsetPoint(jointype) 2116 2117 # finally handle the start (butt, round or square) ... 2118 if (endtype == EndType.Butt): 2119 pt1 = Point(round(float(pts[0].x) - Normals[0].x * delta), \ 2120 round(float(pts[0].y) - Normals[0].y * delta)) 2121 result.append(pt1) 2122 pt1 = Point(round(float(pts[0].x) + Normals[0].x * delta), \ 2123 round(float(pts[0].y) + Normals[0].y * delta)) 2124 result.append(pt1) 2125 else: 2126 j = 0 2127 k = 1 2128 if (endtype == EndType.Square): _DoSquare(pts[0]) 2129 else: _DoRound(pts[0]) 2130 res.append(result) 2131 2132 2133 c = Clipper() 2134 c.AddPolygons(res, PolyType.Subject) 2135 if delta > 0: 2136 c.Execute(ClipType.Union, res, PolyFillType.Positive, PolyFillType.Positive) 2137 else: 2138 bounds = _GetBounds(res) 2139 outer = [] 2140 outer.append(Point(bounds.left-10, bounds.bottom+10)) 2141 outer.append(Point(bounds.right+10, bounds.bottom+10)) 2142 outer.append(Point(bounds.right+10, bounds.top-10)) 2143 outer.append(Point(bounds.left-10, bounds.top-10)) 2144 c.AddPolygon(outer, PolyType.Subject) 2145 c.ReverseSolution = True 2146 c.Execute(ClipType.Union, res, PolyFillType.Negative, PolyFillType.Negative) 2147 if len(res) > 0: res.pop(0) 2148 return res 2149 2150def OffsetPolygons(polys, delta, jointype = JoinType.Square, limit = 0.0, autoFix = True): 2151 if not autoFix: 2152 return _OffsetInternal(polys, True, delta, jointype, EndType.Butt, limit) 2153 pts = polys[:] 2154 botPoly = None 2155 botPt = None 2156 for poly in pts: 2157 poly = _StripDupPts(poly) 2158 if len(poly) < 3: continue 2159 bot = _GetLowestPt(poly) 2160 if botPt is None or (bot.y > botPt.y) or \ 2161 (bot.y == botPt.y and bot.x < botPt.x): 2162 botPt = bot 2163 botPoly = poly 2164 if botPt is None: return [] 2165 # if the outermost polygon has the wrong orientation, 2166 # reverse the orientation of all the polygons ... 2167 if Area(botPoly) < 0.0: 2168 for i in range(len(pts)): 2169 pts[i] = pts[i][::-1] 2170 return _OffsetInternal(pts, True, delta, jointype, EndType.Butt, limit) 2171 2172def OffsetPolyLines(polys, delta, jointype = JoinType.Square, endtype = EndType.Square, limit = 0.0): 2173 polys2 = polys[:] 2174 for p in polys2: 2175 if p == []: continue 2176 for i in range(1, len(p)): 2177 if _PointsEqual(p[i-1], p[i]): p.pop(i) 2178 2179 if endtype == EndType.Closed: 2180 for i in range(len(polys2)): 2181 polys2.append(polys2[i][::-1]) 2182 return _OffsetInternal(polys2, True, delta, jointype, EndType.Butt, limit) 2183 else: 2184 return _OffsetInternal(polys2, False, delta, jointype, endtype, limit) 2185 2186def _DistanceSqrd(pt1, pt2): 2187 dx = (pt1.x - pt2.x) 2188 dy = (pt1.y - pt2.y) 2189 return (dx*dx + dy*dy) 2190 2191def _ClosestPointOnLine(pt, linePt1, linePt2): 2192 dx = linePt2.x - linePt1.x 2193 dy = linePt2.y - linePt1.y 2194 if (dx == 0 and dy == 0): 2195 return FloatPoint(linePt1.x, linePt1.y) 2196 q = ((pt.x-linePt1.x)*dx + (pt.Y-linePt1.Y)*dy) / (dx*dx + dy*dy) 2197 return FloatPoint( 2198 (1-q)*linePt1.X + q*linePt2.X, 2199 (1-q)*linePt1.Y + q*linePt2.Y) 2200 2201def _SlopesNearColinear(pt1, pt2, pt3, distSqrd): 2202 if _DistanceSqrd(pt1, pt2) > _DistanceSqrd(pt1, pt3): return False 2203 cpol = _ClosestPointOnLine(pt2, pt1, pt3); 2204 dx = pt2.x - cpol.x 2205 dy = pt2.y - cpol.y 2206 return (dx*dx + dy*dy) < distSqrd 2207 2208def _PointsAreClose(pt1, pt2, distSqrd): 2209 dx = pt1.x - pt2.x 2210 dy = pt1.y - pt2.y 2211 return (dx * dx) + (dy * dy) <= distSqrd 2212 2213def CleanPolygon(poly, distance = 1.415): 2214 distSqrd = distance * distance 2215 highI = len(poly) -1 2216 while (highI > 0 and _PointsEqual(poly[highI], poly[0])): highI -= 1 2217 if (highI < 2): return [] 2218 pt = poly[highI] 2219 result = [] 2220 i = 0 2221 while True: 2222 while (i < highI and _PointsAreClose(pt, poly[i+1], distSqrd)): i +=2 2223 i2 = i 2224 while (i < highI and (_PointsAreClose(poly[i], poly[i+1], distSqrd) or \ 2225 _SlopesNearColinear(pt, poly[i], poly[i+1], distSqrd))): i +=1 2226 if i >= highI: break 2227 elif i != i2: continue 2228 pt = poly[i] 2229 i +=1 2230 result.append(pt) 2231 2232 if (i <= highI): result.append(poly[i]) 2233 j = len(result) 2234 if (j > 2 and _SlopesNearColinear(result[j-2], result[j-1], result[0], distSqrd)): 2235 del result[j-1:] 2236 if len(result) < 3: return [] 2237 else: return result 2238 2239def CleanPolygons(polys, distance = 1.415): 2240 result = [] 2241 for poly in polys: 2242 result.append(CleanPolygon(poly, distance = 1.415)) 2243 return result 2244 2245def SimplifyPolygon(poly, fillType): 2246 result = [] 2247 c = Clipper(); 2248 c.ForceSimple = True 2249 c.AddPolygon(poly, PolyType.Subject); 2250 c.Execute(ClipType.Union, result, fillType, fillType) 2251 return result 2252 2253def SimplifyPolygons(polys, fillType): 2254 result = [] 2255 c = Clipper(); 2256 c.ForceSimple = True 2257 c.AddPolygons(polys, PolyType.Subject); 2258 c.Execute(ClipType.Union, result, fillType, fillType) 2259 return result 2260