5 actlist_t* actlist_new()
10 void actlist_destroy(actlist_t*a)
15 void actlist_verify_and_dump(actlist_t*a, int32_t y)
17 segment_t*s = a->list;
18 assert(!s || !s->left);
22 double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x;
24 if(lastx>x) fprintf(stderr, "?%f<->%f? ", lastx, x);
28 assert(!s->left || s->left->right == s);
29 assert(!s->right || s->right->left == s);
30 fprintf(stderr, "[%d]", s->nr);
32 if(s) fprintf(stderr, " ");
33 else fprintf(stderr, "\n");
37 segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
39 /* this runs in O(n) right now, and should be optimized using a splay
40 tree to run in ammortized O(log(n))
41 (update: currently only 2.5% of the algorithm's running time is spent here,
42 so maybe we don't need to bother)
44 segment_t*last=0, *s = a->list;
47 double d = LINE_EQ(p1, s);
51 /* We default to always inserting the new segment to the right of the old segment.
52 We do this so that we don't place new segments into the middle of already
53 overlapping lines which may have intersections scheduled.
55 //fprintf(stderr, "Notice: actlist_find: both points (%d,%d) and (%d,%d) exactly on segment [%d]\n", p1.x, p1.y, p2.x, p2.y, s->nr);
66 static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s)
70 s->right = left->right;
82 void actlist_insert(actlist_t*a, point_t p, segment_t*s)
84 segment_t*left = actlist_find(a, p, s->b);
85 actlist_insert_after(a, left, s);
88 void actlist_delete(actlist_t*a, segment_t*s)
91 s->left->right = s->right;
96 s->right->left = s->left;
98 s->left = s->right = 0;
101 int actlist_size(actlist_t*a)
106 segment_t* actlist_leftmost(actlist_t*a)
111 segment_t* actlist_left(actlist_t*a, segment_t*s)
116 segment_t* actlist_right(actlist_t*a, segment_t*s)
118 if(s) return s->right;
122 void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
124 actlist_delete(a, s1);
125 actlist_insert_after(a, s2, s1);