[Commit] tess ChangeLog, 1.12, 1.13 bentley.5c, 1.13, 1.14 sortlist.5c, 1.2, 1.3

[Carl Worth]

Committed by: cworth

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

Modified Files:
	ChangeLog bentley.5c sortlist.5c 
Log Message:

        * sortlist.5c (delete): Reset prev/next to List.nil to catch bugs
        sooner.

        * bentley.5c: Move the prev/next pointers to the end of the struct
        so I can decipher the printouts from the nickle debugger.
        (event_greater): Fix to compare unrounded rational X intersection
        value.

        The algorithm is behaving quite well now. I haven't found a random
        test that fails yet, (only tried one seed and up to 100 edges so
        far).


Index: ChangeLog
===================================================================
RCS file: /local/src/CVS/tess/ChangeLog,v
retrieving revision 1.12
retrieving revision 1.13
diff -u -d -r1.12 -r1.13
--- ChangeLog	9 Jul 2004 02:06:58 -0000	1.12
+++ ChangeLog	9 Jul 2004 19:19:15 -0000	1.13
@@ -1,3 +1,17 @@
+2004-07-09  Carl Worth  <cworth at isi.edu>
+
+	* sortlist.5c (delete): Reset prev/next to List.nil to catch bugs
+	sooner.
+
+	* bentley.5c: Move the prev/next pointers to the end of the struct
+	so I can decipher the printouts from the nickle debugger.
+	(event_greater): Fix to compare unrounded rational X intersection
+	value.
+
+	The algorithm is behaving quite well now. I haven't found a random
+	test that fails yet, (only tried one seed and up to 100 edges so
+	far).
+
 2004-07-08  Carl Worth  <cworth at isi.edu>
 
 	* bentley.5c: Random tests work up through 27 edges now, (much,

Index: bentley.5c
===================================================================
RCS file: /local/src/CVS/tess/bentley.5c,v
retrieving revision 1.13
retrieving revision 1.14
diff -u -d -r1.13 -r1.14
--- bentley.5c	9 Jul 2004 02:06:58 -0000	1.13
+++ bentley.5c	9 Jul 2004 19:19:15 -0000	1.14
@@ -34,10 +34,10 @@
 } EdgePtr;
 
 typedef struct {
-    EdgePtr    prev, next;
     Point top;
     Point middle;
     Point bottom;
+    EdgePtr    prev, next;
 } Edge;
 
 typedef enum {
@@ -52,12 +52,12 @@
 } EventPtr;
 
 typedef struct {
-    EventPtr    prev, next;
     EventType type;
     EdgePtr e1;
     EdgePtr e2;
     Point point;
-    rational rational_y;
+    RationalPoint rational_point;
+    EventPtr    prev, next;
 } Event;
 
 bool slope_greater (Edge a, Edge b)
@@ -88,8 +88,8 @@
      * (top-to-bottom). */
    
     /* Vertical discrimination begins with Y value. */
-    if (a.rational_y != b.rational_y)
-        return a.rational_y > b.rational_y;
+    if (a.rational_point.y != b.rational_point.y)
+        return a.rational_point.y > b.rational_point.y;
 
     /* XXX: We will be able to drop these when we disallow horizontal
      * edges. */
@@ -125,8 +125,8 @@
      * (left-to-right) due to the infinitesimal tilt rule. */
 
     /* Horizontal discrimination begins with X value. */
-    if (a.point.x != b.point.x)
-        return a.point.x > b.point.x;
+    if (a.rational_point.x != b.rational_point.x)
+        return a.rational_point.x > b.rational_point.x;
 
     /* At this point, degenerate edges cause problems, (stop events
      * get scheduled before start events). I had tried adding code
@@ -414,7 +414,7 @@
 		type = EventType.Start,
 		e1 = (EdgePtr.elt) &segments[i],
 		point = segments[i].top,
-		rational_y = segments[i].top.y,
+		rational_point = segments[i].top,
 		prev = Sortlist::List.nil,
 		next = Sortlist::List.nil
 	    };
@@ -422,7 +422,7 @@
 		type = EventType.Stop,
 		e1 = (EdgePtr.elt) &segments[i],
 		point = segments[i].bottom,
-		rational_y = segments[i].bottom.y,
+		rational_point = segments[i].bottom,
 		prev = Sortlist::List.nil,
 		next = Sortlist::List.nil
 	    };
@@ -543,7 +543,7 @@
 			          x = floor (intersection.x + 0.5),
 			          y = floor (intersection.y + 0.5),
 			      },
-			      rational_y = intersection.y
+			      rational_point = intersection
 	                  },
 			  event_ptr_greater);
     }
@@ -717,6 +717,14 @@
 
 Test[*] tests = {
     {
+	name = "endpoint",
+	desc = "An intersection that occurs at the enpoint of a segments.",
+	edges = {
+	    { top = { x = 4, y = 6}, bottom = { x = 5, y = 6}},
+	    { top = { x = 4, y = 5}, bottom = { x = 5, y = 7}},
+	}
+    },
+    {
 	name = "overlapping",
 	desc = "Parallel segments that share an endpoint, with different slopes.",
 	edges = {
@@ -798,7 +806,7 @@
 for (int i=0; i < dim(tests); i++)
     run_test (tests[i].name, tests[i].edges);
 
-num_random = 28;
+num_random = 30;
 
 PRNG::srandom (0);
 Edge[...] random_edges = {};

Index: sortlist.5c
===================================================================
RCS file: /local/src/CVS/tess/sortlist.5c,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- sortlist.5c	2 Jul 2004 08:06:07 -0000	1.2
+++ sortlist.5c	9 Jul 2004 19:19:15 -0000	1.3
@@ -91,6 +91,8 @@
 	    head = old.elt->next;
 	if (old.elt->next != List.nil)
 	    old.elt->next.elt->prev = old.elt->prev;
+	old.elt->prev = List.nil;
+	old.elt->next = List.nil;
 	validate (head);
     }