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