[Commit] tess ChangeLog, 1.21, 1.22 bentley.5c, 1.17, 1.18 sortlist.5c, 1.3, 1.4

Carl Worth commit at keithp.com
Sat Jul 31 10:31:13 PDT 2004 

Committed by: cworth

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

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

        * bentley.5c (bend_at_tolerance_squares): Replace potentially
        unbounded iteration of Bentley-Ottman with a single second
        pass. The second pass isn't yet computing intersections with
        tolerance squares --- just mechanics for the second-pass handling
        of events so far.


Index: ChangeLog
===================================================================
RCS file: /local/src/CVS/tess/ChangeLog,v
retrieving revision 1.21
retrieving revision 1.22
diff -u -d -r1.21 -r1.22
--- ChangeLog	29 Jul 2004 03:26:37 -0000	1.21
+++ ChangeLog	31 Jul 2004 17:31:10 -0000	1.22
@@ -1,3 +1,11 @@
+2004-07-31  Carl Worth  <cworth at isi.edu>
+
+	* bentley.5c (bend_at_tolerance_squares): Replace potentially
+	unbounded iteration of Bentley-Ottman with a single second
+	pass. The second pass isn't yet computing intersections with
+	tolerance squares --- just mechanics for the second-pass handling
+	of events so far.
+
 2004-07-28  Carl Worth  <cworth at isi.edu>
 
 	* bentley.5c: Remove code that is not needed since we won't have

Index: bentley.5c
===================================================================
RCS file: /local/src/CVS/tess/bentley.5c,v
retrieving revision 1.17
retrieving revision 1.18
diff -u -d -r1.17 -r1.18
--- bentley.5c	29 Jul 2004 03:26:37 -0000	1.17
+++ bentley.5c	31 Jul 2004 17:31:10 -0000	1.18
@@ -3,14 +3,14 @@
 autoload Skiplist;
 
 const bool VALIDATE_SORT = true;
-const bool PRINT_SVG_FILES = false;
+const bool PRINT_SVG_FILES = true;
 
 autoload Sort;
 
 import File;
 
 string TEST_NAME = "bentley";
-int FRAME_COUNT;
+int FRAME_COUNT = 0;
 
 typedef struct {
     int x;
@@ -353,12 +353,12 @@
     fprintf (svg_file, "</svg>\n");
 }
 
