## Re: [Algorithms] Weiler Atherton Implementation (2D polygon clipping)

 Re: [Algorithms] Weiler Atherton Implementation (2D polygon clipping) From: Andrew Willmott - 2005-05-30 19:50:21 ```The short version: WA is not a practical, robust algorithm. This is not a problem you can solve. The long version: a friend of mine was working on 2D clipping algorithms for his Master's thesis. He ran into exactly the same problems you describe, and spent a lot of time trying to fix them. He eventually got in touch with one of the paper authors, and established that their code had the same set of problems. It was a nice algorithm in theory, but it inevitably ran into robustness issues in practice. He went on to write his own, which was based off a BSP tree approach, I think. (I might be wrong about that -- this was all over ten years ago, and I can't find his thesis online. It was "Object-precision methods for visible surface determination", J. Williams, University of Auckland..) Andrew pierloic@... wrote: >Hello, > >I am implementing the Weiler Atherton algorithm as it really matches my needs >for some physic dev: >- concave with holes polygon clipped with concave with holes polygon >- the algorithm outputs 2 lists: inside polygons and outside polygons >- ability to use results as inputs for several passes > >You can find the original article here : >http://www.cs.drexel.edu/~david/Classes/CS430/HWs/p214-weiler.pdf > > >The general cases works really good but it is getting harder with the >pathological cases when some intersections points happens to be the same as >some polygon points: >- 2 non parallel edges intersect on one end of one edge >- 2 non parallel edges intersect on one end of one edge which is also an end of >the other edge >- 2 parallel edges intersect on two points which are end of edges > >I tried different ways to treat them (insert intersection nodes or not) but >nothing really works for the moment. > >The paper is quite "vague" about it : >"If care is taken in placement of intersections where the subject and clip >polygon contours are identical in the x-y plane, no degenerate polygons will be >produced by the clipping process" > >Then the text makes two assertions : >"These two types of intersections will be found to alternate along any given >contour and the number of intersections will always be even" > >I cant satisfy these two assertions with the different approaches i tried for >the pathological cases... > >Anyone has experimented these issues ? Any help is welcome. > >Thanks, >-- >Pierre Loic Herve > > >------------------------------------------------------- >SF.Net email is sponsored by: GoToMeeting - the easiest way to collaborate >online with coworkers and clients while avoiding the high cost of travel and >communications. There is no equipment to buy and you can meet as often as >you want. Try it free.http://ads.osdn.com/?ad_idt02&alloc_id135&op=click >_______________________________________________ >GDAlgorithms-list mailing list >GDAlgorithms-list@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_ida88 > > ```

 [Algorithms] Weiler Atherton Implementation (2D polygon clipping) From: - 2005-05-26 13:21:23 ```Hello, I am implementing the Weiler Atherton algorithm as it really matches my n= eeds for some physic dev: - concave with holes polygon clipped with concave with holes polygon - the algorithm outputs 2 lists: inside polygons and outside polygons - ability to use results as inputs for several passes You can find the original article here : http://www.cs.drexel.edu/~david/Classes/CS430/HWs/p214-weiler.pdf The general cases works really good but it is getting harder with the pathological cases when some intersections points happens to be the same = as some polygon points: - 2 non parallel edges intersect on one end of one edge - 2 non parallel edges intersect on one end of one edge which is also an = end of the other edge - 2 parallel edges intersect on two points which are end of edges I tried different ways to treat them (insert intersection nodes or not) b= ut nothing really works for the moment. The paper is quite "vague" about it : "If care is taken in placement of intersections where the subject and cli= p polygon contours are identical in the x-y plane, no degenerate polygons w= ill be produced by the clipping process" Then the text makes two assertions : "These two types of intersections will be found to alternate along any gi= ven contour and the number of intersections will always be even" I cant satisfy these two assertions with the different approaches i tried= for the pathological cases... Anyone has experimented these issues ? Any help is welcome. Thanks, -- Pierre Loic Herve ```
 Re: [Algorithms] Weiler Atherton Implementation (2D polygon clipping) From: Andrew Willmott - 2005-05-30 19:50:21 ```The short version: WA is not a practical, robust algorithm. This is not a problem you can solve. The long version: a friend of mine was working on 2D clipping algorithms for his Master's thesis. He ran into exactly the same problems you describe, and spent a lot of time trying to fix them. He eventually got in touch with one of the paper authors, and established that their code had the same set of problems. It was a nice algorithm in theory, but it inevitably ran into robustness issues in practice. He went on to write his own, which was based off a BSP tree approach, I think. (I might be wrong about that -- this was all over ten years ago, and I can't find his thesis online. It was "Object-precision methods for visible surface determination", J. Williams, University of Auckland..) Andrew pierloic@... wrote: >Hello, > >I am implementing the Weiler Atherton algorithm as it really matches my needs >for some physic dev: >- concave with holes polygon clipped with concave with holes polygon >- the algorithm outputs 2 lists: inside polygons and outside polygons >- ability to use results as inputs for several passes > >You can find the original article here : >http://www.cs.drexel.edu/~david/Classes/CS430/HWs/p214-weiler.pdf > > >The general cases works really good but it is getting harder with the >pathological cases when some intersections points happens to be the same as >some polygon points: >- 2 non parallel edges intersect on one end of one edge >- 2 non parallel edges intersect on one end of one edge which is also an end of >the other edge >- 2 parallel edges intersect on two points which are end of edges > >I tried different ways to treat them (insert intersection nodes or not) but >nothing really works for the moment. > >The paper is quite "vague" about it : >"If care is taken in placement of intersections where the subject and clip >polygon contours are identical in the x-y plane, no degenerate polygons will be >produced by the clipping process" > >Then the text makes two assertions : >"These two types of intersections will be found to alternate along any given >contour and the number of intersections will always be even" > >I cant satisfy these two assertions with the different approaches i tried for >the pathological cases... > >Anyone has experimented these issues ? Any help is welcome. > >Thanks, >-- >Pierre Loic Herve > > >------------------------------------------------------- >SF.Net email is sponsored by: GoToMeeting - the easiest way to collaborate >online with coworkers and clients while avoiding the high cost of travel and >communications. There is no equipment to buy and you can meet as often as >you want. Try it free.http://ads.osdn.com/?ad_idt02&alloc_id135&op=click >_______________________________________________ >GDAlgorithms-list mailing list >GDAlgorithms-list@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_ida88 > > ```