On Thu, 2010-03-18 at 15:09 +0000, Peter Clifton wrote: > Dear all, > > It has come to my attention that my PCB+GL branches (starting from > "polygon_speedup" onwards, contain a flaw which can in some > circumstances result in subtly corrupted polygons - which can in turn > ruin a finished board's connectivity.
Looks like this is due to poly_ContourInContour sometimes mistakenly returning TRUE for touching contours. My sped-up polygon handling code didn't appreciate that much. I've not yet identified whether this issue can cause bugs in the git HEAD polygon handling. The attached patch fixes the issue, but is painfully slow. Can anyone suggest a better (faster) test for contour inside-ness which doesn't sometimes return a false positive for touching contours? [snip] > In src/polygon.c, you will find two lines: > > #define SUBTRACT_PIN_VIA_BATCH_SIZE 100 > #define SUBTRACT_LINE_BATCH_SIZE 1 > > (Older versions of my branches had line batch size > 1, but I cut back > to 1 due to a similar bug). "Similar", but sadly unrelated. No magic bullet today.. the line issue is (possibly) due to the gathering routines taking a wrong turn in the infinitesimally touching case where various holes share edges. I don't "think" it is a numerical stability / intersection topology issue, rather errors in our / my handling of limiting cases. > Change these to read: > > #define SUBTRACT_PIN_VIA_BATCH_SIZE 1 > #define SUBTRACT_LINE_BATCH_SIZE 1 > > > It appears this will work-around the issue for cases I've encountered, > but unfortunately it will slow down polygon processing. For those looking to _use_ my branches, I'd recommend the above workaround rather than re-fetching my branches with the attached patch applied. The patch causes a huge slow-down due to its more obsessive testing. -- 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)
>From 5f8db06c35fabaeb29382f36cd3a1deaaaeac31d Mon Sep 17 00:00:00 2001 From: Peter Clifton <pc...@cam.ac.uk> Date: Thu, 18 Mar 2010 20:43:58 +0000 Subject: [PATCH] Fix poly_ContourInContour() test not to return TRUE for touching contours This test could previously return true for touching contours, such as: __________.... |_________ | : :........ || : :: /\ : || : Note that the bounding box of A is inside that of B, :: / \ :/ \ : such that initial bounding box checks won't reject the ::/ A \/ B \: possibility of A being inside B. ::\ /\ /: :: \ / :\ / : ::..\/..:.\/..: When testing for insideness, the first point on A's contour is picked. In this case, unfortunately being the touching X point between the two contours. This point (correctly) returns as being inside B - and the false presumption is that the whole A contour is inside B. This commit introduces an unfortunately slow, but more robust test, where we check each note in A for whether it is inside B. We return as soon as we find an A node outside B, however this means the test is VERY much slower for the case where A _is_ inside B. --- src/polygon1.c | 15 ++++++++++++++- 1 files changed, 14 insertions(+), 1 deletions(-) diff --git a/src/polygon1.c b/src/polygon1.c index d9f6ce4..11e6146 100644 --- a/src/polygon1.c +++ b/src/polygon1.c @@ -2257,10 +2257,23 @@ poly_M_CheckInside (POLYAREA * p, Vector v0) int poly_ContourInContour (PLINE * poly, PLINE * inner) { + VNODE *pt; assert (poly != NULL); assert (inner != NULL); if (cntrbox_inside (inner, poly)) - return poly_InsideContour (poly, inner->head.point); + { /* FIXME: This is SLOW!! + * Check all points on the contour being tested, because we don't + * want to falsely return that two contours are inside each other + * if they just touch at a few points. + */ + pt = &inner->head; + do + { + if (!poly_InsideContour (poly, pt->point)) + return 0; + } while ((pt = pt->next) != &inner->head); + return 1; + } return 0; } -- 1.7.0
_______________________________________________ geda-user mailing list geda-user@moria.seul.org http://www.seul.org/cgi-bin/mailman/listinfo/geda-user