zhanglz95 / wapy

Python implementation of polygon clipping algorithm

WApy(Weiler-Atherton clipping algorithm in python)

This rep is python implementation of Weiler-Atherton clipping algorithm.

Reference:https://www.cnblogs.com/lsxqw2004/p/4843417.html

Reference rep:https://github.com/lsxqw2004/blog_sample_codes

How to use?

Just copy the python file into the path of your project and import:

from PolygonCut import *

The two Polygons you input should be like this:

#"x y x y ... x y" in clockwise by Default, otherwise transform to clockwise
S = "161 137 429 376 558 192 619 418 281 431"
C = "183 391 224 240 610 107 657 361 429 376"

Then get the clipped Polygons:

result = PolyClipping(S, C)			# True by default
#result = PolyClipping(S, C, False) # if you want anticlockwise output

The format of result should be like this:

#"x y x y ... x y" in clockwise by Default
["261.867222 226.952486 429.000000 376.000000 262.690141 386.140845 215.627162 270.836548 224.000000 240.000000",
"429.000000 376.000000 558.000000 192.000000 604.546479 364.450890"]

Moreover： The coordinate frame is:

------------------------------------>x+
|
|
|
|
|
|
|
|
|
v
y+

wapy's Issues

发现了一个bug并进行了修改

当两个多边形有顶点重合时，程序将陷入死循环，例如：
S = "242 78 480 77 480 289 242 289"
C = "180 20 480 77 440 260 180 231"

代码修改：
line 531, 插入
inters_len = []
s1_next_list = []

line 563，插入
s1_next_list.append(s1.next)

line 568，插入

#如果S和C有重合的点
inters_len.append(len(inters))
if (len(listI) >= 2 and floatEqual(inters[0].x, listI[len(listI)-inters_len[-1]-1].x)
                           and floatEqual(inters[0].y, listI[len(listI)-inters_len[-1]-1].y)):
       curr = inters[0]
       last = listI[len(listI)-inters_len[-1]-1]
       curr_next = curr.nextS if curr.crossDi == 0 else curr.nextC
       last_next = last.nextS if last.crossDi == 0 else last.nextC
       #做叉乘
        if (curr_next.x-inters[0].x)*(last_next.y-inters[0].y) - \
           (last_next.x-inters[0].x)*(curr_next.y-inters[0].y) > 0:
                    
            listI[len(listI)-inters_len[-1]-2].nextS.crossDi = 0
        else:
            listI.pop(-inters_len[-1]-1)
            # 替换上一个s的next
            listC[cutStartIdx-1].next = s1
            if inters_len[-2] > 1:
                listI[-inters_len[-1]-1].nextC = inters[0]

Infinite loop

These two polygons produce an infinite loop. Figure attached

p1 = [(30.46125586693899, 41.985513507992174), 
        (30.3575578768862, 41.72616095904533), 
        (29.852017536972905, 40.3553403553245), 
        (29.748319546920115, 40.05894220558392), 
        (28.983522565558335, 38.66959324515582), 
        (29.074263167854276, 38.521399727780555), 
        (29.255736594763672, 38.24352993553698), 
        (29.709431828422733, 38.20648433474324), 
        (30.09830901298205, 38.910417436605655), 
        (30.39644559538358, 39.44762866280602), 
        (30.78532277994289, 40.281238039536724), 
        (30.979761372153472, 40.651738505854844), 
        (32.78156158653803, 42.50419637669552), 
        (33.338947032843706, 43.05993596118266), 
        (33.27413676115014, 43.35633411092324),
         (33.22228387735157, 43.67124950396056),
          (32.40564178973557, 45.72748596545732), 
          (32.094540042171005, 45.227320340050696), 
          (31.6019648675589, 44.17141512936718), 
          (31.329750838353565, 43.726823462251325), 
          (31.187165129803393, 43.46748202750477), (30.72051250838748, 42.46715077590178), (30.46125586693899, 41.985513507992174)] 
    p2 = [(28.607610546300204, 51.118159933876896), (28.81501430395013, 50.2104593555587), (28.905747128701734, 49.895532848321096), (28.970565177801483, 49.65471977107156), (29.12611605165284, 49.06192347159039), (29.307589478562235, 46.72781721785007), (29.281666925366043, 46.43143018230977), (29.152038604710878, 44.801257030431856), (29.17796115790707, 44.48634163739454), (29.20389148850944, 43.94911929620413), (29.22981404156748, 43.7083062189546), (29.139073439409692, 40.040424963076944), (29.696466663121548, 40.02189660479017), (31.627887420616936, 39.52173097938355), (32.41860695517491, 39.63287889596508), (32.65193326588287, 45.227320340050696), (32.44452950823295, 45.50519013229426), (32.54823527583007, 52.69275912746405), (32.535270110528884, 52.80390704404557), (32.14639292596957, 57.435073951522234), (32.14639292596957, 57.52769351060674), (32.71674353743828, 60.5472156237025), (32.82044930503541, 60.75098310015829), (33.170438771097345, 62.28852557796165), (33.131551052738125, 62.418201852829945), (32.976000178886764, 62.529349769411475), (32.690820984380245, 62.696071645073516), (30.65569445928773, 59.58392997289325), (29.90387042077147, 58.87999687103084), (29.696466663121548, 58.69474663787178), (29.4372177992174, 58.342774529840426), (29.268701760064857, 58.08343309509388), (29.12611605165284, 57.861137261141074), (27.907631614038177, 56.30506642505094), (27.81689101188039, 55.95309431701959), (27.739115574885634, 55.71228124055981), (27.739115574885634, 55.13801329857565), (27.84282134248276, 54.50817139751098), (28.024294769392156, 53.47079454511424), (28.089105041085727, 53.11882243708289), (28.192810808682854, 52.766861443251834), (28.25762108023827, 52.52603725180201), (28.37428423559225, 51.933252067310875), (28.55575766250164, 51.34045576703995), (28.607610546300204, 51.118159933876896)]

发现bug并做了修改