X-Git-Url: https://git.draconx.ca/gitweb/slotifier.git/blobdiff_plain/4e1fa5cd8519f2de9bd504e03c0d6394b104692a..66da2ec430dc20657579eb90289e8e5ff4f5c987:/src/slotifier.c

diff --git a/src/slotifier.c b/src/slotifier.c
index 3998926..05ede6b 100644
--- 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;
 }