lib/gfxpoly/poly.c

   1 #include <stdlib.h>
   2 #include <assert.h>
   3 #include <memory.h>
   4 #include <math.h>
   5 #include "../mem.h"
   6 #include "../q.h"
   7 #include "poly.h"
   8 #include "active.h"
   9 #include "xrow.h"
  10
  11 //#define DEBUG
  12 //#undef assert
  13 //#define assert(x)
  14
  15 char point_equals(const void*o1, const void*o2)
  16 {
  17     const point_t*p1 = o1;
  18     const point_t*p2 = o2;
  19     return p1->x == p2->x && p1->y == p2->y;
  20 }
  21 unsigned int point_hash(const void*o)
  22 {
  23     const point_t*p = o;
  24     return p->x^p->y;
  25 }
  26 void* point_dup(const void*o)
  27 {
  28     const point_t*p = o;
  29     point_t*n = malloc(sizeof(point_t));
  30     n->x = p->x;
  31     n->y = p->y;
  32     return n;
  33 }
  34 void point_free(void*o)
  35 {
  36     point_t*p = o;
  37     p->x = 0;
  38     p->y = 0;
  39     free(p);
  40 }
  41 type_t point_type = {
  42     equals: point_equals,
  43     hash: point_hash,
  44     dup: point_dup,
  45     free: point_free,
  46 };
  47
  48 typedef struct _status {
  49     int y;
  50     actlist_t*actlist;
  51     heap_t*queue;
  52     edge_t*output;
  53     xrow_t*xrow;
  54 #ifdef DEBUG
  55     dict_t*seen_crossings; //list of crossing we saw so far
  56     dict_t*intersecting_segs; //list of segments intersecting in this scanline
  57     dict_t*segs_with_point; //lists of segments that received a point in this scanline
  58 #endif
  59 } status_t;
  60
  61 int compare_events(const void*_a,const void*_b)
  62 {
  63     event_t* a = (event_t*)_a;
  64     event_t* b = (event_t*)_b;
  65     if(a->p.y < b->p.y) {
  66         return 1;
  67     } else if(a->p.y > b->p.y) {
  68         return -1;
  69     /* we should schedule start events after end/intersect.
  70        The order of end/intersect doesn't actually matter, however,
  71        so this might be doing too much */
  72     } else if(a->type < b->type) {
  73         return 1;
  74     } else if(a->type > b->type) {
  75         return -1;
  76     } else if(a->p.x < b->p.x) {
  77         return 1;
  78     } else if(a->p.x > b->p.x) {
  79         return -1;
  80     } else
  81         return 0;
  82 }
  83
  84 gfxpoly_t* gfxpoly_new()
  85 {
  86     return 0;
  87 }
  88 void gfxpoly_destroy(gfxpoly_t*poly)
  89 {
  90     edge_t* s = poly;
  91     while(s) {
  92         edge_t*next  = s->next;
  93         free(s);
  94         s = next;
  95     }
  96 }
  97
  98 void gfxpoly_dump(gfxpoly_t*poly)
  99 {
 100     edge_t* s = (edge_t*)poly;
 101     while(s) {
 102         fprintf(stderr, "(%d,%d) -> (%d,%d)\n", s->a.x, s->a.y, s->b.x, s->b.y);
 103         s = s->next;
 104     }
 105 }
 106
 107 inline static event_t event_new()
 108 {
 109     event_t e;
 110     memset(&e, 0, sizeof(e));
 111     return e;
 112 }
 113
 114 void event_dump(event_t*e)
 115 {
 116     if(e->type == EVENT_HORIZONTAL) {
 117         fprintf(stderr, "Horizontal [%d] (%d,%d) -> (%d,%d)\n", e->s1->nr, e->s1->a.x, e->s1->a.y, e->s1->b.x, e->s1->b.y);
 118     } else if(e->type == EVENT_START) {
 119         fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
 120     } else if(e->type == EVENT_END) {
 121         fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
 122     } else if(e->type == EVENT_CROSS) {
 123         fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
 124     } else {
 125         assert(0);
 126     }
 127 }
 128
 129 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
 130 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
 131
 132 void segment_init(segment_t*s, int x1, int y1, int x2, int y2)
 133 {
 134     if(y1<y2) {
 135         s->dir = DIR_DOWN;
 136     } else if(y1>y2) {
 137         int x = x1;x1=x2;x2=x;
 138         int y = y1;y1=y2;y2=y;
 139         s->dir = DIR_UP;
 140     } else {
 141         s->dir = DIR_HORIZONTAL;
 142         if(x1>x2) {
 143             int x = x1;x1=x2;x2=x;
 144             int y = y1;y1=y2;y2=y;
 145         }
 146     }
 147     s->a.x = x1;
 148     s->a.y = y1;
 149     s->b.x = x2;
 150     s->b.y = y2;
 151     s->k = (double)x1*y2-(double)x2*y1;
 152     s->left = s->right = 0;
 153     s->delta.x = x2-x1;
 154     s->delta.y = y2-y1;
 155     s->pos = s->a;
 156     s->tmp = -1;
 157     s->new_point.y = y1-1;
 158 #define XDEBUG
 159 #ifdef XDEBUG
 160     static int segment_count=0;
 161     s->nr = segment_count++;
 162 #endif
 163
 164     assert(LINE_EQ(s->a, s) == 0);
 165     assert(LINE_EQ(s->b, s) == 0);
 166
 167     /* check that all signs are in order:
 168        a        a
 169        |\      /|
 170        | \    / |
 171      minx-b  b--maxx
 172      < 0        > 0
 173     */
 174     point_t p = s->b;
 175     p.x = min32(s->a.x, s->b.x);
 176     assert(LINE_EQ(p, s) <= 0);
 177     p.x = max32(s->a.x, s->b.x);
 178     assert(LINE_EQ(p, s) >= 0);
 179
 180     dict_init2(&s->scheduled_crossings, &ptr_type, 0);
 181 }
 182
 183 segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2)
 184 {
 185     segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
 186     segment_init(s, x1, y1, x2, y2);
 187     return s;
 188 }
 189 void segment_destroy(segment_t*s)
 190 {
 191     dict_clear(&s->scheduled_crossings);
 192     free(s);
 193 }
 194
 195 void gfxpoly_enqueue(edge_t*list, heap_t*queue)
 196 {
 197     edge_t*l;
 198     for(l=list;l;l=l->next) {
 199         if(l->a.x == l->b.x &&
 200            l->a.y == l->b.y) {
 201             fprintf(stderr, "Warning: intersector input contains zero-length segments\n");
 202             continue;
 203         }
 204         segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y);
 205 #ifdef DEBUG
 206         fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s\n",
 207                 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
 208                 s->dir==DIR_UP?"up":"down");
 209 #endif
 210         event_t e = event_new();
 211         e.type = s->dir==DIR_HORIZONTAL?EVENT_HORIZONTAL:EVENT_START;
 212         e.p = s->a;
 213         e.s1 = s;
 214         e.s2 = 0;
 215         heap_put(queue, &e);
 216     }
 217 }
 218
 219 void schedule_endpoint(status_t*status, segment_t*s)
 220 {
 221     // schedule end point of segment
 222     assert(s->b.y > status->y);
 223     event_t e;
 224     e.type = EVENT_END;
 225     e.p = s->b;
 226     e.s1 = s;
 227     e.s2 = 0;
 228     heap_put(status->queue, &e);
 229 }
 230
 231 void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
 232 {
 233     /* the code that's required (and the checks you can perform) before
 234        it can be said with 100% certainty that we indeed have a valid crossing
 235        amazes me every time. -mk */
 236     assert(s1!=s2);
 237
 238     /* we probably could precompute these */
 239     int32_t minx1 = min32(s1->a.x,s1->b.x);
 240     int32_t miny1 = min32(s1->a.y,s1->b.y);
 241     int32_t maxx1 = max32(s1->a.x,s1->b.x);
 242     int32_t maxy1 = max32(s1->a.y,s1->b.y);
 243     int32_t minx2 = min32(s2->a.x,s2->b.x);
 244     int32_t miny2 = min32(s2->a.y,s2->b.y);
 245     int32_t maxx2 = max32(s2->a.x,s2->b.x);
 246     int32_t maxy2 = max32(s2->a.y,s2->b.y);
 247
 248     /* both segments are active, so this can't happen */
 249     assert(!(maxy1 <= miny2 || maxy2 <= miny1));
 250
 251     /* TODO: optimize this. remove y, precompute the two x values */
 252     if(maxx1 <= minx2 || maxx2 <= minx1 ||
 253        maxy1 <= miny2 || maxy2 <= miny1) {
 254         /* bounding boxes don't intersect */
 255         return;
 256     }
 257
 258     if(dict_contains(&s1->scheduled_crossings, s2)) {
 259         /* FIXME: this whole segment hashing thing is really slow */
 260         //fprintf(stderr, "Encountered crossing between [%d] and [%d] twice\n", s1->nr, s2->nr);
 261
 262         // we already know about this one
 263         return;
 264     }
 265
 266     double adx = s1->delta.x;
 267     double ady = s1->delta.y;
 268     double bdx = s2->delta.x;
 269     double bdy = s2->delta.y;
 270     double det = adx*bdy - ady*bdx;
 271     if(!det) {
 272         if(s1->k == s2->k) {
 273             // lines are exactly on top of each other (ignored)
 274 #ifdef DEBUG
 275             fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
 276 #endif
 277             return;
 278         } else {
 279             /* lines are parallel */
 280             return;
 281         }
 282     }
 283     double asign2 = LINE_EQ(s1->a, s2);
 284     double bsign2 = LINE_EQ(s1->b, s2);
 285     if(asign2<0 && bsign2<0) {
 286         // segment1 is completely to the left of segment2
 287         return;
 288     }
 289     if(asign2>0 && bsign2>0)  {
 290         // segment2 is completely to the left of segment1
 291         return;
 292     }
 293     if(asign2==0) {
 294         // segment1 touches segment2 in a single point (ignored)
 295 #ifdef DEBUG
 296         fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
 297 #endif
 298         return;
 299     }
 300     if(bsign2==0) {
 301         // segment1 touches segment2 in a single point (ignored)
 302 #ifdef DEBUG
 303         fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
 304 #endif
 305         return;
 306     }
 307     double asign1 = LINE_EQ(s2->a, s1);
 308     double bsign1 = LINE_EQ(s2->b, s1);
 309     if(asign1<0 && bsign1<0) {
 310         // segment1 is completely to the left of segment2
 311         return;
 312     }
 313     if(asign1>0 && bsign1>0)  {
 314         // segment2 is completely to the left of segment1
 315         return;
 316     }
 317     if(asign1==0) {
 318         // segment2 touches segment1 in a single point (ignored)
 319 #ifdef DEBUG
 320         fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
 321 #endif
 322         return;
 323     }
 324     if(asign2==0) {
 325         // segment2 touches segment1 in a single point (ignored)
 326 #ifdef DEBUG
 327         fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
 328 #endif
 329         return;
 330     }
 331
 332     double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
 333     double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
 334
 335     point_t p;
 336     p.x = (int32_t)ceil((-la*bdx +lb*adx) / det);
 337     p.y = (int32_t)ceil((+lb*ady -la*bdy) / det);
 338
 339     assert(p.y >= status->y);
 340 #ifdef DEBUG
 341     point_t pair;
 342     pair.x = s1->nr;
 343     pair.y = s2->nr;
 344     assert(!dict_contains(status->seen_crossings, &pair));
 345     dict_put(status->seen_crossings, &pair, 0);
 346     fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
 347 #endif
 348
 349     /* we insert into each other's intersection history because these segments might switch
 350        places and we still want to look them up quickly after they did */
 351     dict_put(&s1->scheduled_crossings, s2, 0);
 352     dict_put(&s2->scheduled_crossings, s1, 0);
 353
 354     event_t e = event_new();
 355     e.type = EVENT_CROSS;
 356     e.p = p;
 357     e.s1 = s1;
 358     e.s2 = s2;
 359     heap_put(status->queue, &e);
 360     return;
 361 }
 362
 363 void exchange_two(status_t*status, event_t*e)
 364 {
 365     //exchange two segments in list
 366     segment_t*s1 = e->s1;
 367     segment_t*s2 = e->s2;
 368 #ifdef DEBUG
 369     if(!dict_contains(status->intersecting_segs, s1))
 370         dict_put(status->intersecting_segs, s1, 0);
 371     if(!dict_contains(status->intersecting_segs, s2))
 372         dict_put(status->intersecting_segs, s2, 0);
 373 #endif
 374     segment_t*left = actlist_left(status->actlist, s2);
 375     segment_t*right = actlist_right(status->actlist, s1);
 376     assert(left == s1);
 377     assert(right == s2);
 378     actlist_swap(status->actlist, s1, s2);
 379     assert(actlist_right(status->actlist, s2) == s1);
 380     assert(actlist_left(status->actlist, s1) == s2);
 381     left = actlist_left(status->actlist, s2);
 382     right = actlist_right(status->actlist, s1);
 383     if(left)
 384         schedule_crossing(status, left, s2);
 385     if(right)
 386         schedule_crossing(status, s1, right);
 387 }
 388
 389 typedef struct _box {
 390     point_t left1, left2, right1, right2;
 391 } box_t;
 392 static inline box_t box_new(int x, int y)
 393 {
 394     box_t box;
 395     box.right1.x = box.right2.x = x;
 396     box.left1.x = box.left2.x = x-1;
 397     box.left1.y = box.right1.y = y-1;
 398     box.left2.y = box.right2.y = y;
 399     return box;
 400 }
 401
 402 void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
 403 {
 404     edge_t*e = malloc(sizeof(edge_t));
 405     e->a = s->pos;
 406     e->b = p;
 407     assert(e->a.y != e->b.y);
 408     e->next = status->output;
 409     status->output = e;
 410 }
 411
 412 void mark_point_in_segment(status_t*status, segment_t*s, point_t p)
 413 {
 414 #ifdef DEBUG
 415     if(s->pos.x == p.x && s->pos.y == p.y) {
 416         fprintf(stderr, "Error: tried to add (%d,%d) to segment [%d] twice\n", p.x, p.y, s->nr);
 417     }
 418 #endif
 419     assert(s->pos.x != p.x || s->pos.y != p.y);
 420 #ifdef DEBUG
 421     fprintf(stderr, "[%d] gets extra point (%d,%d)\n", s->nr, p.x, p.y);
 422     if(!dict_contains(status->segs_with_point, s))
 423         dict_put(status->segs_with_point, s, 0);
 424 #endif
 425     if(s->new_point.y != p.y) {
 426         s->new_point = p;
 427     }
 428     s->new_pos = p;
 429 }
 430
 431 /* possible optimizations:
 432    1.) keep two different active lists around, one for negative and one for
 433        positive slopes
 434    2.) delay starting events until after this function (tricky, because we *do*
 435        need the start coordinates)
 436 */
 437 /*
 438    SLOPE_POSITIVE:
 439       \+     \ +
 440 ------ I      \I
 441       -I\----  I
 442        I \   --I\---
 443        I  \    I \  -------
 444        +   \   +  \
 445 */
 446 static void mark_points_in_positively_sloped_segments(status_t*status, int32_t y)
 447 {
 448     int t;
 449     for(t=0;t<status->xrow->num;t++) {
 450         box_t box = box_new(status->xrow->x[t], y);
 451         segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
 452         seg = actlist_right(status->actlist, seg);
 453         while(seg) {
 454             if(seg->a.y == y) {
 455                 // this segment just started, ignore it
 456             } else if(seg->delta.x < 0) {
 457                 // ignore segment w/ negative slope
 458             } else {
 459                 double d1 = LINE_EQ(box.right1, seg);
 460                 double d2 = LINE_EQ(box.right2, seg);
 461                 if(d1>=0 || d2>=0) {
 462                     mark_point_in_segment(status, seg, box.right2);
 463                 } else {
 464                     break;
 465                 }
 466             }
 467             seg = actlist_right(status->actlist, seg);
 468         }
 469     }
 470 }
 471 /* SLOPE_NEGATIVE:
 472    |   +   /|  +  /    /
 473    |   I  / |  I /    /
 474    |   I /  |  I/    /
 475    |   I/   |  I    /
 476    |   I    | /I   /
 477    |  /+    |/ +  /
 478 */
 479 static void mark_points_in_negatively_sloped_segments(status_t*status, int32_t y)
 480 {
 481     int t;
 482     for(t=status->xrow->num-1;t>=0;t--) {
 483         box_t box = box_new(status->xrow->x[t], y);
 484         segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
 485         while(seg) {
 486             if(seg->a.y == y) {
 487                 // this segment just started, ignore it
 488             } else if(seg->delta.x >= 0) {
 489                 // ignore segment w/ positive slope
 490             } else {
 491                 double d1 = LINE_EQ(box.left1, seg);
 492                 double d2 = LINE_EQ(box.left2, seg);
 493                 if(d1<0 || d2<0) {
 494                     mark_point_in_segment(status, seg, box.right2);
 495                 } else {
 496                     break;
 497                 }
 498             }
 499             seg = actlist_left(status->actlist, seg);
 500         }
 501     }
 502 }
 503
 504 static void add_points(status_t*status)
 505 {
 506     /* TODO: we could use some clever second linked list structure so that we
 507              only need to process points which we know we marked */
 508     int t;
 509     segment_t*s = actlist_leftmost(status->actlist);
 510     while(s) {
 511         if(s->new_point.y == status->y) {
 512             insert_point_into_segment(status, s, s->new_point);
 513             s->pos = s->new_pos;
 514         }
 515         s = actlist_right(status->actlist, s);
 516     }
 517 }
 518
 519 void intersect_with_horizontal(status_t*status, segment_t*h)
 520 {
 521     segment_t* left = actlist_find(status->actlist, h->a, h->a);
 522     segment_t* right = actlist_find(status->actlist, h->b, h->b);
 523
 524     segment_t* s = right;
 525
 526     while(s!=left) {
 527         assert(s);
 528         /*
 529            x1 + ((x2-x1)*(y-y1)) / dy =
 530            (x1*(y2-y) + x2*(y-y1)) / dy
 531         */
 532         point_t p;
 533         p.y = status->y;
 534         p.x = XPOS(s, p.y);
 535 #ifdef DEBUG
 536         fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
 537                 s->a.x, s->a.y,
 538                 s->b.x, s->b.y,
 539                 p.x, p.y
 540                 );
 541 #endif
 542         assert(p.x >= h->a.x);
 543         assert(p.x <= h->b.x);
 544         assert(s->delta.x > 0 && p.x >= s->a.x || s->delta.x <= 0 && p.x <= s->a.x);
 545         assert(s->delta.x > 0 && p.x <= s->b.x || s->delta.x <= 0 && p.x >= s->b.x);
 546         xrow_add(status->xrow, p.x);
 547
 548         s = actlist_left(status->actlist, s);
 549     }
 550     xrow_add(status->xrow, h->a.x);
 551 }
 552
 553 void event_apply(status_t*status, event_t*e)
 554 {
 555     switch(e->type) {
 556         case EVENT_HORIZONTAL: {
 557 #ifdef DEBUG
 558             event_dump(e);
 559 #endif
 560             intersect_with_horizontal(status, e->s1);
 561             break;
 562         }
 563         case EVENT_END: {
 564             //delete segment from list
 565             segment_t*s = e->s1;
 566 #ifdef DEBUG
 567             event_dump(e);
 568             dict_del(status->intersecting_segs, s);
 569             dict_del(status->segs_with_point, s);
 570             assert(!dict_contains(status->intersecting_segs, s));
 571             assert(!dict_contains(status->segs_with_point, s));
 572 #endif
 573             insert_point_into_segment(status, s, s->b);
 574             segment_t*left = actlist_left(status->actlist, s);
 575             segment_t*right = actlist_right(status->actlist, s);
 576             actlist_delete(status->actlist, s);
 577             if(left && right)
 578                 schedule_crossing(status, left, right);
 579             segment_destroy(s);e->s1=0;
 580             break;
 581         }
 582         case EVENT_START: {
 583             //insert segment into list
 584 #ifdef DEBUG
 585             event_dump(e);
 586 #endif
 587             segment_t*s = e->s1;
 588             actlist_insert(status->actlist, e->p, s);
 589             segment_t*left = actlist_left(status->actlist, s);
 590             segment_t*right = actlist_right(status->actlist, s);
 591             if(left)
 592                 schedule_crossing(status, left, s);
 593             if(right)
 594                 schedule_crossing(status, s, right);
 595
 596             schedule_endpoint(status, e->s1);
 597             break;
 598         }
 599         case EVENT_CROSS: {
 600             // exchange two (or more) segments
 601             if(actlist_right(status->actlist, e->s1) == e->s2 &&
 602                actlist_left(status->actlist, e->s2) == e->s1) {
 603                 exchange_two(status, e);
 604             } else {
 605                 /* ignore this crossing for now (there are some line segments in between).
 606                    it'll get rescheduled as soon as the "obstacles" are gone */
 607                 char del1 = dict_del(&e->s1->scheduled_crossings, e->s2);
 608                 char del2 = dict_del(&e->s2->scheduled_crossings, e->s1);
 609                 assert(del1 && del2);
 610 #ifdef DEBUG
 611                 point_t pair;
 612                 pair.x = e->s1->nr;
 613                 pair.y = e->s2->nr;
 614                 assert(dict_contains(status->seen_crossings, &pair));
 615                 dict_del(status->seen_crossings, &pair);
 616 #endif
 617             }
 618         }
 619     }
 620 }
 621
 622 #ifdef DEBUG
 623 void check_status(status_t*status)
 624 {
 625     DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
 626         if((s->pos.x != s->b.x ||
 627             s->pos.y != s->b.y) &&
 628            !dict_contains(status->segs_with_point, s)) {
 629             fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
 630                     s->nr,
 631                     s->delta.x<0?"-":"+",
 632                     status->y);
 633             assert(0);
 634         }
 635     }
 636 }
 637 #endif
 638
 639 edge_t* gfxpoly_process(edge_t*poly)
 640 {
 641     heap_t* queue = heap_new(sizeof(event_t), compare_events);
 642     gfxpoly_enqueue(poly, queue);
 643     status_t status;
 644     memset(&status, 0, sizeof(status_t));
 645     status.queue = queue;
 646     status.actlist = actlist_new();
 647 #ifdef DEBUG
 648     status.seen_crossings = dict_new2(&point_type);
 649     gfxpoly_dump(poly);
 650 #endif
 651
 652     status.xrow = xrow_new();
 653
 654     event_t*e = heap_chopmax(queue);
 655     while(e) {
 656         status.y = e->p.y;
 657 #ifdef DEBUG
 658         status.intersecting_segs = dict_new2(&ptr_type);
 659         status.segs_with_point = dict_new2(&ptr_type);
 660         fprintf(stderr, "----------------------------------- %d\n", status.y);
 661         actlist_verify_and_dump(status.actlist, status.y-1);
 662 #endif
 663         xrow_reset(status.xrow);
 664         do {
 665             if(e->type != EVENT_HORIZONTAL) {
 666                 xrow_add(status.xrow, e->p.x);
 667             }
 668             event_apply(&status, e);
 669             free(e);
 670             e = heap_chopmax(queue);
 671         } while(e && status.y == e->p.y);
 672
 673         xrow_sort(status.xrow);
 674         mark_points_in_positively_sloped_segments(&status, status.y);
 675         mark_points_in_negatively_sloped_segments(&status, status.y);
 676         add_points(&status);
 677 #ifdef DEBUG
 678         check_status(&status);
 679         dict_destroy(status.intersecting_segs);
 680         dict_destroy(status.segs_with_point);
 681 #endif
 682     }
 683 #ifdef DEBUG
 684     dict_destroy(status.seen_crossings);
 685 #endif
 686     actlist_destroy(status.actlist);
 687     heap_destroy(queue);
 688     xrow_destroy(status.xrow);
 689
 690     return status.output;
 691 }