Fix inconsistent merging of asymmetric hole overlaps.

When computing the overlap relation between holes with different
sizes, the current search may not find all overlaps in the case
where a smaller hole is visited before a larger one, because
searching for holes within the radius of the smaller hole could
potentially not find the larger one.

The search procedure is altered slightly in order to solve this.
First, we begin the search by looking at holes in descending tool
diameter, to give a known upper bound at each stage.

Then we find potential overlaps by finding all holes within this
upper bound, and select the results that actually overlap.

diff --git a/src/slotifier.c b/src/slotifier.c
index 3998926e490c15bb94eb884d602a5fba8c112ed5..05ede6b70192b97da4bbffdf584f7d9d5e1530aa 100644 (file)
--- a/src/slotifier.c
+++ b/src/slotifier.c
@@ -193,15 +193,43 @@ static CNearTreeHandle build_search_tree(gerbv_image_t *drill)
        return t;
 }
 
+static gerbv_aperture_type_t tool_type(gerbv_image_t *drill, int aperture)
+{
+       gerbv_aperture_t *tool = drill->aperture[abs(aperture)];
+
+       return tool->type;
+}
+
+static double tool_radius(gerbv_image_t *drill, int aperture)
+{
+       gerbv_aperture_t *tool = drill->aperture[abs(aperture)];
+
+       /* Half a mil slop to decisively include points on boundary. */
+       return tool->parameter[0] / 2.0 + 0.0005;
+}
+
+static int holes_overlap(gerbv_image_t *drill, gerbv_net_t *a, gerbv_net_t *b)
+{
+       double d = hypot(a->start_x - b->start_x, a->start_y - b->start_y);
+
+       return tool_radius(drill, a->aperture) >= d
+           || tool_radius(drill, b->aperture) >= d;
+}
+
 static int combine_holes(gerbv_image_t *drill, gerbv_net_t *hole,
                          CNearTreeHandle t)
 {
-       int biggest_tool = hole->aperture;
        CVectorHandle group, tmp;
-       gerbv_aperture_t *tool;
-       int ret = -1;
+       int biggest_tool, ret = -1;
+       double biggest_r;
        size_t i, j;
 
+       /*
+        * Since we consider holes in order of decreasing size, the initial hole
+        * considered is by definition the biggest one we will find in a group.
+        */
+       biggest_r = tool_radius(drill, (biggest_tool = hole->aperture));
+
        if (CVectorCreate(&group, sizeof (gerbv_net_t *), 10)) {
                fprintf(stderr, _("%s: failed to allocate memory\n"), progname);
                return -1;
@@ -221,22 +249,15 @@ static int combine_holes(gerbv_image_t *drill, gerbv_net_t *hole,
        hole->aperture = -hole->aperture;
 
        for (i = 0; i < CVectorSize(group); i++) {
-               double xy[2], dia, r;
+               double xy[2];
 
                CVectorGetElement(group, &hole, i);
-               tool = drill->aperture[abs(hole->aperture)];
-               assert(tool->type == GERBV_APTYPE_CIRCLE);
-
-               xy[0] = hole->start_x; xy[1] = hole->start_y;
-               dia = tool->parameter[0];
-
-               /* Half a mil slop to decisively include points on boundary. */
-               r = dia/2 + 0.0005;
 
-               if (drill->aperture[biggest_tool]->parameter[0] < dia)
-                       biggest_tool = abs(hole->aperture);
+               assert(tool_type(drill, hole->aperture) == GERBV_APTYPE_CIRCLE);
+               assert(tool_radius(drill, hole->aperture) <= biggest_r);
 
-               if (CNearTreeFindInSphere(t, r, 0, tmp, xy, 1) != 0) {
+               xy[0] = hole->start_x; xy[1] = hole->start_y;
+               if (CNearTreeFindInSphere(t, biggest_r, 0, tmp, xy, 1) != 0) {
                        /* We should always should find at least one hole! */
                        fprintf(stderr, _("%s: fatal error searching holes\n"),
                                        progname);
@@ -248,13 +269,18 @@ static int combine_holes(gerbv_image_t *drill, gerbv_net_t *hole,
                         * of pointers to its internal copies of pointers
                         * to the objects in the tree.  So we need this
                         * double indirection to get the actual hole. */
+                       gerbv_net_t *newhole;
                        void *p;
+
                        CVectorGetElement(tmp, &p, j);
-                       hole = *(void **)p;
+                       newhole = *(void **)p;
+
+                       if (newhole->aperture < 0)
+                               continue; /* already visited */
 
-                       if (hole->aperture >= 0) {
-                               CVectorAddElement(group, &hole);
-                               hole->aperture = -hole->aperture;
+                       if (holes_overlap(drill, hole, newhole)) {
+                               CVectorAddElement(group, &newhole);
+                               newhole->aperture = -newhole->aperture;
                        }
                }
        }
@@ -318,10 +344,38 @@ err:
        return ret;
 }
 
+/*
+ * Order two holes by hole diameter.
+ */
+static gerbv_image_t *hsc_drill_data;
+static int hole_size_cmp(const void *a_, const void *b_)
+{
+       gerbv_net_t * const *a = a_, * const *b = b_;
+       gerbv_aperture_t *ta, *tb;
+
+       ta = hsc_drill_data->aperture[abs(a[0]->aperture)];
+       assert(ta->type == GERBV_APTYPE_CIRCLE);
+
+       tb = hsc_drill_data->aperture[abs(b[0]->aperture)];
+       assert(tb->type == GERBV_APTYPE_CIRCLE);
+
+       if (ta->parameter[0] > tb->parameter[0])
+               return -1;
+       if (ta->parameter[0] < tb->parameter[0])
+               return 1;
+       return 0;
+}
+
+static void sort_holes_by_size(gerbv_image_t *drill, CVectorHandle work)
+{
+       hsc_drill_data = drill;
+       qsort(work->array, work->size, work->elementsize, hole_size_cmp);
+}
+
 static int slotify(gerbv_image_t *drill)
 {
+       CVectorHandle holes, work;
        CNearTreeHandle t;
-       CVectorHandle holes;
        int ret = 0;
        size_t i;
 
@@ -334,18 +388,32 @@ static int slotify(gerbv_image_t *drill)
 
        CNearTreeObjects(t, &holes);
        if (!holes)
-               goto out;
+               goto err_free_tree;
 
-       for (i = 0; i < CVectorSize(holes); i++) {
+       if (CVectorCreate(&work, sizeof (gerbv_net_t *), CVectorSize(holes))) {
+               fprintf(stderr, _("%s: failed to allocate memory\n"), progname);
+               goto err_free_tree;
+       }
+
+       memcpy(work->array, holes->array, holes->size * holes->elementsize);
+       work->size = holes->size;
+       sort_holes_by_size(drill, work);
+
+       for (i = 0; i < CVectorSize(work); i++) {
                gerbv_net_t *hole;
 
-               CVectorGetElement(holes, &hole, i);
+               CVectorGetElement(work, &hole, i);
                /* Skip holes we've already looked at */
                if (hole->aperture < 0)
                        continue;
                if (hole->aperture_state == GERBV_APERTURE_STATE_ON)
                        continue;
 
+               if (verbose > 1) {
+                       fprintf(stderr, _("%s: checking hole at (%.4f,%.4f) for overlaps\n"),
+                                       progname, hole->start_x, hole->start_y);
+               }
+
                if (combine_holes(drill, hole, t) < 0) {
                        ret = -1;
                        break;
@@ -361,7 +429,8 @@ static int slotify(gerbv_image_t *drill)
                        gerbv_image_delete_net(hole);
        }
 
-out:
+       CVectorFree(&work);
+err_free_tree:
        CNearTreeFree(&t);
        return ret;
 }

diff --git a/tests/simple.at b/tests/simple.at
index 11c59b7bc8de9c871098eb7280fb0aa24f58998f..748a4bfbd7dce06417da3b7ae8121c426512183f 100644 (file)
--- a/tests/simple.at
+++ b/tests/simple.at
@@ -110,3 +110,65 @@ M30
 ]])
 
 AT_CLEANUP
+
+AT_SETUP([asymmetric overlap])
+
+AT_DATA([test.cnc],
+[[M48
+INCH
+T25C0.025
+T24C0.050
+%
+T25
+X010200Y010000
+X010300Y010000
+T24
+X010000Y010000
+M30
+]])
+
+AT_CHECK([slotifier test.cnc], [0],
+[[M48
+INCH,TZ
+T10C0.050
+T11C0.025
+%
+T10
+X010000Y010000G85X010300Y010000
+T11
+M30
+
+]])
+
+AT_CLEANUP
+
+AT_SETUP([asymmetric overlap #2])
+
+AT_DATA([test.cnc],
+[[M48
+INCH
+T25C0.030
+T24C0.100
+%
+T25
+X010400Y010250
+T24
+X010800Y010000
+X010000Y010000
+M30
+]])
+
+AT_CHECK([slotifier test.cnc], [0],
+[[M48
+INCH,TZ
+T10C0.100
+T11C0.030
+%
+T10
+X010800Y010000G85X010000Y010000
+T11
+M30
+
+]])
+
+AT_CLEANUP