4 actlist_t* actlist_new()
9 void actlist_destroy(actlist_t*a)
14 void actlist_dump(actlist_t*a, int32_t y)
16 segment_t*s = a->list;
21 double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x;
24 fprintf(stderr, "?%f<->%f? ", lastx, x);
28 fprintf(stderr, "[%d]", s->nr);
30 if(s) fprintf(stderr, " ");
31 else fprintf(stderr, "\n");
34 void actlist_verify(actlist_t*a, int32_t y)
36 segment_t*s = a->list;
37 assert(!s || !s->left);
41 double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x;
47 assert(!s->left || s->left->right == s);
48 assert(!s->right || s->right->left == s);
53 segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
55 /* this runs in O(n) right now, and should be optimized using a splay
56 tree to run in ammortized O(log(n))
57 (update: currently only 2.5% of the algorithm's running time is spent here,
58 so maybe we don't need to bother)
60 segment_t*last=0, *s = a->list;
63 double d = LINE_EQ(p1, s);
67 /* We default to always inserting the new segment to the right of the old segment.
68 We do this so that we don't place new segments into the middle of already
69 overlapping lines which may have intersections scheduled.
71 //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);
82 static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s)
86 s->right = left->right;
98 void actlist_insert(actlist_t*a, point_t p, segment_t*s)
100 segment_t*left = actlist_find(a, p, s->b);
101 actlist_insert_after(a, left, s);
104 void actlist_delete(actlist_t*a, segment_t*s)
107 s->left->right = s->right;
112 s->right->left = s->left;
114 s->left = s->right = 0;
117 int actlist_size(actlist_t*a)
122 segment_t* actlist_leftmost(actlist_t*a)
127 segment_t* actlist_rightmost(actlist_t*a)
129 /* this is only used in checks, so it doesn't matter that it's slow */
130 segment_t*s = a->list;
139 segment_t* actlist_left(actlist_t*a, segment_t*s)
144 segment_t* actlist_right(actlist_t*a, segment_t*s)
146 if(s) return s->right;
150 void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
152 actlist_delete(a, s1);
153 actlist_insert_after(a, s2, s1);