lib/gfxpoly/active.c

   1 #include <memory.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     if(!s) fprintf(stderr, "(empty)\n");
  21     while(s) {
  22         if(y) {
  23             double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x;
  24             if(s!=a->list) {
  25                 if(lastx>x)
  26                     fprintf(stderr, "?%f<->%f? ", lastx, x);
  27             }
  28             lastx = x;
  29         }
  30         fprintf(stderr, "[%d]", s->nr);
  31         s = s->right;
  32         if(s) fprintf(stderr, " ");
  33         else fprintf(stderr, "\n");
  34     }
  35 }
  36 void actlist_verify(actlist_t*a, int32_t y)
  37 {
  38     segment_t*s = a->list;
  39     assert(!s || !s->left);
  40     segment_t*l = 0;
  41     while(s) {
  42         if(y) {
  43             if(l) {
  44                 /* we need to re-evaluate the x of the previous segment. if we
  45                    try to store it, it might end up being converted to a double,
  46                    which will make it non-equal to (and possibly larger than) the
  47                    "long double" the FPU has in it's register. This only happens
  48                    when compiler optimizations are turned on. */
  49                 assert((XPOS(s, y) - XPOS(l, y)) >= 0);
  50                 assert(XDIFF(s,l,y) >= 0);
  51             }
  52             l = s;
  53         }
  54         assert(!s->left || s->left->right == s);
  55         assert(!s->right || s->right->left == s);
  56         s = s->right;
  57     }
  58 }
  59
  60 static inline double cmp(segment_t*s, point_t p1, point_t p2)
  61 {
  62     double d = LINE_EQ(p1, s);
  63     if(d==0) {
  64         d = LINE_EQ(p2, s);
  65         if(d==0) {
  66             /* We default to always inserting the new segment to the right of the old segment.
  67                We do this so that we don't place new segments into the middle of already
  68                overlapping lines which may have intersections scheduled.
  69              */
  70             //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);
  71         }
  72     }
  73     return d;
  74 }
  75
  76 segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
  77 {
  78     /* this runs in O(n) right now, and should be optimized using a splay
  79        tree to run in ammortized O(log(n))
  80        (update: currently only 2.5% of the algorithm's running time is spent here,
  81         so maybe we don't need to bother)
  82      */
  83     segment_t*last=0, *s = a->list;
  84     if(!s) return last;
  85     while(s) {
  86         double d = cmp(s, p1, p2);
  87         if(d<0)
  88             break;
  89         last = s;
  90         s = s->right;
  91     }
  92     return last;
  93 }
  94
  95 #define SEGNR(s) ((s)?(s)->nr:-1)
  96 #ifdef SPLAY
  97
  98 #define LINK(node,side,child) (node)->side = (child);if(child) {(child)->parent = (node);}
  99  //;fprintf(stderr, "[%d]->%s now [%d]\n", SEGNR(node), __STRING(side), SEGNR(child));
 100
 101 // rotates segment's left node to the top
 102 static inline segment_t*rotate_right(actlist_t*a, segment_t*s)
 103 {
 104     /*      s             n
 105            /               \
 106           n      ->         s
 107            \               /
 108             l             l
 109     */
 110     assert(s->leftchild);
 111     segment_t*p = s->parent;
 112     segment_t*n = s->leftchild;
 113     segment_t*l = n->rightchild;
 114     LINK(n,rightchild,s);
 115     LINK(s,leftchild,l);
 116     n->parent = p;
 117     if(p) {
 118         if(p->leftchild == s)
 119             p->leftchild = n;
 120         else if(p->rightchild == s)
 121             p->rightchild = n;
 122     } else {
 123         a->root = n;
 124     }
 125     return n;
 126 }
 127 // rotates segment's right node to the top
 128 static inline segment_t*rotate_left(actlist_t*a, segment_t*s)
 129 {
 130     /*      s             n
 131              \           /
 132               n  ->     s
 133              /           \
 134             r             r
 135     */
 136     assert(s->rightchild);
 137     segment_t*p = s->parent;
 138     segment_t*n = s->rightchild;
 139     segment_t*r = n->leftchild;
 140     LINK(n,leftchild,s);
 141     LINK(s,rightchild,r);
 142     n->parent = p;
 143     if(p) {
 144         if(p->leftchild == s)
 145             p->leftchild = n;
 146         else if(p->rightchild == s)
 147             p->rightchild = n;
 148     } else {
 149         a->root = n;
 150     }
 151     return n;
 152 }
 153
 154 static int actlist_splay_walk(actlist_t*a, segment_t*s, segment_t**ss, segment_t*parent)
 155 {
 156     if(!s) return 1;
 157     if(parent != s->parent) {
 158         fprintf(stderr, "Parent mismatch in [%d]: [%d] != [%d]\n", SEGNR(s), SEGNR(parent), SEGNR(s->parent));
 159         return 0;
 160     }
 161     if(!actlist_splay_walk(a, s->leftchild, ss, s)) return 0;
 162     if(s != *ss) {
 163         fprintf(stderr, "[%d] != [%d]\n", SEGNR(s), SEGNR(*ss));
 164         return 0;
 165     }
 166     (*ss) = (*ss)->right;
 167     if(!actlist_splay_walk(a, s->rightchild, ss, s)) return 0;
 168     return 1;
 169 }
 170
 171 static int actlist_splay_verify(actlist_t*a)
 172 {
 173     segment_t*c = a->list;
 174     if(!actlist_splay_walk(a, a->root, &c, 0)) return 0;
 175     if(c) return 0;
 176     return 1;
 177 }
 178 static void actlist_splay_dump2(actlist_t*a, segment_t*s, int indent)
 179 {
 180     if(!s) return;
 181     int t;
 182     if(s->leftchild || s->rightchild) {
 183         fprintf(stderr, "(");
 184         fprintf(stderr, "[%d]", SEGNR(s->leftchild));
 185         if(s->leftchild) {
 186             actlist_splay_dump2(a, s->leftchild, indent+8);
 187         }
 188         fprintf(stderr, ",");
 189         fprintf(stderr, "[%d]", SEGNR(s->rightchild));
 190         if(s->rightchild) {
 191             actlist_splay_dump2(a, s->rightchild, indent+8);
 192         }
 193         fprintf(stderr, ")");
 194     }
 195 }
 196 static void actlist_splay_dump(actlist_t*a)
 197 {
 198     fprintf(stderr, "[%d]", SEGNR(a->root));
 199     actlist_splay_dump2(a, a->root, 1);
 200     fprintf(stderr, "\n");
 201 }
 202
 203
 204 static void move_to_root(actlist_t*a, segment_t*s)
 205 {
 206     if(!s) return;
 207     /* this is a textbook implementation of the three splay operations
 208        zig, zig-zig and zig-zag */
 209     int nr=0;
 210     while(a->root != s) {
 211         assert(s->parent);
 212         segment_t*p = s->parent;
 213         if(p == a->root) {
 214             // zig
 215             if(a->root->leftchild == s) {
 216                 rotate_right(a, a->root);
 217             } else {
 218                 rotate_left(a, a->root);
 219             }
 220             assert(a->root == s);
 221         } else {
 222             segment_t*pp = p->parent;
 223             if(p->leftchild == s && pp->leftchild == p) {
 224                 // zig-zig (left)
 225                 rotate_right(a, pp);
 226                 rotate_right(a, s->parent);
 227             } else if(p->rightchild == s && pp->rightchild == p) {
 228                 // zig-zig (right)
 229                 rotate_left(a, pp);
 230                 rotate_left(a, s->parent);
 231             } else if(p->leftchild == s && pp->rightchild == p) {
 232                 // zig-zag (left)
 233                 rotate_right(a, p);
 234                 rotate_left(a, s->parent);
 235             } else if(p->rightchild == s && pp->leftchild == p) {
 236                 // zig-zag (right)
 237                 rotate_left(a, p);
 238                 rotate_right(a, s->parent);
 239             } else {
 240                 assert(0);
 241             }
 242         }
 243     }
 244 }
 245
 246 static int actlist_splay(actlist_t*a, point_t p1, point_t p2)
 247 {
 248     if(!a->list) return;
 249
 250     segment_t tmp;
 251     memset(&tmp, 0, sizeof(tmp));
 252     segment_t*left=&tmp,*right=&tmp;
 253
 254     int c = 0;
 255     while(1) {
 256         if(cmp(a->root,p1,p2)<0) {
 257             /* we're to the left of the root */
 258             if(!a->root->leftchild) {
 259                 c = -1;break;
 260             }
 261             if(cmp(a->root->leftchild,p1,p2)<0) {
 262                 /* we're also to the left of the root's left child
 263                    -> rotate right, so that the left child is root */
 264                 segment_t*s = a->root->leftchild;
 265                 LINK(a->root, leftchild, s->rightchild);
 266                 LINK(s, rightchild, a->root);
 267                 a->root = s;
 268                 if(!a->root->leftchild) {
 269                     c = -1;break;
 270                 }
 271             }
 272             LINK(right, leftchild, a->root);
 273             right = a->root;
 274             a->root = a->root->leftchild;
 275         } else /* cmp(a->root,p1,p2)>=0 */ {
 276             /* we're to the right of the root */
 277             if(!a->root->rightchild) {
 278                 c = 1;break;
 279             }
 280             if(cmp(a->root->rightchild,p1,p2)>=0) {
 281                 /* we're also to the right of the root's right child
 282                    -> rotate left, so that the right child is root */
 283                 segment_t*s = a->root->rightchild;
 284                 LINK(a->root, rightchild, s->leftchild);
 285                 LINK(s, leftchild, a->root);
 286                 a->root = s;
 287                 if(!a->root->rightchild)
 288                     c = 1;break;
 289             }
 290             LINK(left, rightchild, a->root);
 291             left = a->root;
 292             a->root = a->root->rightchild;
 293         }
 294     }
 295     LINK(left, rightchild, a->root->leftchild);
 296     LINK(right, leftchild, a->root->rightchild);
 297     LINK(a->root, leftchild, tmp.rightchild);
 298     LINK(a->root, rightchild, tmp.leftchild);
 299     a->root->parent = 0;
 300 }
 301
 302 #endif
 303
 304 static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s)
 305 {
 306 #ifdef SPLAY
 307     //fprintf(stderr, "insert [%d] after [%d]\n", SEGNR(s), SEGNR(left));
 308     //actlist_splay_dump(a);
 309     //actlist_dump(a, s->a.y);
 310 #endif
 311
 312     s->left = left;
 313     if(left) {
 314         s->right = left->right;
 315     } else {
 316         s->right = a->list;
 317         a->list = s;
 318     }
 319     if(s->left)
 320         s->left->right = s;
 321     if(s->right)
 322         s->right->left = s;
 323
 324 #ifdef SPLAY
 325     // we insert nodes not trees
 326     assert(!s->leftchild);
 327     assert(!s->rightchild);
 328
 329     if(a->root) {
 330         move_to_root(a, left);
 331
 332         if(left) {
 333             LINK(s,leftchild,a->root);
 334             // steal right child from (previous) root
 335             LINK(s,rightchild,a->root->rightchild);
 336             a->root->rightchild = 0;
 337         } else {
 338             LINK(s,rightchild,a->root);
 339         }
 340
 341         /*if(cmp(a->root, s->a, s->b) < 0) {
 342             LINK(s,rightchild,a->root);
 343             // steal left child from (previous) root
 344             LINK(s,leftchild,a->root->leftchild);
 345             a->root->leftchild = 0;
 346         } else {
 347             LINK(s,leftchild,a->root);
 348             // steal right child from (previous) root
 349             LINK(s,rightchild,a->root->rightchild);
 350             a->root->rightchild = 0;
 351         }*/
 352     }
 353     a->root = s;
 354     a->root->parent = 0;
 355
 356     assert(actlist_splay_verify(a));
 357 #endif
 358
 359     a->size++;
 360 }
 361
 362 void actlist_delete(actlist_t*a, segment_t*s)
 363 {
 364 #ifdef SPLAY
 365     assert(actlist_splay_verify(a));
 366     move_to_root(a, s);
 367     assert(actlist_splay_verify(a));
 368 #endif
 369     if(s->left) {
 370         s->left->right = s->right;
 371     } else {
 372         a->list = s->right;
 373     }
 374     if(s->right) {
 375         s->right->left = s->left;
 376     }
 377     s->left = s->right = 0;
 378     a->size--;
 379 #ifdef SPLAY
 380     assert(a->root == s);
 381     // delete root node
 382     if(!a->root->leftchild) {
 383         a->root = a->root->rightchild;
 384     } else if(!a->root->rightchild) {
 385         a->root = a->root->leftchild;
 386     } else {
 387         if(lrand48()&1) {
 388             // free up root->left->right
 389             segment_t*t = a->root->leftchild;
 390             while(t->rightchild) {
 391                 segment_t*r = t->rightchild;
 392                 segment_t*l = r->leftchild;
 393                 LINK(r, leftchild, t);
 394                 LINK(t, rightchild, l);
 395                 t = r;
 396             }
 397             LINK(a->root,leftchild,t);
 398             assert(!a->root->leftchild->rightchild);
 399             LINK(a->root->leftchild,rightchild,a->root->rightchild);
 400             a->root = a->root->leftchild;
 401         } else {
 402             // free up root->right->left
 403             segment_t*t = a->root->rightchild;
 404             while(t->leftchild) {
 405                 segment_t*l = t->leftchild;
 406                 segment_t*r = l->rightchild;
 407                 LINK(l, rightchild, t);
 408                 LINK(t, leftchild, r);
 409                 t = l;
 410             }
 411             LINK(a->root,rightchild,t);
 412             assert(!a->root->rightchild->leftchild);
 413             LINK(a->root->rightchild,leftchild,a->root->leftchild);
 414             a->root = a->root->rightchild;
 415         }
 416     }
 417     if(a->root)
 418         a->root->parent = 0;
 419     s->leftchild = s->rightchild = s->parent = 0;
 420
 421     assert(actlist_splay_verify(a));
 422 #endif
 423 }
 424 int actlist_size(actlist_t*a)
 425 {
 426     return a->size;
 427 }
 428
 429 segment_t* actlist_leftmost(actlist_t*a)
 430 {
 431     return a->list;
 432 }
 433
 434 segment_t* actlist_rightmost(actlist_t*a)
 435 {
 436     /* this is only used in checks, so it doesn't matter that it's slow */
 437     segment_t*s = a->list;
 438     segment_t*last = 0;
 439     while(s) {
 440         last = s;
 441         s = s->right;
 442     }
 443     return last;
 444 }
 445
 446 void actlist_insert(actlist_t*a, point_t p1, point_t p2, segment_t*s)
 447 {
 448     segment_t*left = actlist_find(a, p1, p2);
 449     actlist_insert_after(a, left, s);
 450 }
 451
 452
 453 segment_t* actlist_left(actlist_t*a, segment_t*s)
 454 {
 455     return s->left;
 456 }
 457
 458 segment_t* actlist_right(actlist_t*a, segment_t*s)
 459 {
 460     if(s) return s->right;
 461     else  return a->list;
 462 }
 463
 464 void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
 465 {
 466 #ifdef SPLAY
 467     assert(actlist_splay_verify(a));
 468 #endif
 469 #ifdef CHECKS
 470     /* test that s1 is to the left of s2- our swap
 471        code depends on that */
 472     segment_t*s = s1;
 473     while(s && s!=s2) s = s->right;
 474     assert(s==s2);
 475 #endif
 476 /*#ifndef SPLAY
 477     actlist_delete(a, s1);
 478     actlist_insert_after(a, s2, s1);
 479 #else*/
 480     segment_t*s1l = s1->left;
 481     segment_t*s1r = s1->right;
 482     segment_t*s2l = s2->left;
 483     segment_t*s2r = s2->right;
 484     if(s1l) s1l->right = s2;
 485     else    a->list = s2;
 486     s2->left = s1l;
 487     if(s2r) s2r->left = s1;
 488     s1->right = s2r;
 489     if(s2l!=s1) s1->left = s2l;
 490     else        s1->left = s2;
 491     if(s1r!=s2) s2->right = s1r;
 492     else        s2->right = s1;
 493
 494 #ifdef SPLAY
 495     if(s2->parent==s1) {
 496         /*
 497              s1            s2
 498             /      ->     /
 499           s2            s1
 500         */
 501         segment_t*l = s2->leftchild;
 502         segment_t*r = s2->rightchild;
 503         assert(s1->rightchild == s2); // because s1 < s2
 504         segment_t*l1 = s1->leftchild;
 505         segment_t*p = s1->parent;
 506         s1->parent = s2;
 507         s2->parent = p;
 508         if(p) {
 509             if(p->leftchild == s1) p->leftchild=s2;
 510             else {assert(p->rightchild == s1);p->rightchild=s2;}
 511         } else {
 512             a->root = s2;
 513         }
 514         s2->leftchild = l1;
 515         s2->rightchild = s1;
 516         s1->leftchild = l;
 517         s1->rightchild = r;
 518     } else if(s1->parent==s2) {
 519         /*
 520              s2            s1
 521             /      ->     /
 522           s1            s2
 523         */
 524         segment_t*l = s1->leftchild;
 525         segment_t*r = s1->rightchild;
 526         segment_t*r2 = s2->rightchild;
 527         assert(s2->leftchild == s1); // because s1 < s2
 528         segment_t*p = s2->parent;
 529         s2->parent = s1;
 530         s1->parent = p;
 531         if(p) {
 532             if(p->leftchild == s2) p->leftchild=s1;
 533             else {assert(p->rightchild == s2);p->rightchild=s1;}
 534         } else {
 535             a->root = s1;
 536         }
 537         s1->leftchild = s2;
 538         s1->rightchild = r2;
 539         s2->leftchild = l;
 540         s2->rightchild = r;
 541     } else {
 542         segment_t*s1p = s1->parent;
 543         segment_t*s1l = s1->leftchild;
 544         segment_t*s1r = s1->rightchild;
 545         segment_t*s2p = s2->parent;
 546         segment_t*s2l = s2->leftchild;
 547         segment_t*s2r = s2->rightchild;
 548         s2->parent = s1p;
 549         s2->leftchild = s1l;
 550         s2->rightchild = s1r;
 551         s1->parent = s2p;
 552         s1->leftchild = s2l;
 553         s1->rightchild = s2r;
 554         assert(s1p || s2p);
 555         if(s1p) {
 556             if(s1p->leftchild == s1) s1p->leftchild=s2;
 557             else {assert(s1p->rightchild == s1);s1p->rightchild=s2;}
 558         } else {
 559             a->root = s2;
 560         }
 561         if(s2p) {
 562             if(s2p->leftchild == s2) s2p->leftchild=s1;
 563             else {assert(s2p->rightchild == s2);s2p->rightchild=s1;}
 564         } else {
 565             a->root = s1;
 566         }
 567     }
 568     if(s1->leftchild) s1->leftchild->parent = s1;
 569     if(s2->leftchild) s2->leftchild->parent = s2;
 570     if(s1->rightchild) s1->rightchild->parent = s1;
 571     if(s2->rightchild) s2->rightchild->parent = s2;
 572     if(!actlist_splay_verify(a)) {
 573         actlist_splay_dump(a);
 574         actlist_dump(a, s1->a.y);
 575     }
 576 #endif
 577
 578 //#endif
 579 }