From: Bretton Wade <brettonw@mi...>  20050531 08:45:12

(Despite my experience in this area, I continue to believe that object space algorithms like this can be made to work. It's my masochistic tendencies showing through.) As a general rule, clipping algorithms on complex geometry are not robust and accurate with floating point math.=20 In any large enough data set, you will find at least one unexpected special case that you must solve. The last two assertions you claim to have trouble with (types of intersections will alternate and the number will always be even) are implications of the Jordan curve theorem (Any continuous simple closed curve in the plane separates the plane into two disjoint regions: the inside and the outside.) You have to make these work in order to be sure the clipper is correct. If this is for offline processing, use arbitrary precision arithmetic to eliminate a major source of accuracy errors. It will be slow, but the alternative is manually examining thousands of failure cases. BSP based clipping is no better than the WeilerAtherton algorithm in the long run; it's just easier to code the operations. Unfortunately it will also give you more polygons, meaning more opportunities for error. I implemented the Sutherland and Hodgman algorithm a few years back for offline processing of water polygons in Flight Simulator. Polys with holes were clipped only to quads, and I had a @$%$ of a time getting that robust across the entire world.=20 Here are a few suggestions: 1) Be careful about testing for equality. This comes up in the collocation and collinear testing a lot. Epsilon testing is a generally accepted method for comparison of floats [abs(ab)<epsilon], but breaks down if epsilon is meaningless in the range of numbers you are working in. A better test is looking for least significant bits of deviation (typecast the floats to ints, and compare the result to less than some small enough integer tolerance). 2) Error check your input religiously. You want polygon chains that are simple, have no collinear or collocated vertices, have area greater than 0, etc., etc. Do all this conditioning before you feed the clipper, not while you feed it. Punt on any polygon that isn't well conditioned. 3) Skip the alternative winding order hole polygon approach if you can. I inserted the hole polygon into the source polygons and updated the test for simpleness to allow collinear edges in the polygon. This removes one major source of complexity from the algorithm. 4) Isolate your intersection routines so that they always order line segments the same way. This ensures that you get the same intersection point whether you are considering AB intersects CD, or CD intersects AB (or DC intersects BA...) 5) To make the Jordan curve theorem hold, I found that I had to sort the intersections along the clipping plane and fudge it if I got multiple intersection points that appeared to be collocated. Basically the sort routine had to enforce the alternating nature of the intersection points. If you keep going down this road... Good luck and please report back on your results. Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Andrew Willmott Sent: Monday, May 30, 2005 12:51 PM To: gdalgorithmslist@... Subject: Re: [Algorithms] Weiler Atherton Implementation (2D polygon clipping) The short version: WA is not a practical, robust algorithm. This is not=20 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=20 describe, and spent a lot of time trying to fix them. He eventually got=20 in touch with one of the paper authors, and established that their code=20 had the same set of problems. It was a nice algorithm in theory, but it=20 inevitably ran into robustness issues in practice. He went on to write=20 his own, which was based off a BSP tree approach, I think. (I might be=20 wrong about that  this was all over ten years ago, and I can't find=20 his thesis online. It was "Objectprecision methods for visible surface=20 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/p214weiler.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 xy 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=16135&op=3Dclick >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_ida88 > =20 >  This SF.Net email is sponsored by Yahoo. Introducing Yahoo! Search Developer Network  Create apps using Yahoo! Search APIs Find out how you can build Yahoo! directly into your own Applications  visit http://developer.yahoo.net/?fr=3Doffadysdnostgq22005 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 