On Mon, 2010-06-07 at 11:21 +0200, Armin Faltl wrote: > Peter Clifton wrote: > > The plugin now works to construct a tree ordered by "containership" - > > and processes the relevant contours in an appropriate order so outer > > contours are processed before inner ones. > > > How do you determine containership?
Now you're asking me a HARD question.... ;) polygoncombine.c defines a helper function, PolygonContainsPolygon() which is supposed to compute the "correct" result. As a cheat (which seemed to work), I make this simply: static bool PolygonContainsPolygon (POLYAREA *outer, POLYAREA *inner) { return poly_ContourInContour (outer->contours, inner->contours); } (Which is a function in polygon1.c). Note that I'm _assuming_ the input polygons to "combinepolygon" only have a single contour, since poly_ContourInContour() only operates on the FIRST contour in the linked list passed. (I think). I'm not entirely sure how I'd go about writing this test if I were working with complex polygons. poly_ContourInContour, however, makes a big assumption: That the caller _knows_ the contours it is asking about don't INTERSECT. If they _do_ intersect, the result from the function is undetermined. (e.g. Random, based upon implementation details.) In our case, I can guess that the contours won't intersect (for "normal" input data), but I don't KNOW they don't intersect. (Debug output suggests that some "might" in the example I posted). Fortunately, it doesn't _really_ matter if we get a bad report for containership between two intersecting contours, so I've not bothered proving the contours don't intersect. poly_ContourInContour() works like this: 1. Check bounding boxes as a quick way of throwing out a false answer 2. Pick the first point on the contour we're testing to be "inside" the "outer" contour, and run a test to prove it is not outside that. This is done with a call to poly_InsideContour(). 3. Compute a point which is inside the "inside" contour, and away from its edges. Test _that_ point, to prove it is not outside the "outside" contour. (This avoids a false result if the two contours are separate, but the point tested in step 2 shares a point with the "outer" contour). The inside / outside testing in poly_InsideContour() works by casting a ray in a particular direction from the point being outwards, and counting intersections between that ray and polygon edges. I hope that was enlightening.. I hope this was the kind of explanation you were after. Let me know if you wanted any other details, and I'll try to fill them in. Best regards, -- Peter Clifton Electrical Engineering Division, Engineering Department, University of Cambridge, 9, JJ Thomson Avenue, Cambridge CB3 0FA Tel: +44 (0)7729 980173 - (No signal in the lab!) Tel: +44 (0)1223 748328 - (Shared lab phone, ask for me) _______________________________________________ geda-user mailing list geda-user@moria.seul.org http://www.seul.org/cgi-bin/mailman/listinfo/geda-user