[Commit] tess ChangeLog,1.10,1.11 bentley.5c,1.11,1.12

[Carl Worth]

Committed by: cworth

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

Modified Files:
	ChangeLog bentley.5c 
Log Message:

        * bentley.5c (event_greater): Remove buggy code intended to handle
        (bentley_ottman): Add remove_degenerate function to just yank the
        degenerate edges out before beginning the algorithm.

        The random test works at least as far as 20 now.


Index: ChangeLog
===================================================================
RCS file: /local/src/CVS/tess/ChangeLog,v
retrieving revision 1.10
retrieving revision 1.11
diff -u -d -r1.10 -r1.11
--- ChangeLog	9 Jul 2004 00:51:10 -0000	1.10
+++ ChangeLog	9 Jul 2004 02:04:38 -0000	1.11
@@ -1,5 +1,14 @@
 2004-07-08  Carl Worth  <cworth at isi.edu>
 
+	* bentley.5c (event_greater): Remove buggy code intended to handle
+	degenerate edges (including duplicates!).
+	(bentley_ottman): Add remove_degenerate function to just yank the
+	degenerate edges out before beginning the algorithm.
+
+	The random test works at least as far as 20 now.
+	
+2004-07-08  Carl Worth  <cworth at isi.edu>
+
 	* bentley.5c (event_greater): Yet another rework of the
 	event_greater function. It's pretty close now. Horizontal and even
 	fully degnerate edges are handled better. And even partially

Index: bentley.5c
===================================================================
RCS file: /local/src/CVS/tess/bentley.5c,v
retrieving revision 1.11
retrieving revision 1.12
diff -u -d -r1.11 -r1.12
--- bentley.5c	9 Jul 2004 00:51:10 -0000	1.11
+++ bentley.5c	9 Jul 2004 02:04:38 -0000	1.12
@@ -128,26 +128,19 @@
     if (a.point.x != b.point.x)
         return a.point.x > b.point.x;
 
+    /* At this point, degenerate edges cause problems, (stop events
+     * get scheduled before start events). I had tried adding code
+     * here to fix it, but decided instead to just remove those edges
+     * before the algorithm begine.
+     */
+
     /* Even with the same X-value, further horizontal discrimination
      * is determined by the event type for horizontal edges.  As
      * before, due to the shortening rule, stop events occur before
      * the current X value while start events occur after the current
      * value.
-     *
-     * However, if the start and stop events belong to the same edge
-     * then the start event must come first. The X comparison above
-     * catches every case except for a degenerate edge with top ==
-     * bottom.
      */
     if (a.type != b.type) {
-	if (a.e1.elt->top.x == a.e1.elt->bottom.x &&
-	    a.e1.elt->top.y == a.e1.elt->bottom.y &&
-	    a.e1.elt->top.x == b.e1.elt->top.x &&
-	    a.e1.elt->top.y == b.e1.elt->top.y &&
-	    b.e1.elt->top.x == b.e1.elt->bottom.x &&
-	    b.e1.elt->top.y == b.e1.elt->bottom.y)
-	    return a.type == EventType.Stop;
-
 	if (a.type == EventType.Stop)
 	    return false;
 	if (a.type == EventType.Start)
@@ -381,6 +374,16 @@
     EventPtr event_queue = Sortlist::List.nil;
     Edge[...] result = {};
 
+    Edge[*] remove_degenerate (Edge[*] edges) {
+	Edge[...] non_degenerate = {};
+	for (int i=0; i < dim(edges); i++)
+	    if (edges[i].top.x != edges[i].bottom.x ||
+		edges[i].top.y != edges[i].bottom.y)
+		non_degenerate[dim(non_degenerate)] = edges[i];
+
+	return non_degenerate;
+    }
+
     Edge[*] remove_horizontal (Edge[*] edges) {
 	Edge[...] non_horizontal = {};
 	for (int i=0; i < dim(edges); i++)
@@ -392,6 +395,8 @@
 
     EventPtr initialize_event_queue (Edge[*] segments) {
 	Event[...] events = {};
+
+	segments = remove_degenerate (segments);
 /*
 	segments = remove_horizontal (segments);
 */
@@ -791,7 +796,7 @@
 for (int i=0; i < dim(tests); i++)
     run_test (tests[i].name, tests[i].edges);
 
-num_random = 19;
+num_random = 20;
 
 PRNG::srandom (0);
 Edge[...] random_edges = {};