5 actlist_t* actlist_new()
10 void actlist_destroy(actlist_t*a)
15 void actlist_dump(actlist_t*a, int32_t y)
17 segment_t*s = a->list;
22 double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x;
25 fprintf(stderr, "?%f<->%f? ", lastx, x);
29 fprintf(stderr, "[%d]", s->nr);
31 if(s) fprintf(stderr, " ");
32 else fprintf(stderr, "\n");
35 void actlist_verify(actlist_t*a, int32_t y)
37 segment_t*s = a->list;
38 assert(!s || !s->left);
42 double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x;
48 assert(!s->left || s->left->right == s);
49 assert(!s->right || s->right->left == s);
54 segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
56 /* this runs in O(n) right now, and should be optimized using a splay
57 tree to run in ammortized O(log(n))
58 (update: currently only 2.5% of the algorithm's running time is spent here,
59 so maybe we don't need to bother)
61 segment_t*last=0, *s = a->list;
64 double d = LINE_EQ(p1, s);
68 /* We default to always inserting the new segment to the right of the old segment.
69 We do this so that we don't place new segments into the middle of already
70 overlapping lines which may have intersections scheduled.
72 //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);
83 static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s)
87 s->right = left->right;
99 void actlist_insert(actlist_t*a, point_t p, segment_t*s)
101 segment_t*left = actlist_find(a, p, s->b);
102 actlist_insert_after(a, left, s);
105 void actlist_delete(actlist_t*a, segment_t*s)
108 s->left->right = s->right;
113 s->right->left = s->left;
115 s->left = s->right = 0;
118 int actlist_size(actlist_t*a)
123 segment_t* actlist_leftmost(actlist_t*a)
128 segment_t* actlist_rightmost(actlist_t*a)
130 /* this is only used in checks, so it doesn't matter that it's slow */
131 segment_t*s = a->list;
140 segment_t* actlist_left(actlist_t*a, segment_t*s)
145 segment_t* actlist_right(actlist_t*a, segment_t*s)
147 if(s) return s->right;
151 void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
153 actlist_delete(a, s1);
154 actlist_insert_after(a, s2, s1);