On Mon, 2010-06-07 at 14:37 +0200, Armin Faltl wrote: > The answer was enlightening, though I'd have to do a lot more thinking about > why it doesn't matter, if some polygons are intersecting.
Not necessarily that the result doesn't matter, rather - that the "correct" result is not so easily defined in the first place. From what I could tell, pstoedit emits mostly non-intersecting contours. > If a polygone is complex, i.e. has holes, the cast ray will pass an odd > number > of edges, if the start point is inside the polygon. Numerically > difficult is the > case, if the ray scratches a corner. I assume, your ray is an axe-direction > and you sort the edges before checking hits or something. So if an > interval-test > shows, that it's a corner and you are lucky to have a minimal delta from > previous edge-sorting, you may slightly offset the start point along an edge > and rerun the test (the sorting delta is a bound for the offset?). I'm not sure.. I didn't write that code, it is part of PCB's polygon1.c which Harry Eaton wrote (based upon the excellent work and code of some researchers who studied polygon algorithms). > Hm - many polygons are axe-aligned, so a ray in a rather random direction > is much less likely to produce corner cases. Otoh, when using an axe-aligned > ray, the intersection test for an edge degenerates to an > interval-inclusion and > a true intersection only if this hits, so rotating the input beforehand > (say 1 rad) may be desirable ;-) The direction it still pretty arbitrary though, so in general it doesn't help. I "think" PCB's code is known to work in the degenerate cases for this particular test. (There are others it can fail on though, due to numerical precision). -- 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 [email protected] http://www.seul.org/cgi-bin/mailman/listinfo/geda-user
