Re: gEDA-user: PCB+GL Branches: URGENT WARNING

[Peter Clifton <pcjc2@xxxxxxxxx>]

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