5 actlist_t* actlist_new()
11 void actlist_verify_and_dump(actlist_t*a, int32_t y)
13 segment_t*s = a->list;
14 assert(!s || !s->left);
18 double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x;
20 if(lastx>x) printf("?%f<->%f? ", lastx, x);
24 assert(!s->left || s->left->right == s);
25 assert(!s->right || s->right->left == s);
26 printf("[%d]", s->nr);
33 segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
35 /* this runs in O(n) right now, and should be optimized using a splay
36 tree to run in ammortized O(log(n)) */
37 segment_t*last=0, *s = a->list;
40 double d = LINE_EQ(p1, s);
44 /* We default to always inserting the new segment to the right of the old segment.
45 We do this so that we don't place new segments into the middle of already
46 overlapping lines which may have intersections scheduled.
48 //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);
59 static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s)
63 s->right = left->right;
74 void actlist_insert(actlist_t*a, point_t p, segment_t*s)
76 segment_t*left = actlist_find(a, p, s->b);
77 actlist_insert_after(a, left, s);
80 void actlist_delete(actlist_t*a, segment_t*s)
83 s->left->right = s->right;
88 s->right->left = s->left;
90 s->left = s->right = 0;
93 segment_t* actlist_leftmost(actlist_t*a)
98 segment_t* actlist_left(actlist_t*a, segment_t*s)
103 segment_t* actlist_right(actlist_t*a, segment_t*s)
108 void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
110 actlist_delete(a, s1);
111 actlist_insert_after(a, s2, s1);
114 void actlist_invert_fromto(actlist_t*a, segment_t*s1, segment_t*s2)
116 segment_t*left = s1->left;
117 segment_t*right = s2->right;
122 segment_t*l = s->left;
123 segment_t*r = s->right;
135 assert(a->list == s1);