lib/gfxpoly/active.c

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