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_verify_and_dump(actlist_t*a, int32_t y)
  16 {
  17     segment_t*s = a->list;
  18     assert(!s || !s->left);
  19     double lastx;
  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) fprintf(stderr, "?%f<->%f? ", lastx, x);
  25             }
  26             lastx = x;
  27         }
  28         assert(!s->left || s->left->right == s);
  29         assert(!s->right || s->right->left == s);
  30         fprintf(stderr, "[%d]", s->nr);
  31         s = s->right;
  32         if(s) fprintf(stderr, " ");
  33         else fprintf(stderr, "\n");
  34     }
  35 }
  36
  37 segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
  38 {
  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)
  43      */
  44     segment_t*last=0, *s = a->list;
  45     if(!s) return last;
  46     while(s) {
  47         double d = LINE_EQ(p1, s);
  48         if(d==0) {
  49             d = LINE_EQ(p2, s);
  50             if(d==0) {
  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.
  54                  */
  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);
  56             }
  57         }
  58         if(d<0)
  59             break;
  60         last = s;
  61         s = s->right;
  62     }
  63     return last;
  64 }
  65
  66 static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s)
  67 {
  68     s->left = left;
  69     if(left) {
  70         s->right = left->right;
  71     } else {
  72         s->right = a->list;
  73         a->list = s;
  74     }
  75     if(s->left)
  76         s->left->right = s;
  77     if(s->right)
  78         s->right->left = s;
  79     a->size++;
  80 }
  81
  82 void actlist_insert(actlist_t*a, point_t p, segment_t*s)
  83 {
  84     segment_t*left = actlist_find(a, p, s->b);
  85     actlist_insert_after(a, left, s);
  86 }
  87
  88 void actlist_delete(actlist_t*a, segment_t*s)
  89 {
  90     if(s->left) {
  91         s->left->right = s->right;
  92     } else {
  93         a->list = s->right;
  94     }
  95     if(s->right) {
  96         s->right->left = s->left;
  97     }
  98     s->left = s->right = 0;
  99     a->size--;
 100 }
 101 int actlist_size(actlist_t*a)
 102 {
 103     return a->size;
 104 }
 105
 106 segment_t* actlist_leftmost(actlist_t*a)
 107 {
 108     return a->list;
 109 }
 110
 111 segment_t* actlist_left(actlist_t*a, segment_t*s)
 112 {
 113     return s->left;
 114 }
 115
 116 segment_t* actlist_right(actlist_t*a, segment_t*s)
 117 {
 118     if(s) return s->right;
 119     else  return a->list;
 120 }
 121
 122 void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
 123 {
 124     actlist_delete(a, s1);
 125     actlist_insert_after(a, s2, s1);
 126 }