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);
42 /* we need to re-evaluate the x of the previous segment. if we
43 try to store it, it might end up being converted to a double,
44 which will make it non-equal to (and possibly larger than) the
45 "long double" the FPU has in it's register. This only happens
46 when compiler optimizations are turned on. */
47 assert((XPOS(s, y) - XPOS(l, y)) >= 0);
48 assert(XDIFF(s,l,y) >= 0);
52 assert(!s->left || s->left->right == s);
53 assert(!s->right || s->right->left == s);
58 segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
60 /* this runs in O(n) right now, and should be optimized using a splay
61 tree to run in ammortized O(log(n))
62 (update: currently only 2.5% of the algorithm's running time is spent here,
63 so maybe we don't need to bother)
65 segment_t*last=0, *s = a->list;
68 double d = LINE_EQ(p1, s);
72 /* We default to always inserting the new segment to the right of the old segment.
73 We do this so that we don't place new segments into the middle of already
74 overlapping lines which may have intersections scheduled.
76 //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);
87 static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s)
91 s->right = left->right;
103 void actlist_insert(actlist_t*a, point_t p, segment_t*s)
105 segment_t*left = actlist_find(a, p, s->b);
106 actlist_insert_after(a, left, s);
109 void actlist_delete(actlist_t*a, segment_t*s)
112 s->left->right = s->right;
117 s->right->left = s->left;
119 s->left = s->right = 0;
122 int actlist_size(actlist_t*a)
127 segment_t* actlist_leftmost(actlist_t*a)
132 segment_t* actlist_rightmost(actlist_t*a)
134 /* this is only used in checks, so it doesn't matter that it's slow */
135 segment_t*s = a->list;
144 segment_t* actlist_left(actlist_t*a, segment_t*s)
149 segment_t* actlist_right(actlist_t*a, segment_t*s)
151 if(s) return s->right;
155 void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
157 actlist_delete(a, s1);
158 actlist_insert_after(a, s2, s1);