Re: gEDA-user: Polygon combiner plugin

[Peter Clifton <pcjc2@xxxxxxxxx>]

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