On 2009-12-21 18:40-0800 Alan W. Irwin wrote: > There are additional -DFILL_INTERSECTION_POLYGON=ON issues for page 3 and > above of example 25, but I feel I am finally beginning to get close to the > end of this mini-project.
Now that I have the basic recursive algorithm working (as of revision 10731) I thought I should review what it does. The idea is a simple one. There is a preparation routine that transforms and swaps (if necessary) polygon 1 and polygon 2 so they are both positively oriented (interior on the left when traversing the vertices in ascending index order), and polygon 1 is known to start outside polygon 2. Then there is a recursion routine that preserves these properties, and which systematically moves through the edges of polygon 1 until two crossings with the edges of polygon 2 are encountered. Then polygon 2 is split at the path between the two crossings (that path must be interior to polygon 2 because of the requirement that polygon 1 starts outside polygon 2). Split 1 is on the "left" and thus must have at least some joint area with polygon 1 that must be filled adjacent to the path that is used to split polygon 2. Split 2 is on the "right" and must therefore have some joint area with polygon 1 that must _not_ be filled adjacent to the path that is used to split polygon 2. The routine is then called recursively where polygon 1 is the same and polygon 2 is first taken as split 1 then as split 2. As the recursion depth increases, the polygons get more complex, but the number of crossings is systematically eliminated until at depth there are no crossings between polygons 1 and 2 and therefore polygon 2 is either completely inside polygon 1 or completely disjoint from it. The current results are that if I locally adjust the clipping limits for example 25 to avoid crossings near polygon vertices, I get good results for the first four pages which gives me some confidence that the basic algorithm is working. My understanding is Arjen is working on adding another particularly fiendish polygon to example 25, and I am very much interested to see how well the recursive algorithm does in that case. ToDo: * Deal with crossings near polygon vertices. * Deal with rare cases where one of the original polygons is inscribed inside the other with lots of boundary touching, but no definite crossings. * Expand the preparation routine to deal with self-intersecting polygons, and the case where two successive edges are parallel with each other. Alan __________________________ Alan W. Irwin Astronomical research affiliation with Department of Physics and Astronomy, University of Victoria (astrowww.phys.uvic.ca). Programming affiliations with the FreeEOS equation-of-state implementation for stellar interiors (freeeos.sf.net); PLplot scientific plotting software package (plplot.org); the libLASi project (unifont.org/lasi); the Loads of Linux Links project (loll.sf.net); and the Linux Brochure Project (lbproject.sf.net). __________________________ Linux-powered Science __________________________ ------------------------------------------------------------------------------ This SF.Net email is sponsored by the Verizon Developer Community Take advantage of Verizon's best-in-class app development support A streamlined, 14 day to market process makes app distribution fast and easy Join now and get one step closer to millions of Verizon customers http://p.sf.net/sfu/verizon-dev2dev _______________________________________________ Plplot-devel mailing list Plplot-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/plplot-devel
