[Commit] tess ChangeLog,1.2,1.3 bentley.5c,1.3,1.4
Carl Worth
commit at keithp.com
Wed Jul 7 10:40:28 PDT 2004
Committed by: cworth
Update of /local/src/CVS/tess
In directory home.keithp.com:/tmp/cvs-serv396
Modified Files:
ChangeLog bentley.5c
Log Message:
* bentley.5c (bentley_ottman_iterative): Reset frame_count only
between separate runs of bentley_ottman_iterative. Put all tests
into a big array so they are all run with a single invocation.
* bentley.5c (bentley_ottman): Print SVG outputs in
independently-named files for each test.
Index: ChangeLog
===================================================================
RCS file: /local/src/CVS/tess/ChangeLog,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- ChangeLog 7 Jul 2004 15:47:25 -0000 1.2
+++ ChangeLog 7 Jul 2004 17:40:26 -0000 1.3
@@ -1,5 +1,14 @@
2004-07-07 Carl Worth <cworth at isi.edu>
+ * bentley.5c (bentley_ottman_iterative): Reset frame_count only
+ between separate runs of bentley_ottman_iterative. Put all tests
+ into a big array so they are all run with a single invocation.
+
+ * bentley.5c (bentley_ottman): Print SVG outputs in
+ independently-named files for each test.
+
+2004-07-07 Carl Worth <cworth at isi.edu>
+
* bentley.5c: Move SVG printing up to the top-level to declutter
the algorithm.
(intersect_lines): Rename intersect to intersect_lines.
Index: bentley.5c
===================================================================
RCS file: /local/src/CVS/tess/bentley.5c,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -d -r1.3 -r1.4
--- bentley.5c 7 Jul 2004 15:47:25 -0000 1.3
+++ bentley.5c 7 Jul 2004 17:40:26 -0000 1.4
@@ -1,6 +1,10 @@
-autoload Sortlist
-autoload Sort
-autoload SVG
+autoload Sortlist;
+autoload Sort;
+
+import File;
+
+string TEST_NAME = "bentley";
+int FRAME_COUNT;
typedef struct {
int x;
@@ -266,8 +270,8 @@
}
Edge[*]
-bentley_ottman (Edge[*] segments, &int intersection_count) {
-
+bentley_ottman (Edge[*] segments, &int intersection_count)
+{
intersection_count = 0;
EventPtr event_queue = Sortlist::List.nil;
Edge[...] result = {};
@@ -384,8 +388,6 @@
}
}
- static int frame_count = 0;
-
while (event_queue != Sortlist::List.nil) {
file svg_file;
@@ -394,10 +396,10 @@
current_y = event.elt->point.y;
string filename;
- filename = sprintf ("bentley_%03d.svg", frame_count++);
- svg_file = File::open (filename, "w");
+ filename = sprintf ("%s_%03d.svg", TEST_NAME, FRAME_COUNT++);
+ svg_file = open (filename, "w");
print_sweep_line_svg (svg_file, sweep_line, segments, event_queue, event, current_y);
- File::close (svg_file);
+ close (svg_file);
event_queue = event_queue.elt->next;
if (event_queue != Sortlist::List.nil)
@@ -458,20 +460,24 @@
}
}
- printf ("Found %d intersections\n", intersection_count);
-
return result;
}
-Edge[*] bentley_ottman_iterative (Edge[*] edges)
+Edge[*]
+bentley_ottman_iterative (Edge[*] edges, &int iterations)
{
Edge[*] old_edges;
- int count;
+ iterations = 0;
+
+ FRAME_COUNT = 0;
+
+ int intersections;
do {
+ iterations++;
old_edges = edges;
- edges = bentley_ottman(old_edges, &count);
- } while (count > 0);
+ edges = bentley_ottman(old_edges, &intersections);
+ } while (intersections > 0);
return edges;
}
@@ -514,33 +520,81 @@
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 = -1, y = -2}, bottom = { x = 9, y = 5}},
-};
-/* 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}}
-};
+bool run_test (string name, Edge[*] edges)
+{
+ int iterations;
-Edge[*] horizontal_test = { { top = { x = 1, y = 1}, bottom = { x = 6, y = 6}},
- { top = { x = 2, y = 3}, bottom = { x = 5, y = 3}}
-};
+ TEST_NAME = name;
-Edge[*] vertical_test = { { top = { x = 5, y = 1}, bottom = { x = 5, y = 7}},
- { top = { x = 2, y = 4}, bottom = { x = 8, y = 5}}
-};
+ Edge[*] intersected_edges = bentley_ottman_iterative (edges, &iterations);
-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}}
+ printf ("%s: ", name);
+
+ if (edges_have_an_intersection_quadratic (intersected_edges))
+ printf ("*** FAIL ***");
+ else
+ printf ("PASS");
+
+ printf (" (%d iteration%s)\n", iterations, iterations == 1 ? "" : "s");
+}
+
+typedef struct {
+ string name;
+ string desc;
+ Edge[*] edges;
+} Test;
+
+Test[*] tests = {
+ {
+ name = "hobby",
+ desc = "Example from John Hobby's paper. Requires 3 passes of the iterative algorithm.",
+ edges = {
+ { top = { x = 0, y = 0}, bottom = { x = 9, y = 5}},
+ { top = { x = 0, y = 0}, bottom = { x = 13, y = 6}},
+ { top = { x = -1, y = -2}, bottom = { x = 9, y = 5}}
+ }
+ },
+ {
+ name = "slope",
+ desc = "Edges with same start/stop points but different slopes",
+ edges = {
+ { 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}}
+ }
+ },
+ {
+ name = "horizontal",
+ desc = "Test of a horizontal edge",
+ edges = {
+ { top = { x = 1, y = 1}, bottom = { x = 6, y = 6}},
+ { top = { x = 2, y = 3}, bottom = { x = 5, y = 3}}
+ }
+ },
+ {
+ name = "vertical",
+ desc = "Test of a vertical edge",
+ edges = {
+ { top = { x = 5, y = 1}, bottom = { x = 5, y = 7}},
+ { top = { x = 2, y = 4}, bottom = { x = 8, y = 5}}
+ }
+ },
+ {
+ name = "congruent",
+ desc = "Two overlapping edges with the same slope",
+ edges = {
+ { 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}}
+ }
+ }
};
+for (int i=0; i < dim(tests); i++)
+ run_test (tests[i].name, tests[i].edges);
+
num_random = 8;
PRNG::srandom (0);
@@ -553,9 +607,4 @@
};
}
-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");
+run_test ("random", random_edges);
More information about the Commit
mailing list