lib/gfxpoly/active.c

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