-Edge[*]
+Event[*]
 bentley_ottman (Edge[*] segments, &int intersection_count)
 {
     intersection_count = 0;
     EventQueue event_queue = Sortlist::new (event_greater);
-    Edge[...] result = {};
+    Event[...] result = {};
 
     Edge[*] remove_horizontal (Edge[*] edges) {
 	Edge[...] non_horizontal = {};
@@ -495,7 +495,7 @@
 
     while ((EventPtr event_ptr = Sortlist::first (event_queue)) != EventPtr.nil)
     {
-	*Event	event = ElementEvent(event_ptr);
+	*Event event = ElementEvent(event_ptr);
 
 	file svg_file;
 
@@ -522,11 +522,15 @@
 	enum switch (event->type) {
 	case Start:
 	    EdgePtr edge = event->e1;
+
+	    result[dim(result)] = *event;
 	    
 	    if (VALIDATE_SORT)
 		Sortlist::validate (sweep_line);
 
 	    Sortlist::insert (sweep_line, edge);
+	    /* Cache the insert position for use in pass 2. */
+	    event->e2 = Sortlist::prev (sweep_line, edge);
 	    
 	    if (VALIDATE_SORT)
 		Sortlist::validate (sweep_line);
@@ -541,12 +545,9 @@
 	    break;
 	case Stop:
 	    EdgePtr edge = event->e1;
-	    
-	    result[dim(result)] = (Edge) {
-		top = ElementEdge(edge)->middle,
-		bottom = event->point
-	    };
-	    
+
+	    result[dim(result)] = *event;
+
 	    EdgePtr left = Sortlist::prev (sweep_line, edge);
 	    EdgePtr right = Sortlist::next (sweep_line, edge);
 
@@ -566,24 +567,8 @@
 
 	    intersection_count++;
 
-	    /* Avoid inserting a degenerate edge if this edge has already
-	     * been used for a previous intersection at exactly the
-	     * same point. */
-	    if (ElementEdge(e1)->middle != event->point)
-		result[dim(result)] = (Edge) {
-		    top = ElementEdge(e1)->middle,
-		    bottom = event->point
-		};
-	    
-	    if (ElementEdge(e2)->middle != event->point)
-		result[dim(result)] = (Edge) {
-		    top = ElementEdge(e2)->middle,
-		    bottom = event->point
-		};
-	    
-	    ElementEdge(e1)->middle = event->point;
-	    ElementEdge(e2)->middle = event->point;
-	    
+	    result[dim(result)] = *event;
+
 	    EdgePtr left  = Sortlist::prev (sweep_line, e1);
 	    EdgePtr right = Sortlist::next (sweep_line, e2);
 	    
@@ -603,22 +588,105 @@
 }
 
 Edge[*]
-bentley_ottman_iterative (Edge[*] edges, &int iterations)
+bend_at_tolerance_squares (Event[*] events)
 {
-    Edge[*] old_edges;
+    int current_y;
 
-    iterations = 0;
+    bool edge_greater (*Edge a, *Edge b) {
 
-    FRAME_COUNT = 0;
+	rational edge_x_for_y (*Edge e, int y) {
+	    int dx = e->bottom.x - e->top.x;
+	    int dy = e->bottom.y - e->top.y;
 
-    int intersections;
-    do {
-	printf ("%d ", iterations++);
-	old_edges = edges;
-	edges = bentley_ottman(old_edges, &intersections);
-    } while (intersections > 0);
+	    if (dy == 0)
+		return e->top.x;
 
-    return edges;
+	    return e->top.x + (y - e->top.y) * dx / dy;
+	}
+
+	rational ax = edge_x_for_y (a, current_y);
+	rational bx = edge_x_for_y (b, current_y);
+
+	if (ax != bx)
+	    return ax > bx;
+
+	/* Slope comparison */
+	return slope_greater (a, b);
+    }
+
+    EdgeList sweep_line = Sortlist::new (edge_greater);
+    Edge[...] result = {};
+
+    /* XXX: We're currently using another skiplist for sweepline here,
+     * just like we did in the Bentley-Ottman pass. But, we should
+     * optimize this by saving the insert position from the first
+     * pass. Then we could use a doubly-linked list for the sweepline
+     * in the second pass (with O(1) insert instead of O(log n) */
+    if (dim(events) == 0)
+	return result;
+
+    current_y = events[0].point.y;
+    for (int i=0; i < dim(events); i++) {
+	*Event event = &events[i];
+
+	current_y = event->point.y;
+	
+	enum switch (event->type) {
+	case Start:
+
+	    EdgePtr edge = event->e1;
+	    
+	    if (VALIDATE_SORT)
+		Sortlist::validate (sweep_line);
+
+	    Sortlist::insert (sweep_line, edge);
+
+	    if (VALIDATE_SORT)
+		Sortlist::validate (sweep_line);
+	    
+	    break;
+	case Stop:
+
+	    EdgePtr edge = event->e1;
+	    
+	    result[dim(result)] = (Edge) {
+		top = ElementEdge(edge)->middle,
+		bottom = event->point
+	    };
+	    
+	    Sortlist::delete (sweep_line, edge);
+
+	    break;
+	case Intersect:
+
+	    EdgePtr e1 = event->e1;
+	    EdgePtr e2 = event->e2;
+
+	    /* Avoid emitting a degenerate edge if this edge has already
+	     * been used for a previous intersection at exactly the
+	     * same point. */
+	    if (ElementEdge(e1)->middle != event->point)
+		result[dim(result)] = (Edge) {
+		    top = ElementEdge(e1)->middle,
+		    bottom = event->point
+		};
+	    
+	    if (ElementEdge(e2)->middle != event->point)
+		result[dim(result)] = (Edge) {
+		    top = ElementEdge(e2)->middle,
+		    bottom = event->point
+		};
+	    
+	    ElementEdge(e1)->middle = event->point;
+	    ElementEdge(e2)->middle = event->point;
+	    
+	    Sortlist::swap (sweep_line, e1);
+	    
+	    break;
+	}
+    }
+
+    return result;
 }
 
 bool edges_have_an_intersection_quadratic (&Edge[*] edges)
@@ -660,20 +728,21 @@
 
 bool run_test (string name, Edge[*] edges)
 {
-    int iterations;
+    int intersections;
 
     TEST_NAME = name;
 
     printf ("%s: ", name);
 
-    Edge[*] intersected_edges = bentley_ottman_iterative (edges, &iterations);
+    Event[*] events = bentley_ottman (edges, &intersections);
+    Edge[*] intersected_edges = bend_at_tolerance_squares (events);
 
     if (edges_have_an_intersection_quadratic (&intersected_edges))
 	printf ("*** FAIL ***");
     else
 	printf ("PASS");
 
-    printf (" (%d iteration%s)\n", iterations, iterations == 1 ? "" : "s");
+    printf (" (%d intersection%s found)\n", intersections, intersections == 1 ? "" : "s");
 }
 
 typedef struct {
@@ -779,7 +848,6 @@
 
 PRNG::srandom (0);
 
-printf ("Initializing %d random edges\n", num_random);
 Edge[...] random_edges = {};
 for (int i=0; i < num_random; i++)
 {
@@ -788,4 +856,5 @@
 	bottom = { x = PRNG::randint (10), y = PRNG::randint (10) }
     };
 }
-run_test ("random", random_edges);
+test_name = sprintf ("random_%d", num_random);
+run_test (test_name, random_edges);

Index: sortlist.5c
===================================================================
RCS file: /local/src/CVS/tess/sortlist.5c,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -d -r1.3 -r1.4
--- sortlist.5c	9 Jul 2004 19:19:15 -0000	1.3
+++ sortlist.5c	31 Jul 2004 17:31:10 -0000	1.4
@@ -1,5 +1,5 @@
 #
-# Doublely linked sorted lists
+# Doubly linked sorted lists
 #
 
 namespace Sortlist {

More information about the Commit mailing list