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;
81 void actlist_insert(actlist_t*a, point_t p, segment_t*s)
83 segment_t*left = actlist_find(a, p, s->b);
84 actlist_insert_after(a, left, s);
87 void actlist_delete(actlist_t*a, segment_t*s)
90 s->left->right = s->right;
95 s->right->left = s->left;
97 s->left = s->right = 0;
100 segment_t* actlist_leftmost(actlist_t*a)
105 segment_t* actlist_left(actlist_t*a, segment_t*s)
110 segment_t* actlist_right(actlist_t*a, segment_t*s)
115 void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
117 actlist_delete(a, s1);
118 actlist_insert_after(a, s2, s1);