[Commit] tess ChangeLog, 1.19, 1.20 bentley.5c, 1.15,
1.16 kbentley.5c, 1.5, NONE
Carl Worth
commit at keithp.com
Wed Jul 28 20:25:18 PDT 2004
Committed by: cworth
Update of /local/src/CVS/tess
In directory home.keithp.com:/tmp/cvs-serv8708
Modified Files:
ChangeLog bentley.5c
Removed Files:
kbentley.5c
Log Message:
* bentley.5c: Merge kbentley.5c into bentley.5c so that it uses
skip lists now. Remove kbentley.5c.
Index: ChangeLog
===================================================================
RCS file: /local/src/CVS/tess/ChangeLog,v
retrieving revision 1.19
retrieving revision 1.20
diff -u -d -r1.19 -r1.20
--- ChangeLog 29 Jul 2004 03:20:30 -0000 1.19
+++ ChangeLog 29 Jul 2004 03:25:15 -0000 1.20
@@ -1,5 +1,8 @@
2004-07-28 Carl Worth <cworth at isi.edu>
+ * bentley.5c: Merge kbentley.5c into bentley.5c so that it uses
+ skip lists now. Remove kbentley.5c.
+
* kbentley.5c: Minor changes to re-synch bentley.5c and
kbentley.5c.
Index: bentley.5c
===================================================================
RCS file: /local/src/CVS/tess/bentley.5c,v
retrieving revision 1.15
retrieving revision 1.16
diff -u -d -r1.15 -r1.16
--- bentley.5c 24 Jul 2004 06:26:16 -0000 1.15
+++ bentley.5c 29 Jul 2004 03:25:15 -0000 1.16
@@ -1,6 +1,9 @@
#!/usr/bin/env nickle
-autoload Sortlist;
+autoload Skiplist;
+
+const bool VALIDATE_SORT = true;
+
autoload Sort;
import File;
@@ -26,41 +29,35 @@
return a.x > b.x;
}
-typedef Edge;
-
-typedef union {
- *Edge elt;
- void nil;
-} EdgePtr;
+typedef Sortlist::List EdgeList;
+typedef Sortlist::ElementPtr EdgePtr;
typedef struct {
Point top;
Point middle;
Point bottom;
- EdgePtr prev, next;
} Edge;
+typedef Sortlist::List EventQueue;
+typedef Sortlist::ElementPtr EventPtr;
+
+*Edge ElementEdge(EdgePtr e) = e.element->value;
+
typedef enum {
Start, Intersect, Stop
} EventType;
-typedef Event;
-
-typedef union {
- *Event elt;
- void nil;
-} EventPtr;
-
typedef struct {
EventType type;
EdgePtr e1;
EdgePtr e2;
Point point;
RationalPoint rational_point;
- EventPtr prev, next;
} Event;
-bool slope_greater (Edge a, Edge b)
+*Event ElementEvent(EventPtr e) = e.element->value;
+
+bool slope_greater (&Edge a, &Edge b)
{
int adx = a.bottom.x - a.top.x;
int bdx = b.bottom.x - b.top.x;
@@ -71,7 +68,7 @@
return adx * bdy > ady * bdx;
}
-bool slope_equal (Edge a, Edge b)
+bool slope_equal (&Edge a, &Edge b)
{
int adx = a.bottom.x - a.top.x;
int bdx = b.bottom.x - b.top.x;
@@ -82,7 +79,7 @@
return adx * bdy == ady * bdx;
}
-bool event_greater (Event a, Event b)
+bool event_greater (&Event a, &Event b)
{
/* The major motion of the sweep line is vertical
* (top-to-bottom). */
@@ -93,8 +90,8 @@
/* 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;
+ bool a_horiz = ElementEdge(a.e1)->top.y == ElementEdge(a.e1)->bottom.y;
+ bool b_horiz = ElementEdge(b.e1)->top.y == ElementEdge(b.e1)->bottom.y;
/* Even with the same Y-value, further vertical discrimination is
* determined by the event type for non-horizontal edges. Due to
@@ -161,11 +158,11 @@
* 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 (! slope_equal (ElementEdge(a.e1), ElementEdge(b.e1)))
if (a.type == EventType.Start)
- return slope_greater (*a.e1.elt, *b.e1.elt);
+ return slope_greater (ElementEdge (a.e1), ElementEdge (b.e1));
else
- return ! slope_greater (*a.e1.elt, *b.e1.elt);
+ return ! slope_greater (ElementEdge (a.e1), ElementEdge (b.e1));
/* As a final discrimination, look at the opposite point. This
* leaves ambiguities only for identical edges.
@@ -174,16 +171,18 @@
* my sort check from returning a false negaative.
*/
if (a.type == EventType.Start)
- return point_greater (b.e1.elt->bottom, a.e1.elt->bottom);
+ return point_greater (ElementEdge (b.e1)->bottom,
+ ElementEdge (a.e1)->bottom);
else
- return point_greater (a.e1.elt->top, b.e1.elt->top);
+ return point_greater (ElementEdge (a.e1)->top,
+ ElementEdge (b.e1)->top);
}
exception parallel (void);
exception no_intersection (void);
-RationalPoint intersect_lines (Edge a, Edge b)
+RationalPoint intersect_lines (&Edge a, &Edge b)
{
int det (int a, int b, int c, int d) {
return a * d - b * c;
@@ -222,9 +221,9 @@
/* XXX: As should be obvious, this function is a bit simpler in the
* absence of horizontal edges */
-RationalPoint intersect_segments (Edge a, Edge b)
+RationalPoint intersect_segments (&Edge a, &Edge b)
{
- RationalPoint intersection = intersect_lines (a, b);
+ RationalPoint intersection = intersect_lines (&a, &b);
if (a.top.y == a.bottom.y) {
if (intersection.x <= a.top.x || intersection.x >= a.bottom.x)
@@ -247,27 +246,31 @@
bool event_ptr_greater (EventPtr a, EventPtr b)
{
- return event_greater (*a.elt, *b.elt);
+ return event_greater (ElementEvent (a), ElementEvent (b));
}
-void fprint_edge (file f, Edge e)
+void fprint_edge (file f, &Edge e)
{
fprintf (f, "(%2d, %2d)-(%2d, %2d)",
e.top.x, e.top.y,
e.bottom.x, e.bottom.y);
}
-void fprint_edge_svg (file svg_file, Edge e)
+void fprint_edge_svg (file svg_file, &Edge e)
{
fprintf (svg_file, "<line x1='%d' y1='%d' x2='%d' y2='%d' />\n",
e.top.x, e.top.y,
e.bottom.x, e.bottom.y);
}
-void fprint_event_queue (file f, EventPtr e)
+void fprint_event_queue (file f, EventQueue queue)
{
- while (e != Sortlist::List.nil) {
- union switch (e.elt->type) {
+ for (EventPtr event_ptr = Sortlist::first(queue);
+ event_ptr != EventPtr.nil;
+ event_ptr = Sortlist::next (queue, event_ptr))
+ {
+ *Event event = ElementEvent (event_ptr);
+ union switch (event->type) {
case Start:
fprintf (f, "Start: ");
break;
@@ -278,25 +281,29 @@
fprintf (f, "Intersect: ");
break;
}
- fprintf (f, "%g:\t", e.elt->point);
- fprint_edge (f, *e.elt->e1.elt);
- if (e.elt->type == EventType.Intersect) {
+ fprintf (f, "%g:\t", event->point);
+ fprint_edge (f, ElementEdge (event->e1));
+ if (event->type == EventType.Intersect) {
fprintf (f, " X ");
- fprint_edge (f, *e.elt->e2.elt);
+ fprint_edge (f, ElementEdge (event->e2));
}
fprintf (f, "\n");
- e = e.elt->next;
}
}
-void fprint_event_queue_svg (file svg_file, EventPtr e)
+void fprint_event_queue_svg (file svg_file, EventQueue queue)
{
int text_y = 214;
- while (e != Sortlist::List.nil) {
+ for (EventPtr event_ptr = Sortlist::first(queue);
+ event_ptr != EventPtr.nil;
+ event_ptr = Sortlist::next (queue, event_ptr))
+ {
+ *Event event = ElementEvent (event_ptr);
+
fprintf (svg_file, "<text stroke='none' fill='black' x='0' y='%d'>\n", text_y);
text_y += 14;
- union switch (e.elt->type) {
+ enum switch (event->type) {
case Start:
fprintf (svg_file, "Start: ");
break;
@@ -307,31 +314,41 @@
fprintf (svg_file, "Intersect: ");
break;
}
- fprintf (svg_file, "%g:\t", e.elt->point);
- fprint_edge (svg_file, *e.elt->e1.elt);
- if (e.elt->type == EventType.Intersect) {
+ fprintf (svg_file, "%g:\t", event->point);
+ fprint_edge (svg_file, ElementEdge (event->e1));
+ if (event->type == EventType.Intersect) {
fprintf (svg_file, " X ");
- fprint_edge (svg_file, *e.elt->e2.elt);
+ fprint_edge (svg_file, ElementEdge (event->e2));
}
fprintf (svg_file, "\n");
- e = e.elt->next;
fprintf (svg_file, "</text>\n");
}
}
-void fprint_sweep_line (file f, EdgePtr e)
+void fprint_sweep_line (file f, EdgeList sweep)
{
- while (e != Sortlist::List.nil) {
- fprint_edge (f, *e.elt);
- e = e.elt->next;
- if (e != Sortlist::List.nil)
+ bool first = true;
+ for (EdgePtr e = Sortlist::first(sweep);
+ e != EdgePtr.nil;
+ e = Sortlist::next (sweep, e))
+ {
+ if (!first)
fprintf (f, ", ");
+ fprint_edge (f, e.element->value);
+ first = false;
}
fprintf (f, "\n");
}
-void print_sweep_line_svg (file svg_file, EdgePtr sweep_line, Edge[*] segments, EventPtr event_queue, EventPtr event, int current_y)
+void print_sweep_line_svg (file svg_file,
+ EdgeList sweep_line,
+ Edge[*] segments,
+ EventQueue event_queue,
+ EventPtr event_ptr,
+ int current_y)
{
+ *Event event = ElementEvent (event_ptr);
+
fprintf (svg_file, "<?xml version='1.0' standalone='no'?>\n");
fprintf (svg_file, "<!DOCTYPE svg PUBLIC '-//W3C//DTD SVG 20001102//EN'\n");
fprintf (svg_file, " 'http://www.w3.org/TR/2000/CR-SVG-20001102/DTD/svg-20001102.dtd'>\n");
@@ -339,34 +356,43 @@
fprintf (svg_file, "<g transform='scale(30,30)' stroke-width='.05'>\n");
for (int i=0; i < dim(segments); i++) {
- fprint_edge_svg (svg_file, segments[i]);
+ fprint_edge_svg (svg_file, &segments[i]);
}
fprintf (svg_file, "</g>\n");
fprintf (svg_file, "<text stroke='none' fill='blue' x='0' y='200'>\n");
- EdgePtr e = sweep_line;
- while (e != Sortlist::List.nil) {
- fprint_edge (svg_file, *e.elt);
- if (e != Sortlist::List.nil)
+
+ bool first = true;
+ for (
+ EdgePtr e = Sortlist::first (sweep_line);
+ e != EdgePtr.nil;
+ e = Sortlist::next (sweep_line, e))
+ {
+ if (!first)
fprintf (svg_file, ", ");
- e = e.elt->next;
+ fprint_edge (svg_file, e.element->value);
+ first = false;
}
fprintf (svg_file, "</text>\n");
fprintf (svg_file, "<g transform='scale(30,30)' stroke='blue' stroke-width='.05'>\n");
- EdgePtr e = sweep_line;
+
int edge_cnt = 0;
- while (e != Sortlist::List.nil) {
- fprint_edge_svg (svg_file, *e.elt);
+ for (EdgePtr edge_ptr = Sortlist::first (sweep_line);
+ edge_ptr != EdgePtr.nil;
+ edge_ptr = Sortlist::next (sweep_line, edge_ptr))
+ {
+ *Edge edge = ElementEdge (edge_ptr);
+ fprint_edge_svg (svg_file, edge);
fprintf (svg_file, "<text font-size='.4' fill='blue' stroke='none' x='%g' y='%g'>%d</text>\n",
- e.elt->top.x + .1, e.elt->top.y - .1, edge_cnt++);
- e = e.elt->next;
+ edge->top.x + .1, edge->top.y - .1, edge_cnt++);
}
fprintf (svg_file, "<line x1='-10' y1='%d' x2='100' y2='%d' stroke-width='.05' stroke='red' />\n",
current_y, current_y);
fprintf (svg_file, "<text font-size='.4' fill='red' stroke='none' x='15' y='%g'>%d</text>\n", current_y - .1, current_y);
- fprintf (svg_file, "<circle cx='%d' cy='%d' r='.15' stroke='none' fill='green'/>\n", event.elt->point.x, event.elt->point.y);
+ fprintf (svg_file, "<circle cx='%d' cy='%d' r='.15' stroke='none' fill='green'/>\n",
+ event->point.x, event->point.y);
fprintf (svg_file, "</g>\n");
fprint_event_queue_svg (svg_file, event_queue);
@@ -378,7 +404,7 @@
bentley_ottman (Edge[*] segments, &int intersection_count)
{
intersection_count = 0;
- EventPtr event_queue = Sortlist::List.nil;
+ EventQueue event_queue = Sortlist::new (event_greater);
Edge[...] result = {};
Edge[*] remove_degenerate (Edge[*] edges) {
@@ -400,13 +426,11 @@
return non_horizontal;
}
- EventPtr initialize_event_queue (Edge[*] segments) {
- Event[...] events = {};
-
- segments = remove_degenerate (segments);
+ void initialize_event_queue (Edge[*] segments) {
/*
- segments = remove_horizontal (segments);
+ segments = remove_degenerate (segments);
*/
+ segments = remove_horizontal (segments);
for (int i=0; i < dim(segments); i++) {
if (point_greater (segments[i].top, segments[i].bottom)) {
@@ -416,85 +440,46 @@
segments[i].bottom = tmp;
}
segments[i].middle = segments[i].top;
+ }
+
+ EdgePtr[dim(segments)] edges = { [i] = Sortlist::element (&segments[i]) };
- events[i*2] = (Event) {
+ for (int i=0; i < dim(edges); i++)
+ {
+ EventPtr start = Sortlist::element (&(Event) {
type = EventType.Start,
- e1 = (EdgePtr.elt) &segments[i],
+ e1 = edges[i],
point = segments[i].top,
- rational_point = segments[i].top,
- prev = Sortlist::List.nil,
- next = Sortlist::List.nil
- };
- events[i*2+1] = (Event) {
+ rational_point = segments[i].top
+ });
+
+ Sortlist::insert (event_queue, start);
+
+ EventPtr stop = Sortlist::element (&(Event) {
type = EventType.Stop,
- e1 = (EdgePtr.elt) &segments[i],
+ e1 = edges[i],
point = segments[i].bottom,
- rational_point = segments[i].bottom,
- prev = Sortlist::List.nil,
- next = Sortlist::List.nil
- };
- }
-
- 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 {
- 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");
- }
-*/
+ rational_point = segments[i].bottom
+ });
- 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];
+ Sortlist::insert (event_queue, stop);
}
-
- return (EventPtr.elt) &events[0];
}
- event_queue = initialize_event_queue (segments);
+ initialize_event_queue (segments);
- int current_y = event_queue.elt->point.y;
+ int current_y;
- bool edge_greater (EdgePtr a, EdgePtr b) {
+ bool edge_greater (*Edge a, *Edge b) {
- rational edge_x_for_y (EdgePtr e, int y) {
- int dx = e.elt->bottom.x - e.elt->top.x;
- int dy = e.elt->bottom.y - e.elt->top.y;
+ 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;
if (dy == 0)
- return e.elt->top.x;
+ return e->top.x;
- return e.elt->top.x + (y - e.elt->top.y) * dx / dy;
+ return e->top.x + (y - e->top.y) * dx / dy;
}
rational ax = edge_x_for_y (a, current_y);
@@ -504,113 +489,139 @@
return ax > bx;
/* Slope comparison */
- return slope_greater (*a.elt, *b.elt);
+ return slope_greater (a, b);
}
/*
- bool edge_greater (EdgePtr a, EdgePtr b) {
- int adx = a.elt->bottom.x - a.elt->top.x;
- int bdx = b.elt->bottom.x - b.elt->top.x;
+ bool edge_greater (*Edge a, *Edge b) {
+ int adx = a->bottom.x - a->top.x;
+ int bdx = b->bottom.x - b->top.x;
- int ady = a.elt->bottom.y - a.elt->top.y;
- int bdy = b.elt->bottom.y - b.elt->top.y;
+ int ady = a->bottom.y - a->top.y;
+ int bdy = b->bottom.y - b->top.y;
- if (ady == 0)
- ax = a.elt->top.x;
- else
- ax = a.elt->top.x + (current_y - a.elt->top.y) * adx / ady;
+ if (ady == 0)
+ ax = a.elt->top.x;
+ else
+ ax = a.elt->top.x + (current_y - a.elt->top.y) * adx / ady;
+ if (bdy == 0)
+ bx = b.elt->top.x;
+ else
+ bx = b.elt->top.x + (current_y - b.elt->top.y) * bdx / bdy;
- if (bdy == 0)
- bx = b.elt->top.x;
- else
- bx = b.elt->top.x + (current_y - b.elt->top.y) * bdx / bdy;
+ if (ax != bx)
+ return ax > bx;
- return ax > bx;
+ return slope_greater (a, b);
}
*/
- EdgePtr sweep_line = Sortlist::List.nil;
+ EdgeList sweep_line = Sortlist::new (edge_greater);
void insert_event_if_intersect_below_current_y (EdgePtr left, EdgePtr right) {
- if (left == Sortlist::List.nil || right == Sortlist::List.nil)
+ if (left == EdgePtr.nil || right == EdgePtr.nil)
return;
/* A slope comparison tells us if the intersection is before current_y */
- if (slope_greater (*right.elt, *left.elt))
+ if (slope_greater (ElementEdge (right), ElementEdge (left)))
return;
RationalPoint intersection;
try {
- intersection = intersect_segments (*left.elt, *right.elt);
+ intersection = intersect_segments (ElementEdge (left),
+ ElementEdge (right));
} catch parallel () {
return;
} catch no_intersection () {
return;
}
- 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),
- },
- rational_point = intersection
- },
- event_ptr_greater);
+ EventPtr intersect = Sortlist::element ( &(Event) {
+ type = EventType.Intersect,
+ e1 = left,
+ e2 = right,
+ point = {
+ x = floor (intersection.x + 0.5),
+ y = floor (intersection.y + 0.5),
+ },
+ rational_point = intersection
+ });
+
+ Sortlist::insert (event_queue, intersect);
+
+ if (VALIDATE_SORT)
+ Sortlist::validate (event_queue);
}
- while (event_queue != Sortlist::List.nil) {
+ while ((EventPtr event_ptr = Sortlist::first (event_queue)) != EventPtr.nil)
+ {
+ *Event event = ElementEvent(event_ptr);
file svg_file;
- EventPtr event = event_queue;
- current_y = event.elt->point.y;
+ current_y = event->point.y;
-/*
- string filename;
- 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);
-*/
+ if (true)
+ {
+ string filename;
+ 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_ptr, current_y);
+ close (svg_file);
+ }
- event_queue = event_queue.elt->next;
- if (event_queue != Sortlist::List.nil)
- event_queue.elt->prev = Sortlist::List.nil;
+ if (false)
+ {
+ printf ("%3d: type %g y %g sweep: ", FRAME_COUNT-1, event->type, current_y);
+ fprint_sweep_line (stdout, sweep_line);
+ }
+
+ Sortlist::delete (event_queue, event_ptr);
- union switch (event.elt->type) {
+ enum switch (event->type) {
case Start:
- EdgePtr edge, left, right;
+ EdgePtr edge = event->e1;
+
+ if (VALIDATE_SORT)
+ Sortlist::validate (sweep_line);
- edge = event.elt->e1;
- Sortlist::insert (&sweep_line, edge, edge_greater);
- left = edge.elt->prev;
- right = edge.elt->next;
+ Sortlist::insert (sweep_line, edge);
+
+ if (VALIDATE_SORT)
+ Sortlist::validate (sweep_line);
+
+ EdgePtr left = Sortlist::prev (sweep_line, edge);
+ EdgePtr right = Sortlist::next (sweep_line, edge);
+
insert_event_if_intersect_below_current_y (left, edge);
+
insert_event_if_intersect_below_current_y (edge, right);
+
break;
case Stop:
- EdgePtr edge, left, right;
-
+ EdgePtr edge = event->e1;
+
result[dim(result)] = (Edge) {
- top = event.elt->e1.elt->middle,
- bottom = event.elt->point
+ top = ElementEdge(edge)->middle,
+ bottom = event->point
};
+
+ EdgePtr left = Sortlist::prev (sweep_line, edge);
+ EdgePtr right = Sortlist::next (sweep_line, edge);
+
+ Sortlist::delete (sweep_line, edge);
- edge = event.elt->e1;
- left = edge.elt->prev;
- right = edge.elt->next;
- Sortlist::delete (&sweep_line, edge);
insert_event_if_intersect_below_current_y (left, right);
+
break;
case Intersect:
- EdgePtr e1, e2, left, right;
+
+ EdgePtr e1 = event->e1;
+ EdgePtr e2 = event->e2;
/* skip this intersection if its edges are not adjacent */
- if (event.elt->e1.elt->next != event.elt->e2)
+ if (e2 != Sortlist::next (sweep_line, e1))
break;
intersection_count++;
@@ -618,29 +629,32 @@
/* 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)
+ if (ElementEdge(e1)->middle != event->point)
result[dim(result)] = (Edge) {
- top = event.elt->e1.elt->middle,
- bottom = event.elt->point
+ top = ElementEdge(e1)->middle,
+ bottom = event->point
};
- if (event.elt->e2.elt->middle != event.elt->point)
+
+ if (ElementEdge(e2)->middle != event->point)
result[dim(result)] = (Edge) {
- top = event.elt->e2.elt->middle,
- bottom = event.elt->point
+ top = ElementEdge(e2)->middle,
+ bottom = event->point
};
- event.elt->e1.elt->middle = event.elt->point;
- event.elt->e2.elt->middle = event.elt->point;
-
- Sortlist::swap (&sweep_line, event.elt->e1);
+
+ ElementEdge(e1)->middle = event->point;
+ ElementEdge(e2)->middle = event->point;
+
+ EdgePtr left = Sortlist::prev (sweep_line, e1);
+ EdgePtr right = Sortlist::next (sweep_line, e2);
+
+ Sortlist::swap (sweep_line, e1);
/* after the swap e2 is left of e1 */
- e2 = event.elt->e2;
- left = e2.elt->prev;
+
insert_event_if_intersect_below_current_y (left, e2);
- e1 = event.elt->e1;
- right = e1.elt->next;
insert_event_if_intersect_below_current_y (e1, right);
+
break;
}
}
@@ -667,10 +681,9 @@
return edges;
}
-bool edges_have_an_intersection_quadratic (Edge[*] edges)
+bool edges_have_an_intersection_quadratic (&Edge[*] edges)
{
RationalPoint intersection;
- Edge a, b;
for (int i=0; i < dim(edges); i++) {
if (point_greater (edges[i].top, edges[i].bottom)) {
@@ -684,10 +697,10 @@
for (int j=0; j < dim (edges); j++) {
if (i==j)
continue;
- a = edges[i];
- b = edges[j];
+ &Edge a = &edges[i];
+ &Edge b = &edges[j];
try {
- intersection = intersect_segments (a, b);
+ intersection = intersect_segments (&a, &b);
} catch parallel () {
continue;
} catch no_intersection () {
@@ -715,7 +728,7 @@
Edge[*] intersected_edges = bentley_ottman_iterative (edges, &iterations);
- if (edges_have_an_intersection_quadratic (intersected_edges))
+ if (edges_have_an_intersection_quadratic (&intersected_edges))
printf ("*** FAIL ***");
else
printf ("PASS");
@@ -835,5 +848,4 @@
bottom = { x = PRNG::randint (10), y = PRNG::randint (10) }
};
}
-
run_test ("random", random_edges);
--- kbentley.5c DELETED ---
More information about the Commit
mailing list