[Commit] tess ChangeLog,1.1,1.2 bentley.5c,1.2,1.3

[Carl Worth]

Committed by: cworth

Update of /local/src/CVS/tess
In directory home.keithp.com:/tmp/cvs-serv30124

Modified Files:
	ChangeLog bentley.5c 
Log Message:

        (intersect_lines): Rename intersect to intersect_lines.
        (intersect_segments): New function that calls intersect_lines and
        checks whether the intersection lies within both segments.
        (edges_have_an_intersection_quadratic): New O(n**2) algorithm to
        check if there are any remaining intersections after the main
        algorithm is complete.
        Added a few focused test cases and one random test.


Index: ChangeLog
===================================================================
RCS file: /local/src/CVS/tess/ChangeLog,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- ChangeLog	7 Jul 2004 15:32:35 -0000	1.1
+++ ChangeLog	7 Jul 2004 15:47:25 -0000	1.2
@@ -2,4 +2,11 @@
 
 	* bentley.5c: Move SVG printing up to the top-level to declutter
 	the algorithm.
+	(intersect_lines): Rename intersect to intersect_lines.
+	(intersect_segments): New function that calls intersect_lines and
+	checks whether the intersection lies within both segments.
+	(edges_have_an_intersection_quadratic): New O(n**2) algorithm to
+	check if there are any remaining intersections after the main
+	algorithm is complete.
+	Added a few focused test cases and one random test.
 

Index: bentley.5c
===================================================================
RCS file: /local/src/CVS/tess/bentley.5c,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- bentley.5c	7 Jul 2004 15:32:35 -0000	1.2
+++ bentley.5c	7 Jul 2004 15:47:25 -0000	1.3
@@ -79,8 +79,10 @@
 
 exception parallel (void);
 
-RationalPoint intersect (Edge a, Edge b) {
+exception no_intersection (void);
 
+RationalPoint intersect_lines (Edge a, Edge b)
+{
     int det (int a, int b, int c, int d) {
 	return a * d - b * c;
     }
@@ -109,6 +111,30 @@
     };
 }
 
+/* XXX: As should be obvious, this function is a bit simpler in the
+ * absence of horizontal edges */
+RationalPoint intersect_segments (Edge a, Edge b)
+{
+    RationalPoint intersection = intersect_lines (a, b);
+
+    if (a.top.y == a.bottom.y) {
+	if (intersection.x <= a.top.x || intersection.x >= a.bottom.x)
+	    raise no_intersection ();
+    } else {
+	if (intersection.y <= a.top.y || intersection.y >= a.bottom.y)
+	    raise no_intersection ();
+    }
+
+    if (b.top.y == b.bottom.y) {
+	if (intersection.x <= b.top.x || intersection.x >= b.bottom.x)
+	    raise no_intersection ();
+    } else {
+	if (intersection.y <= b.top.y || intersection.y >= b.bottom.y)
+	    raise no_intersection ();
+    }
+
+    return intersection;
+}
 
 bool event_ptr_greater (EventPtr a, EventPtr b)
 {
@@ -334,7 +360,7 @@
 
 	RationalPoint intersection;
 	try {
-	    intersection = intersect (*a.elt, *b.elt);
+	    intersection = intersect_lines (*a.elt, *b.elt);
 	} catch parallel () {
 	    return;
 	}
@@ -450,11 +476,86 @@
     return edges;
 }
 
+bool edges_have_an_intersection_quadratic (Edge[*] edges)
+{
+    RationalPoint intersection;
+    Edge a, b;
+
+    for (int i=0; i < dim(edges); i++) {
+	if (point_greater (edges[i].top, edges[i].bottom)) {
+	    Point tmp;
+	    tmp = edges[i].top;
+	    edges[i].top = edges[i].bottom;
+	    edges[i].bottom = tmp;
+	}
+    }
+    for (int i=0; i < dim(edges); i++) {
+	for (int j=0; j < dim (edges); j++) {
+	    if (i==j)
+		continue;
+	    a = edges[i];
+	    b = edges[j];
+	    try {
+		intersection = intersect_segments (a, b);
+	    } catch parallel () {
+		continue;
+	    } catch no_intersection () {
+		continue;
+	    }
+	    printf ("Found intersection (%g,%g) between (%g,%g)-(%g,%g) and (%g,%g)-(%g,%g)\n",
+		    intersection.x, intersection.y,
+		    a.top.x, a.top.y,
+		    a.bottom.x, a.bottom.y,
+		    b.top.x, b.top.y,
+		    b.bottom.x, b.bottom.y);
+	    return true;
+	}
+    }
+    return false;
+}
+
 /* Cool, degnerate case from Hobby's paper. Require's 3 passes until
  * we implement tolerance squares. */
 Edge[*] hobby_edges = { { top = { x =   0, y =   0}, bottom = { x =   9, y =   5}},
 			{ top = { x =   0, y =   0}, bottom = { x =  13, y =   6}},
-			{ top = { x =   9, y =   5}, bottom = { x =  -1, y =  -2}}
+			{ top = { x =  -1, y =  -2}, bottom = { x =   9, y =   5}},
 };
 
-bentley_ottman_iterative (hobby_edges);
+/* Some focused test for several corner cases. */
+Edge[*] slope_test = { { top = { x = 4, y = 1}, bottom = { x = 6, y = 3}},
+		       { top = { x = 4, y = 1}, bottom = { x = 2, y = 3}},
+		       { top = { x = 2, y = 4}, bottom = { x = 4, y = 6}},
+		       { top = { x = 6, y = 4}, bottom = { x = 4, y = 6}}
+};
+
+Edge[*] horizontal_test = { { top = { x = 1, y = 1}, bottom = { x = 6, y = 6}},
+			    { top = { x = 2, y = 3}, bottom = { x = 5, y = 3}}
+};
+
+Edge[*] vertical_test = { { top = { x = 5, y = 1}, bottom = { x = 5, y = 7}},
+			  { top = { x = 2, y = 4}, bottom = { x = 8, y = 5}}
+};
+
+Edge[*] congruent_test = { { top = { x = 5, y = 1}, bottom = { x = 5, y = 7}},
+			   { top = { x = 5, y = 2}, bottom = { x = 5, y = 6}},
+			   { top = { x = 2, y = 4}, bottom = { x = 8, y = 5}}
+};
+
+num_random = 8;
+
+PRNG::srandom (0);
+Edge[...] random_edges = {};
+for (int i=0; i < num_random; i++)
+{
+    random_edges[dim (random_edges)] = (Edge) {
+	top = { x = PRNG::randint (10), y = PRNG::randint (10) },
+	bottom = { x = PRNG::randint (10), y = PRNG::randint (10) }
+    };
+}
+
+Edge[*] intersected_edges = bentley_ottman_iterative (congruent_test);
+
+if (edges_have_an_intersection_quadratic (intersected_edges))
+    printf ("Error: There's still at least one intersection left.\n");
+else
+    printf ("Phew: No intersections left\n");