lib/gfxpoly/active.c

   1 #include "../q.h"
   2 #include "active.h"
   3
   4 actlist_t* actlist_new()
   5 {
   6     NEW(actlist_t, a);
   7     return a;
   8 }
   9 void actlist_destroy(actlist_t*a)
  10 {
  11     free(a);
  12 }
  13
  14 void actlist_dump(actlist_t*a, int32_t y)
  15 {
  16     segment_t*s = a->list;
  17     double lastx;
  18     char bad = 0;
  19     while(s) {
  20         if(y) {
  21             double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x;
  22             if(s!=a->list) {
  23                 if(lastx>x)
  24                     fprintf(stderr, "?%f<->%f? ", lastx, x);
  25             }
  26             lastx = x;
  27         }
  28         fprintf(stderr, "[%d]", s->nr);
  29         s = s->right;
  30         if(s) fprintf(stderr, " ");
  31         else fprintf(stderr, "\n");
  32     }
  33 }
  34 void actlist_verify(actlist_t*a, int32_t y)
  35 {
  36     segment_t*s = a->list;
  37     assert(!s || !s->left);
  38     double lastx;
  39     while(s) {
  40         if(y) {
  41             double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x;
  42             if(s!=a->list) {
  43                 assert(lastx<=x);
  44             }
  45             lastx = x;
  46         }
  47         assert(!s->left || s->left->right == s);
  48         assert(!s->right || s->right->left == s);
  49         s = s->right;
  50     }
  51 }
  52
  53 segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
  54 {
  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)
  59      */
  60     segment_t*last=0, *s = a->list;
  61     if(!s) return last;
  62     while(s) {
  63         double d = LINE_EQ(p1, s);
  64         if(d==0) {
  65             d = LINE_EQ(p2, s);
  66             if(d==0) {
  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.
  70                  */
  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);
  72             }
  73         }
  74         if(d<0)
  75             break;
  76         last = s;
  77         s = s->right;
  78     }
  79     return last;
  80 }
  81
  82 static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s)
  83 {
  84     s->left = left;
  85     if(left) {
  86         s->right = left->right;
  87     } else {
  88         s->right = a->list;
  89         a->list = s;
  90     }
  91     if(s->left)
  92         s->left->right = s;
  93     if(s->right)
  94         s->right->left = s;
  95     a->size++;
  96 }
  97
  98 void actlist_insert(actlist_t*a, point_t p, segment_t*s)
  99 {
 100     segment_t*left = actlist_find(a, p, s->b);
 101     actlist_insert_after(a, left, s);
 102 }
 103
 104 void actlist_delete(actlist_t*a, segment_t*s)
 105 {
 106     if(s->left) {
 107         s->left->right = s->right;
 108     } else {
 109         a->list = s->right;
 110     }
 111     if(s->right) {
 112         s->right->left = s->left;
 113     }
 114     s->left = s->right = 0;
 115     a->size--;
 116 }
 117 int actlist_size(actlist_t*a)
 118 {
 119     return a->size;
 120 }
 121
 122 segment_t* actlist_leftmost(actlist_t*a)
 123 {
 124     return a->list;
 125 }
 126
 127 segment_t* actlist_rightmost(actlist_t*a)
 128 {
 129     /* this is only used in checks, so it doesn't matter that it's slow */
 130     segment_t*s = a->list;
 131     segment_t*last = 0;
 132     while(s) {
 133         last = s;
 134         s = s->right;
 135     }
 136     return last;
 137 }
 138
 139 segment_t* actlist_left(actlist_t*a, segment_t*s)
 140 {
 141     return s->left;
 142 }
 143
 144 segment_t* actlist_right(actlist_t*a, segment_t*s)
 145 {
 146     if(s) return s->right;
 147     else  return a->list;
 148 }
 149
 150 void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
 151 {
 152     actlist_delete(a, s1);
 153     actlist_insert_after(a, s2, s1);
 154 }