Re: gEDA-user: Polygon combiner plugin

[Peter Clifton <pcjc2@xxxxxxxxx>]

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@xxxxxxxxxxxxxx
http://www.seul.org/cgi-bin/mailman/listinfo/geda-user