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
  11 void actlist_verify_and_dump(actlist_t*a, int32_t y)
  12 {
  13     segment_t*s = a->list;
  14     assert(!s || !s->left);
  15     double lastx;
  16     while(s) {
  17         if(y) {
  18             double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x;
  19             if(s!=a->list) {
  20                 if(lastx>x) printf("?%f<->%f? ", lastx, x);
  21             }
  22             lastx = x;
  23         }
  24         assert(!s->left || s->left->right == s);
  25         assert(!s->right || s->right->left == s);
  26         printf("[%d]", s->nr);
  27         s = s->right;
  28         if(s) printf(" ");
  29         else printf("\n");
  30     }
  31 }
  32
  33 segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
  34 {
  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;
  38     if(!s) return last;
  39     while(s) {
  40         double d = LINE_EQ(p1, s);
  41         if(d==0) {
  42             d = LINE_EQ(p2, s);
  43             if(d==0) {
  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.
  47                  */
  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);
  49             }
  50         }
  51         if(d<0)
  52             break;
  53         last = s;
  54         s = s->right;
  55     }
  56     return last;
  57 }
  58
  59 static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s)
  60 {
  61     s->left = left;
  62     if(left) {
  63         s->right = left->right;
  64     } else {
  65         s->right = a->list;
  66         a->list = s;
  67     }
  68     if(s->left)
  69         s->left->right = s;
  70     if(s->right)
  71         s->right->left = s;
  72 }
  73
  74 void actlist_insert(actlist_t*a, point_t p, segment_t*s)
  75 {
  76     segment_t*left = actlist_find(a, p, s->b);
  77     actlist_insert_after(a, left, s);
  78 }
  79
  80 void actlist_delete(actlist_t*a, segment_t*s)
  81 {
  82     if(s->left) {
  83         s->left->right = s->right;
  84     } else {
  85         a->list = s->right;
  86     }
  87     if(s->right) {
  88         s->right->left = s->left;
  89     }
  90     s->left = s->right = 0;
  91 }
  92
  93 segment_t* actlist_leftmost(actlist_t*a)
  94 {
  95     return a->list;
  96 }
  97
  98 segment_t* actlist_left(actlist_t*a, segment_t*s)
  99 {
 100     return s->left;
 101 }
 102
 103 segment_t* actlist_right(actlist_t*a, segment_t*s)
 104 {
 105     return s->right;
 106 }
 107
 108 void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
 109 {
 110     actlist_delete(a, s1);
 111     actlist_insert_after(a, s2, s1);
 112 }
 113
 114 void actlist_invert_fromto(actlist_t*a, segment_t*s1, segment_t*s2)
 115 {
 116     segment_t*left = s1->left;
 117     segment_t*right = s2->right;
 118     segment_t*s = s1;
 119     assert(s!=s2);
 120     while(1) {
 121         assert(s);
 122         segment_t*l = s->left;
 123         segment_t*r = s->right;
 124         s->left = r;
 125         s->right = l;
 126         if(s==s2)
 127             break;
 128         s = r;
 129     }
 130     s2->left = left;
 131     s1->right = right;
 132     if(left) {
 133         left->right = s2;
 134     } else {
 135         assert(a->list == s1);
 136         a->list = s2;
 137     }
 138     if(right) {
 139         right->left = s1;
 140     }
 141 }