[Commit] tess ChangeLog,1.7,1.8 bentley.5c,1.8,1.9

[Carl Worth]

Committed by: cworth

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

Modified Files:
	ChangeLog bentley.5c 
Log Message:

        * bentley.5c (event_greater): Experimental version of what
        event_greater needs to really do. Still buggy and the current test
        shows off the bugs.


Index: ChangeLog
===================================================================
RCS file: /local/src/CVS/tess/ChangeLog,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -d -r1.7 -r1.8
--- ChangeLog	7 Jul 2004 19:34:41 -0000	1.7
+++ ChangeLog	8 Jul 2004 00:11:57 -0000	1.8
@@ -1,5 +1,11 @@
 2004-07-07  Carl Worth  <cworth at isi.edu>
 
+	* bentley.5c (event_greater): Experimental version of what
+	event_greater needs to really do. Still buggy and the current test
+	shows off the bugs.
+
+2004-07-07  Carl Worth  <cworth at isi.edu>
+
 	* bentley.5c (bentley_ottman): Fix insert_event_if to use
 	intersect_segments rather than a custom, (and inadequate in the
 	case of horizontal lines) check for containment of the

Index: bentley.5c
===================================================================
RCS file: /local/src/CVS/tess/bentley.5c,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -d -r1.8 -r1.9
--- bentley.5c	7 Jul 2004 19:34:41 -0000	1.8
+++ bentley.5c	8 Jul 2004 00:11:57 -0000	1.9
@@ -72,15 +72,78 @@
 
 bool event_greater (Event a, Event b)
 {
-    if (point_greater (a.point, b.point))
-	return true;
-    if (point_greater (b.point, a.point))
-	return false;
-    if (a.type != b.type)
-	return (a.type == EventType.Start);
+    /* The major motion of the sweep line is vertical
+     * (top-to-bottom). */
+   
+    /* Vertical discrimination begins with Y value. */
+    if (a.point.y != b.point.y)
+        return a.point.y > b.point.y;
 
-    /* Slope comparison */
-    return slope_greater (*a.e1.elt, *b.e1.elt);
+    /* XXX: We will be able to drop these when we disallow horizontal
+     * edges. */
+    bool a_horiz = a.e1.elt->top.y == a.e1.elt->bottom.y;
+    bool b_horiz = b.e1.elt->top.y == b.e1.elt->bottom.y;
+
+    /* Further vertical discrimination is determined by the event type
+     * for non-horizontal edges. Due to the infinitesimal shortening
+     * rule, non-horizontal stop events occur before the current Y
+     * value while non-horizontal start events occur after the current
+     * value. */
+    if (a.type != b.type) {
+	if (! a_horiz) {
+	    if (a.type == EventType.Stop)
+		return false;
+	    if (a.type == EventType.Start)
+		return true;
+	}
+	if (! b_horiz) {
+	    if (b.type == EventType.Stop)
+		return true;
+	    if (b.type == EventType.Start)
+		return false;
+	}
+    }
+
+    /* The minor motion of the sweep line is horizontal
+     * (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;
+
+    /* 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. */
+    if (a.type != b.type) {
+	if (a_horiz) {
+	    if (a.type == EventType.Stop)
+		return false;
+	    if (a.type == EventType.Start)
+		return true;
+	}
+	if (b_horiz) {
+	    if (b.type == EventType.Stop)
+		return true;
+	    if (b.type == EventType.Start)
+		return false;
+	}
+    }
+
+    /* At this stage we are looking at two events of the same type at
+     * the same point. The final sort key is a slope comparison. We
+     * need a difference sens for start and stop events based on the
+     * shortening rule.
+     *
+     * NOTE: Fortunately, we get to ignore errors in the relative
+     * ordering of intersection events. This means we don't even have
+     * to look at e2 here, nor worry about which sense of the slope
+     * comparison test is used for intersection events.
+     */
+    if (a.type == EventType.Start)
+        return slope_greater (*a.e1.elt, *b.e1.elt);
+    else
+        return ! slope_greater (*a.e1.elt, *b.e1.elt);
 }
 
 exception parallel (void);
@@ -564,6 +627,15 @@
 
 Test[*] tests = {
     {
+	name = "hobby_stage_3",
+	desc = "Part of the 3rd stage of the 'hobby' test below.",
+	edges = {
+	    { top = { x = -1, y = -2}, bottom = { x =  4, y = 2}},
+	    { top = { x =  5, y =  3}, bottom = { x =  9, y = 5}},
+	    { top = { x =  5, y =  3}, bottom = { x =  6, y = 3}},
+	}
+    },
+    {
 	name = "hobby",
 	desc = "Example from John Hobby's paper. Requires 3 passes of the iterative algorithm.",
 	edges = {
@@ -624,7 +696,7 @@
 for (int i=0; i < dim(tests); i++)
     run_test (tests[i].name, tests[i].edges);
 
-num_random = 8;
+num_random = 12;
 
 PRNG::srandom (0);
 Edge[...] random_edges = {};