[Commit] tess ChangeLog,1.8,1.9 bentley.5c,1.9,1.10
Carl Worth
commit at keithp.com
Wed Jul 7 19:43:11 PDT 2004
Committed by: cworth
Update of /local/src/CVS/tess
In directory home.keithp.com:/tmp/cvs-serv13302
Modified Files:
ChangeLog bentley.5c
Log Message:
* bentley.5c (event_greater): Compared based on rational_y value
so that intersection events get scheduled properly (ie. before the
stop events of their edges).
(event_greater): Add yet another stage to the compare function for
horizontal edges. Someone with a clear head needs to look at this
function, simplify it and make it correct.
(remove_horizontal): New function for yanking out all horizontal
edges (not currently used).
(bentley_ottman): Add code to verify that the results of
qsort/event_greater are consistent.
(bentley_ottman): Use slope comparison rather than comparison with
current_y to determine if an intersection is before
current_y. This allows intersections with horizontal edges to be
scheduled.
(bentley_ottman): Notice when the same edge is interseting a
second edge at the same point as before. This way we can avoid
inserting a degenerate edge into the result.
(run_test): Fix to print the test name before any other output.
Index: ChangeLog
===================================================================
RCS file: /local/src/CVS/tess/ChangeLog,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -d -r1.8 -r1.9
--- ChangeLog 8 Jul 2004 00:11:57 -0000 1.8
+++ ChangeLog 8 Jul 2004 02:43:08 -0000 1.9
@@ -1,5 +1,26 @@
2004-07-07 Carl Worth <cworth at isi.edu>
+ * bentley.5c (event_greater): Compared based on rational_y value
+ so that intersection events get scheduled properly (ie. before the
+ stop events of their edges).
+ (event_greater): Add yet another stage to the compare function for
+ horizontal edges. Someone with a clear head needs to look at this
+ function, simplify it and make it correct.
+ (remove_horizontal): New function for yanking out all horizontal
+ edges (not currently used).
+ (bentley_ottman): Add code to verify that the results of
+ qsort/event_greater are consistent.
+ (bentley_ottman): Use slope comparison rather than comparison with
+ current_y to determine if an intersection is before
+ current_y. This allows intersections with horizontal edges to be
+ scheduled.
+ (bentley_ottman): Notice when the same edge is interseting a
+ second edge at the same point as before. This way we can avoid
+ inserting a degenerate edge into the result.
+ (run_test): Fix to print the test name before any other output.
+
+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.
Index: bentley.5c
===================================================================
RCS file: /local/src/CVS/tess/bentley.5c,v
retrieving revision 1.9
retrieving revision 1.10
diff -u -d -r1.9 -r1.10
--- bentley.5c 8 Jul 2004 00:11:57 -0000 1.9
+++ bentley.5c 8 Jul 2004 02:43:08 -0000 1.10
@@ -57,6 +57,7 @@
EdgePtr e1;
EdgePtr e2;
Point point;
+ rational rational_y;
} Event;
bool slope_greater (Edge a, Edge b)
@@ -76,8 +77,8 @@
* (top-to-bottom). */
/* Vertical discrimination begins with Y value. */
- if (a.point.y != b.point.y)
- return a.point.y > b.point.y;
+ if (a.rational_y != b.rational_y)
+ return a.rational_y > b.rational_y;
/* XXX: We will be able to drop these when we disallow horizontal
* edges. */
@@ -107,6 +108,22 @@
/* 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) {
+ if (a.type == EventType.Stop)
+ return true;
+ if (a.type == EventType.Start)
+ return false;
+ }
+ if (b_horiz && ! a_horiz) {
+ if (b.type == EventType.Stop)
+ return false;
+ if (b.type == EventType.Start)
+ return true;
+ }
+
/* Horizontal discrimination begins with X value. */
if (a.point.x != b.point.x)
return a.point.x > b.point.x;
@@ -341,11 +358,22 @@
EventPtr event_queue = Sortlist::List.nil;
Edge[...] result = {};
+ Edge[*] remove_horizontal (Edge[*] edges) {
+ Edge[...] non_horizontal = {};
+ for (int i=0; i < dim(edges); i++)
+ if (edges[i].top.y != edges[i].bottom.y)
+ non_horizontal[dim(non_horizontal)] = edges[i];
+
+ return non_horizontal;
+ }
+
EventPtr initialize_event_queue (Edge[*] segments) {
Event[...] events = {};
+/*
+ segments = remove_horizontal (segments);
+*/
for (int i=0; i < dim(segments); i++) {
-
if (point_greater (segments[i].top, segments[i].bottom)) {
Point tmp;
tmp = segments[i].top;
@@ -358,6 +386,7 @@
type = EventType.Start,
e1 = (EdgePtr.elt) &segments[i],
point = segments[i].top,
+ rational_y = segments[i].top.y,
prev = Sortlist::List.nil,
next = Sortlist::List.nil
};
@@ -365,6 +394,7 @@
type = EventType.Stop,
e1 = (EdgePtr.elt) &segments[i],
point = segments[i].bottom,
+ rational_y = segments[i].bottom.y,
prev = Sortlist::List.nil,
next = Sortlist::List.nil
};
@@ -372,6 +402,26 @@
Sort::qsort (&events, event_greater);
+/* 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]))
+ 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
+ printf ("%d < %d: good\n", i, j);
+ }
+ printf ("\n");
+ }
+*/
+
for (int i=0; i < dim(events) - 1; i++) {
events[i].next = (EventPtr.elt) &events[i+1];
events[i+1].prev = (EventPtr.elt) &events[i];
@@ -427,18 +477,9 @@
if (left == Sortlist::List.nil || right == Sortlist::List.nil)
return;
-/* XXX: Hobby suggests an initial slope comparison before the
- * intersection test, which is faster for the common case. But I don't
- * see an easy way to make this work with horizontal
- * edges. Fortunately, we plan to get rid of those.
- *
- * When this test is enabled, we can drop the comparison between
- * intersection.c and current_y below.
- */
-/*
- if (slope_greater (*left.elt, *right.elt))
+ /* A slope comparison tells us if the intersection is before current_y */
+ if (slope_greater (*right.elt, *left.elt))
return;
-*/
RationalPoint intersection;
try {
@@ -449,20 +490,18 @@
return;
}
- if (intersection.y > current_y)
- {
- Sortlist::insert (&event_queue,
- (EventPtr.elt) &(Event) {
- type = EventType.Intersect,
- e1 = left,
- e2 = right,
- point = {
- x = floor (intersection.x + 0.5),
- y = floor (intersection.y + 0.5)
- }
+ Sortlist::insert (&event_queue,
+ (EventPtr.elt) &(Event) {
+ type = EventType.Intersect,
+ e1 = left,
+ e2 = right,
+ point = {
+ x = floor (intersection.x + 0.5),
+ y = floor (intersection.y + 0.5),
},
- event_ptr_greater);
- }
+ rational_y = intersection.y
+ },
+ event_ptr_greater);
}
while (event_queue != Sortlist::List.nil) {
@@ -516,14 +555,19 @@
intersection_count++;
- result[dim(result)] = (Edge) {
- top = event.elt->e1.elt->middle,
- bottom = event.elt->point
- };
- result[dim(result)] = (Edge) {
- top = event.elt->e2.elt->middle,
- bottom = event.elt->point
- };
+ /* Avoid inserting a degenerate edge if this edge has already
+ * been used for a previous intersection at exactly the
+ * same point. */
+ if (event.elt->e1.elt->middle != event.elt->point)
+ result[dim(result)] = (Edge) {
+ top = event.elt->e1.elt->middle,
+ bottom = event.elt->point
+ };
+ if (event.elt->e2.elt->middle != event.elt->point)
+ result[dim(result)] = (Edge) {
+ top = event.elt->e2.elt->middle,
+ bottom = event.elt->point
+ };
event.elt->e1.elt->middle = event.elt->point;
event.elt->e2.elt->middle = event.elt->point;
@@ -607,10 +651,10 @@
TEST_NAME = name;
- Edge[*] intersected_edges = bentley_ottman_iterative (edges, &iterations);
-
printf ("%s: ", name);
+ Edge[*] intersected_edges = bentley_ottman_iterative (edges, &iterations);
+
if (edges_have_an_intersection_quadratic (intersected_edges))
printf ("*** FAIL ***");
else
More information about the Commit
mailing list