[Commit] tess ChangeLog,1.9,1.10 bentley.5c,1.10,1.11
Carl Worth
commit at keithp.com
Thu Jul 8 17:51:13 PDT 2004
Committed by: cworth
Update of /local/src/CVS/tess
In directory home.keithp.com:/tmp/cvs-serv6121
Modified Files:
ChangeLog bentley.5c
Log Message:
* 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
overlapping segments with a shared endpoint are handled
unambiguously.
(bentley_ottman): When checking the results of qsort, don't flag
problems for differences in the sorting of duplicate edges.
All of the focused tests pass now, including a new one with
overlapping edges. Random still only survives up to 19 edges
though.
Index: ChangeLog
===================================================================
RCS file: /local/src/CVS/tess/ChangeLog,v
retrieving revision 1.9
retrieving revision 1.10
diff -u -d -r1.9 -r1.10
--- ChangeLog 8 Jul 2004 02:43:08 -0000 1.9
+++ ChangeLog 9 Jul 2004 00:51:10 -0000 1.10
@@ -1,3 +1,17 @@
+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
+ overlapping segments with a shared endpoint are handled
+ unambiguously.
+ (bentley_ottman): When checking the results of qsort, don't flag
+ problems for differences in the sorting of duplicate edges.
+
+ All of the focused tests pass now, including a new one with
+ overlapping edges. Random still only survives up to 19 edges
+ though.
+
2004-07-07 Carl Worth <cworth at isi.edu>
* bentley.5c (event_greater): Compared based on rational_y value
Index: bentley.5c
===================================================================
RCS file: /local/src/CVS/tess/bentley.5c,v
retrieving revision 1.10
retrieving revision 1.11
diff -u -d -r1.10 -r1.11
--- bentley.5c 8 Jul 2004 02:43:08 -0000 1.10
+++ bentley.5c 9 Jul 2004 00:51:10 -0000 1.11
@@ -71,6 +71,17 @@
return adx * bdy > ady * bdx;
}
+bool slope_equal (Edge a, Edge b)
+{
+ int adx = a.bottom.x - a.top.x;
+ int bdx = b.bottom.x - b.top.x;
+
+ int ady = a.bottom.y - a.top.y;
+ int bdy = b.bottom.y - b.top.y;
+
+ return adx * bdy == ady * bdx;
+}
+
bool event_greater (Event a, Event b)
{
/* The major motion of the sweep line is vertical
@@ -85,66 +96,66 @@
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. */
-
- /* XXX: Need a comment describing this one. And I'm not 100%
- * convinced it's in the right place yet. Ugh, this sort function
- * is painful. */
- if (a_horiz && ! b_horiz) {
+ /* Even with the same Y-value, 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.
+ *
+ * So, a non-horizontal stop event is less than another event if
+ * that other event belongs to a horizontal edge or it is not a
+ * stop event. Similar logic holds for non-horizontal start
+ * events.
+ */
+ if (!a_horiz && (b_horiz || b.type != a.type)) {
if (a.type == EventType.Stop)
- return true;
- if (a.type == EventType.Start)
return false;
+ if (a.type == EventType.Start)
+ return true;
}
- if (b_horiz && ! a_horiz) {
+
+ if (!b_horiz && (a_horiz || a.type != b.type)) {
if (b.type == EventType.Stop)
- return false;
- if (b.type == EventType.Start)
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. */
+ /* 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_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;
- }
+ 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)
+ return true;
+ 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
@@ -157,10 +168,22 @@
* to look at e2 here, nor worry about which sense of the slope
* comparison test is used for intersection events.
*/
+ if (! slope_equal (*a.e1.elt, *b.e1.elt))
+ if (a.type == EventType.Start)
+ return slope_greater (*a.e1.elt, *b.e1.elt);
+ else
+ return ! slope_greater (*a.e1.elt, *b.e1.elt);
+
+ /* As a final discrimination, look at the opposite point. This
+ * leaves ambiguities only for identical edges.
+ *
+ * XXX: We probably don't actually need this one, but it prevents
+ * my sort check from returning a false negaative.
+ */
if (a.type == EventType.Start)
- return slope_greater (*a.e1.elt, *b.e1.elt);
+ return point_greater (b.e1.elt->bottom, a.e1.elt->bottom);
else
- return ! slope_greater (*a.e1.elt, *b.e1.elt);
+ return point_greater (a.e1.elt->top, b.e1.elt->top);
}
exception parallel (void);
@@ -402,21 +425,37 @@
Sort::qsort (&events, event_greater);
-/* A quick O(n**2) test to determine consistency of the sort
+/* A quick O(n**2) test to determine consistency of the sort */
+/*
for (int i=0; i < dim(events); i++) {
for (int j=0; j < dim(events); j++) {
if (i==j)
continue;
- if (j < i)
- if (event_greater (events[i], events[j]))
+ if (j < i) {
+ if (event_greater (events[i], events[j])) {
printf ("%d > %d: good\n", i, j);
- else
- printf ("*** %d < %d: badness\n", i, j);
- else
- if (event_greater (events[i], events[j]))
- printf ("*** %d > %d: badness\n", i, j);
- else
+ } else {
+ if (events[i].e1.elt->top.x == events[j].e1.elt->top.x &&
+ events[i].e1.elt->top.y == events[j].e1.elt->top.y &&
+ events[i].e1.elt->bottom.x == events[j].e1.elt->bottom.x &&
+ events[i].e1.elt->bottom.y == events[j].e1.elt->bottom.y)
+ printf ("%d == %d: good\n", i, j);
+ else
+ printf ("*** %d < %d: badness\n", i, j);
+ }
+ } else {
+ if (event_greater (events[i], events[j])) {
+ if (events[i].e1.elt->top.x == events[j].e1.elt->top.x &&
+ events[i].e1.elt->top.y == events[j].e1.elt->top.y &&
+ events[i].e1.elt->bottom.x == events[j].e1.elt->bottom.x &&
+ events[i].e1.elt->bottom.y == events[j].e1.elt->bottom.y)
+ printf ("%d == %d: good\n", i, j);
+ else
+ printf ("*** %d > %d: badness\n", i, j);
+ } else {
printf ("%d < %d: good\n", i, j);
+ }
+ }
}
printf ("\n");
}
@@ -512,7 +551,7 @@
current_y = event.elt->point.y;
string filename;
- filename = sprintf ("%s_%03d.svg", TEST_NAME, FRAME_COUNT++);
+ filename = sprintf ("%s_%04d.svg", TEST_NAME, FRAME_COUNT++);
svg_file = open (filename, "w");
print_sweep_line_svg (svg_file, sweep_line, segments, event_queue, event, current_y);
close (svg_file);
@@ -671,8 +710,20 @@
Test[*] tests = {
{
+ name = "overlapping",
+ desc = "Parallel segments that share an endpoint, with different slopes.",
+ edges = {
+ { top = { x = 2, y = 0}, bottom = { x = 1, y = 1}},
+ { top = { x = 2, y = 0}, bottom = { x = 0, y = 2}},
+ { top = { x = 0, y = 3}, bottom = { x = 1, y = 3}},
+ { top = { x = 0, y = 3}, bottom = { x = 2, y = 3}},
+ { top = { x = 0, y = 4}, bottom = { x = 0, y = 6}},
+ { top = { x = 0, y = 5}, bottom = { x = 0, y = 6}}
+ }
+ },
+ {
name = "hobby_stage_3",
- desc = "Part of the 3rd stage of the 'hobby' test below.",
+ desc = "A particularly tricky 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}},
@@ -740,7 +791,7 @@
for (int i=0; i < dim(tests); i++)
run_test (tests[i].name, tests[i].edges);
-num_random = 12;
+num_random = 19;
PRNG::srandom (0);
Edge[...] random_edges = {};
More information about the Commit
mailing list