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 }
  80
  81 void actlist_insert(actlist_t*a, point_t p, segment_t*s)
  82 {
  83     segment_t*left = actlist_find(a, p, s->b);
  84     actlist_insert_after(a, left, s);
  85 }
  86
  87 void actlist_delete(actlist_t*a, segment_t*s)
  88 {
  89     if(s->left) {
  90         s->left->right = s->right;
  91     } else {
  92         a->list = s->right;
  93     }
  94     if(s->right) {
  95         s->right->left = s->left;
  96     }
  97     s->left = s->right = 0;
  98 }
  99
 100 segment_t* actlist_leftmost(actlist_t*a)
 101 {
 102     return a->list;
 103 }
 104
 105 segment_t* actlist_left(actlist_t*a, segment_t*s)
 106 {
 107     return s->left;
 108 }
 109
 110 segment_t* actlist_right(actlist_t*a, segment_t*s)
 111 {
 112     return s->right;
 113 }
 114
 115 void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
 116 {
 117     actlist_delete(a, s1);
 118     actlist_insert_after(a, s2, s1);
 119 }