From: Matthias Kramm <kramm@quiss.org>
Date: Wed, 22 Apr 2009 16:35:08 +0000 (+0200)
Subject: first version of new polygon intersector
X-Git-Tag: polyok~21
X-Git-Url: http://git.asbjorn.biz/?p=swftools.git;a=commitdiff_plain;h=66a03382aab040571f94b0861719753bda3ff8f1

first version of new polygon intersector
---

diff --git a/.gitignore b/.gitignore
index 1bed48d..fe4f5e0 100644
--- a/.gitignore
+++ b/.gitignore
@@ -29,7 +29,7 @@ t
 r
 cming
 gen
-Makefile
+./Makefile
 Makefile.common
 Makefile.new
 Makefile.depend
diff --git a/lib/.gitignore b/lib/.gitignore
index f3c7a7c..1785310 100644
--- a/lib/.gitignore
+++ b/lib/.gitignore
@@ -1 +1 @@
-Makefile
+lib/Makefile
diff --git a/lib/gfxpoly.c b/lib/gfxpoly.c
index a408618..a08899d 100644
--- a/lib/gfxpoly.c
+++ b/lib/gfxpoly.c
@@ -449,7 +449,7 @@ static ArtVpath* gfxline_to_ArtVpath(gfxline_t*line, char fill)
     }
 
     /* Find adjacent identical points. If an ajdacent pair of identical
-       points is found, the second is removed.
+       points is found, the second one is removed.
        So moveto x,y lineto x,y becomes moveto x,y
           lineto x,y lineto x,y becomes lineto x,y
           lineto x,y moveto x,y becomes lineto x,y
diff --git a/lib/gfxpoly/Makefile b/lib/gfxpoly/Makefile
new file mode 100644
index 0000000..04d227b
--- /dev/null
+++ b/lib/gfxpoly/Makefile
@@ -0,0 +1,25 @@
+all: testheap test
+
+../libbase.a: ../q.c ../q.h ../mem.c ../mem.h
+	cd ..; make libbase.a
+
+../libgfx.a: ../gfxtools.h ../gfxtools.c ../gfxpoly.h ../gfxpoly.c
+	cd ..; make libgfx.a
+
+testheap: ../libbase.a testheap.c
+	gcc -g testheap.c ../libbase.a -o testheap -lm -lz -ljpeg
+
+active.o: active.c active.h poly.h
+	gcc -g -c active.c -o active.o
+
+convert.o: convert.c convert.h poly.h
+	gcc -g -c convert.c -o convert.o
+
+poly.o: poly.c poly.h active.h ../q.h
+	gcc -g -c poly.c -o poly.o
+
+xrow.o: xrow.c xrow.h ../q.h ../mem.h
+	gcc -g -c xrow.c -o xrow.o
+
+test: ../libbase.a ../libgfx.a test.c poly.o convert.o active.o xrow.o poly.h convert.h
+	gcc -g test.c poly.o convert.o active.o xrow.o ../libbase.a ../libgfx.a -o test -lm -lz -ljpeg -lfreetype
diff --git a/lib/gfxpoly/active.c b/lib/gfxpoly/active.c
new file mode 100644
index 0000000..d726a01
--- /dev/null
+++ b/lib/gfxpoly/active.c
@@ -0,0 +1,141 @@
+#include <assert.h>
+#include "../q.h"
+#include "active.h"
+
+actlist_t* actlist_new()
+{
+    NEW(actlist_t, a);
+    return a;
+}
+
+void actlist_verify_and_dump(actlist_t*a, int32_t y)
+{
+    segment_t*s = a->list;
+    assert(!s || !s->left);
+    double lastx;
+    while(s) {
+        if(y) {
+            double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x;
+            if(s!=a->list) {
+                if(lastx>x) printf("?%f<->%f? ", lastx, x);
+            }
+            lastx = x;
+        }
+        assert(!s->left || s->left->right == s);
+        assert(!s->right || s->right->left == s);
+        printf("[%d]", s->nr);
+        s = s->right;
+        if(s) printf(" ");
+        else printf("\n");
+    }
+}
+
+segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
+{
+    /* this runs in O(n) right now, and should be optimized using a splay
+       tree to run in ammortized O(log(n)) */
+    segment_t*last=0, *s = a->list;
+    if(!s) return last;
+    while(s) {
+        double d = LINE_EQ(p1, s);
+        if(d==0) {
+            d = LINE_EQ(p2, s);
+            if(d==0) {
+                /* We default to always inserting the new segment to the right of the old segment.
+                   We do this so that we don't place new segments into the middle of already
+                   overlapping lines which may have intersections scheduled.
+                 */
+                //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);
+            }
+        }
+        if(d<0)
+            break;
+        last = s;
+        s = s->right;
+    }
+    return last;
+}
+
+static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s)
+{
+    s->left = left;
+    if(left) {
+        s->right = left->right;
+    } else {
+        s->right = a->list;
+        a->list = s;
+    }
+    if(s->left) 
+        s->left->right = s;
+    if(s->right) 
+        s->right->left = s;
+}
+
+void actlist_insert(actlist_t*a, point_t p, segment_t*s)
+{
+    segment_t*left = actlist_find(a, p, s->b);
+    actlist_insert_after(a, left, s);
+}
+
+void actlist_delete(actlist_t*a, segment_t*s)
+{
+    if(s->left) {
+        s->left->right = s->right;
+    } else {
+        a->list = s->right;
+    }
+    if(s->right) {
+        s->right->left = s->left;
+    }
+    s->left = s->right = 0;
+}
+
+segment_t* actlist_leftmost(actlist_t*a)
+{
+    return a->list;
+}
+
+segment_t* actlist_left(actlist_t*a, segment_t*s)
+{
+    return s->left;
+}
+
+segment_t* actlist_right(actlist_t*a, segment_t*s)
+{
+    return s->right;
+}
+
+void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
+{
+    actlist_delete(a, s1);
+    actlist_insert_after(a, s2, s1);
+}
+
+void actlist_invert_fromto(actlist_t*a, segment_t*s1, segment_t*s2)
+{
+    segment_t*left = s1->left;
+    segment_t*right = s2->right;
+    segment_t*s = s1;
+    assert(s!=s2);
+    while(1) {
+        assert(s);
+        segment_t*l = s->left;
+        segment_t*r = s->right;
+        s->left = r;
+        s->right = l;
+        if(s==s2)
+            break;
+        s = r;
+    }
+    s2->left = left;
+    s1->right = right;
+    if(left) {
+        left->right = s2;
+    } else {
+        assert(a->list == s1);
+        a->list = s2; 
+    }
+    if(right) {
+        right->left = s1;
+    }
+}
diff --git a/lib/gfxpoly/active.h b/lib/gfxpoly/active.h
new file mode 100644
index 0000000..f257f96
--- /dev/null
+++ b/lib/gfxpoly/active.h
@@ -0,0 +1,24 @@
+#ifndef __active_h__
+#define __active_h__
+
+#include "poly.h"
+#include "splay.h"
+
+typedef struct _actlist
+{
+    //SPLAY_HEAD(root, actnode_t);
+    segment_t*list;
+} actlist_t;
+
+actlist_t* actlist_new();
+void actlist_verify_and_dump(actlist_t*a, int32_t y);
+segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2);  // finds segment immediately to the left of p1 (breaking ties w/ p2)
+void actlist_insert(actlist_t*a, point_t p, segment_t*s);
+void actlist_delete(actlist_t*a, segment_t*s);
+void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2);
+void actlist_invert_fromto(actlist_t*a, segment_t*s1, segment_t*s2);
+segment_t* actlist_left(actlist_t*a, segment_t*s);
+segment_t* actlist_leftmost(actlist_t*a);
+segment_t* actlist_right(actlist_t*a, segment_t*s);
+
+#endif
diff --git a/lib/gfxpoly/convert.c b/lib/gfxpoly/convert.c
new file mode 100644
index 0000000..10171f2
--- /dev/null
+++ b/lib/gfxpoly/convert.c
@@ -0,0 +1,56 @@
+#include <stdlib.h>
+#include <math.h>
+#include <assert.h>
+#include "../gfxdevice.h"
+#include "poly.h"
+
+static inline void gfxpoly_add_segment(segment_t**list, double _x1, double _y1, double _x2, double _y2)
+{
+    int x1 = ceil(_x1);
+    int y1 = ceil(_y1);
+    int x2 = ceil(_x2);
+    int y2 = ceil(_y2);
+    if(y1!=y2) {
+        segment_t*s = segment_new(x1, y1, x2, y2);
+        segment_insert_before(list, s);
+    }
+}
+
+gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line)
+{
+    segment_t*s = 0;
+
+    /* factor that determines into how many line fragments a spline is converted */
+    double subfraction = 2.4;//0.3
+
+    double lastx=0, lasty=0;
+    assert(!line || line[0].type == gfx_moveTo);
+    while(line) {
+        if(line->type == gfx_moveTo) {
+        } else if(line->type == gfx_lineTo) {
+            gfxpoly_add_segment(&s, lastx, lasty, line->x, line->y);
+	} else if(line->type == gfx_splineTo) {
+            int parts = (int)(sqrt(fabs(line->x-2*line->sx+lastx) + 
+                                   fabs(line->y-2*line->sy+lasty))*subfraction);
+            if(!parts) parts = 1;
+	    double stepsize = 1.0/parts;
+            int i;
+	    for(i=0;i<parts;i++) {
+		double t = (double)i*stepsize;
+		double x = line->x*t*t + 2*line->sx*t*(1-t) + x*(1-t)*(1-t);
+		double y = line->y*t*t + 2*line->sy*t*(1-t) + y*(1-t)*(1-t);
+                gfxpoly_add_segment(&s, lastx, lasty, x, y);
+                lastx = x;
+                lasty = y;
+	    }
+            gfxpoly_add_segment(&s, lastx, lasty, line->x, line->y);
+        }
+        lastx = line->x;
+        lasty = line->y;
+        line = line->next;
+    }
+
+    gfxline_free(line);
+    return s;
+}
+
diff --git a/lib/gfxpoly/convert.h b/lib/gfxpoly/convert.h
new file mode 100644
index 0000000..688f016
--- /dev/null
+++ b/lib/gfxpoly/convert.h
@@ -0,0 +1,8 @@
+#ifndef __poly_convert_h__
+#define __poly_convert_h__
+
+#include "poly.h"
+
+gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line);
+
+#endif //__poly_convert_h__
diff --git a/lib/gfxpoly/poly.c b/lib/gfxpoly/poly.c
new file mode 100644
index 0000000..9dc42b0
--- /dev/null
+++ b/lib/gfxpoly/poly.c
@@ -0,0 +1,647 @@
+#include <stdlib.h>
+#include <assert.h>
+#include <memory.h>
+#include <math.h>
+#include "../q.h"
+#include "poly.h"
+#include "active.h"
+#include "xrow.h"
+
+#define DEBUG
+
+char point_equals(const void*o1, const void*o2) 
+{
+    const point_t*p1 = o1;
+    const point_t*p2 = o2;
+    return p1->x == p2->x && p1->y == p2->y;
+}
+unsigned int point_hash(const void*o) 
+{
+    const point_t*p = o;
+    return p->x^p->y;
+}
+void* point_dup(const void*o) 
+{
+    const point_t*p = o;
+    point_t*n = malloc(sizeof(point_t));
+    n->x = p->x;
+    n->y = p->y;
+    return n;
+}
+void point_free(void*o) 
+{
+    point_t*p = o;
+    p->x = 0;
+    p->y = 0;
+    free(p);
+}
+type_t point_type = {
+    equals: point_equals,
+    hash: point_hash,
+    dup: point_dup,
+    free: point_free,
+};
+
+typedef struct _status {
+    int y;
+    actlist_t*actlist;
+    heap_t*queue;
+#ifdef DEBUG
+    dict_t*seen_crossings; //list of crossing we saw so far
+    dict_t*intersecting_segs; //list of segments intersecting in this scanline
+    dict_t*segs_with_point; //lists of segments that received a point in this scanline
+#endif
+} status_t;
+
+int compare_events(const void*_a,const void*_b)
+{
+    event_t* a = (event_t*)_a;
+    event_t* b = (event_t*)_b; 
+    if(a->p.y < b->p.y) {
+        return 1;
+    } else if(a->p.y > b->p.y) {
+        return -1;
+    } else if(a->type < b->type) {
+        return 1;
+    } else if(a->type > b->type) {
+        return -1;
+    } else if(a->p.x < b->p.x) {
+        return 1;
+    } else if(a->p.x > b->p.x) {
+        return -1;
+    } else
+        return 0;
+}
+
+gfxpoly_t* gfxpoly_new()
+{
+    return 0;
+}
+void gfxpoly_destroy(gfxpoly_t*poly)
+{
+    segment_t* s = poly;
+    while(s) {
+        segment_t*right = s->right;
+        free(s);
+        s = right;
+        if(s==poly)
+            break;
+    }
+}
+
+void gfxpoly_dump(gfxpoly_t*poly)
+{
+    segment_t* s = (segment_t*)poly;
+    while(s) {
+        printf("[%d] (%d,%d) -> (%d,%d) %s\n",
+                s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
+                s->dir==DIR_UP?"up":"down");
+        s = s->right;
+        if(s==poly)
+            break;
+    }
+}
+
+inline static event_t event_new()
+{
+    event_t e;
+    memset(&e, 0, sizeof(e));
+    return e;
+}
+
+void event_dump(event_t*e)
+{
+    if(e->type == EVENT_START) {
+        printf("event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
+    } else if(e->type == EVENT_END) {
+        printf("event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
+    } else if(e->type == EVENT_CROSS) {
+        printf("event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
+    } else assert(0);
+}
+
+static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
+static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
+
+void segment_init(segment_t*s, int x1, int y1, int x2, int y2)
+{
+    assert(y1!=y2);
+    if(y1<y2) {
+        s->dir = DIR_DOWN;
+    } else {
+        int x = x1;x1=x2;x2=x;
+        int y = y1;y1=y2;y2=y;
+        s->dir = DIR_UP;
+    }
+    s->a.x = x1;
+    s->a.y = y1;
+    s->b.x = x2;
+    s->b.y = y2;
+    s->k = (double)x1*y2-(double)x2*y1;
+    s->left = s->right = 0;
+    s->delta.x = x2-x1;
+    s->delta.y = y2-y1;
+    s->pos = s->a;
+    s->tmp = -1;
+#ifdef DEBUG
+    static int segment_count=0; //for debugging
+    s->nr = segment_count++;
+#endif
+
+    assert(LINE_EQ(s->a, s) == 0);
+    assert(LINE_EQ(s->b, s) == 0);
+    
+    /* check that all signs are in order:
+       a        a
+       |\      /|
+       | \    / |
+     minx-b  b--maxx
+     < 0        > 0
+    */
+    point_t p = s->b;
+    p.x = min32(s->a.x, s->b.x);
+    assert(LINE_EQ(p, s) <= 0);
+    p.x = max32(s->a.x, s->b.x);
+    assert(LINE_EQ(p, s) >= 0);
+
+    dict_init2(&s->scheduled_crossings, &ptr_type, 0);
+}
+
+segment_t*segment_new(int x1, int y1, int x2, int y2)
+{
+    segment_t*s = malloc(sizeof(segment_t));
+    segment_init(s, x1, y1, x2, y2);
+    return s;
+}
+
+void segment_insert_before(segment_t**list, segment_t*add)
+{
+    if(!*list) {
+        *list = add;
+        add->left = add->right = add;
+    } else {
+        add->left = (*list)->left;
+        add->right = (*list);
+        add->right->left = add;
+        add->left->right = add;
+    }
+}
+
+void segments_enqueue(segment_t*list, heap_t*queue)
+{
+    segment_t*l = list;
+    while(l) {
+        segment_t*right = l->right;
+        l->left = l->right = 0;
+        event_t e = event_new();
+        e.type = EVENT_START;
+        e.p = l->a;e.s1 = l;e.s2 = 0;
+        heap_put(queue, &e);
+        e.type = EVENT_END;
+        e.p = l->b;e.s1 = l;e.s2 = 0;
+        heap_put(queue, &e);
+        l = right;
+        if(l==list) break;
+    }
+}
+
+void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2, int miny)
+{
+    /* the code that's required (and the checks you can perform) before
+       it can be said with 100% certainty that we indeed have a valid crossing
+       amazes me every time. -mk */
+    assert(s1!=s2);
+
+    if(dict_contains(&s1->scheduled_crossings, s2)) {
+        // we already know about this one
+        return;
+    }
+
+    /* we probably could precompute these */
+    int32_t minx1 = min32(s1->a.x,s1->b.x);
+    int32_t miny1 = min32(s1->a.y,s1->b.y);
+    int32_t maxx1 = max32(s1->a.x,s1->b.x);
+    int32_t maxy1 = max32(s1->a.y,s1->b.y);
+    int32_t minx2 = min32(s2->a.x,s2->b.x);
+    int32_t miny2 = min32(s2->a.y,s2->b.y);
+    int32_t maxx2 = max32(s2->a.x,s2->b.x);
+    int32_t maxy2 = max32(s2->a.y,s2->b.y);
+    
+    if(maxx1 <= minx2 || maxx2 <= minx1 ||
+       maxy1 <= miny2 || maxy2 <= miny1) {
+        /* bounding boxes don't intersect */
+        return;
+    }
+    double adx = s1->delta.x;
+    double ady = s1->delta.y;
+    double bdx = s2->delta.x;
+    double bdy = s2->delta.y;
+    double det = adx*bdy - ady*bdx;
+    if(!det) {
+        if(s1->k == s2->k) {
+            // lines are exactly on top of each other (ignored)
+            fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
+            return;
+        } else {
+            /* lines are parallel */
+            return;
+        }
+    }
+    double asign2 = LINE_EQ(s1->a, s2);
+    double bsign2 = LINE_EQ(s1->b, s2);
+    if(asign2<0 && bsign2<0) {
+        // segment1 is completely to the left of segment2
+        return;
+    }
+    if(asign2>0 && bsign2>0)  {
+        // segment2 is completely to the left of segment1
+        return;
+    }
+    if(asign2==0) {
+        // segment1 touches segment2 in a single point (ignored)
+#ifdef DEBUG
+        fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
+#endif
+        return;
+    }
+    if(bsign2==0) {
+        // segment1 touches segment2 in a single point (ignored)
+#ifdef DEBUG
+        fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
+#endif
+        return;
+    }
+    double asign1 = LINE_EQ(s2->a, s1);
+    double bsign1 = LINE_EQ(s2->b, s1);
+    if(asign1<0 && bsign1<0) {
+        // segment1 is completely to the left of segment2
+        return;
+    }
+    if(asign1>0 && bsign1>0)  {
+        // segment2 is completely to the left of segment1
+        return;
+    }
+    if(asign1==0) {
+        // segment2 touches segment1 in a single point (ignored)
+#ifdef DEBUG
+        fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
+#endif
+        return;
+    }
+    if(asign2==0) {
+        // segment2 touches segment1 in a single point (ignored)
+#ifdef DEBUG
+        fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
+#endif
+        return;
+    }
+
+    double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
+    double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
+
+    point_t p;
+    p.x = (int32_t)ceil((-la*bdx +lb*adx) / det);
+    p.y = (int32_t)ceil((+lb*ady -la*bdy) / det);
+    /* we only schedule crossings if they are *after* the current y. That way, we don't
+       schedule the same crossing twice */
+    if(p.y >= miny) {
+#ifdef DEBUG
+        point_t pair;
+        pair.x = s1->nr;
+        pair.y = s2->nr;
+        assert(!dict_contains(status->seen_crossings, &pair));
+        dict_put(status->seen_crossings, &pair, 0);
+#endif
+        event_t e = event_new();
+        e.type = EVENT_CROSS;
+        e.p = p;
+        e.s1 = s1;
+        e.s2 = s2;
+#ifdef DEBUG
+        printf("schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, e.p.x, e.p.y);
+#endif
+        /* we insert into each other's intersection history because these segments might switch
+           places */
+        dict_put(&s1->scheduled_crossings, s2, 0);
+        dict_put(&s2->scheduled_crossings, s1, 0);
+
+        heap_put(status->queue, &e);
+    }
+    return;
+}
+
+/* routine dealing with the special case of a number of line segments intersecting in exactly one
+   point */
+void exchange_many(status_t*status, event_t*e)
+{
+    int size = 16;
+    int n = 0;
+    segment_t**segs = (segment_t**)malloc(sizeof(segment_t*)*size);
+    segs[n] = e->s1;e->s1->tmp = n;n++;
+    segs[n] = e->s2;e->s2->tmp = n;n++;
+#ifdef DEBUG
+    dict_put(status->intersecting_segs, e->s1, 0);
+    dict_put(status->intersecting_segs, e->s2, 0);
+#endif
+    while(1) {
+        event_t*ee = heap_peek(status->queue);
+        if(ee->p.x != e->p.x ||
+           ee->p.y != e->p.y ||
+           ee->type != e->type) {
+            break;
+        }
+        if(n>=size-1) {
+            size *= 2;
+            segs = realloc(segs, sizeof(segment_t*)*size);
+        }
+        ee = heap_chopmax(status->queue);
+        if(ee->s1->tmp<0) {
+            segs[n] = ee->s1;ee->s1->tmp = n;n++;
+        }
+        if(ee->s2->tmp<0) {
+            segs[n] = ee->s2;ee->s2->tmp = n;n++;
+        }
+#ifdef DEBUG
+        dict_put(status->intersecting_segs, ee->s1, 0);
+        dict_put(status->intersecting_segs, ee->s2, 0);
+#endif
+    }
+    int t;
+#ifdef DEBUG
+    printf("event: multi-intersect: ");
+    for(t=0;t<n;t++) {
+        printf("[%d] ", segs[t]->nr);
+    }
+    printf("\n");
+#endif
+    segment_t*left = 0;
+    segment_t*right = 0;
+    char warn = 0;
+    for(t=0;t<n;t++) {
+        if(!segs[t]->left || segs[t]->left->tmp<0) {
+            assert(!left);
+            left = segs[t];
+        }
+        if(!segs[t]->right || segs[t]->right->tmp<0) {
+            assert(!right);
+            right = segs[t];
+        }
+        if(segs[t]->tmp<0)
+            warn = 1;
+    }
+    if(warn)
+        fprintf(stderr, "Warning: multi-cross section contains rogue segments\n");
+
+    assert(left);
+    assert(right);
+    assert(left!=right);
+    actlist_invert_fromto(status->actlist, left, right);
+    for(t=0;t<n;t++) {
+        segs[t]->tmp = -1;
+    }
+    free(segs);
+    if(right->left)
+        schedule_crossing(status, right->left, right, status->y);
+    if(left->right)
+        schedule_crossing(status, left, left->right, status->y);
+}
+
+void exchange_two(status_t*status, event_t*e)
+{
+    //exchange two segments in list
+    segment_t*s1 = e->s1;
+    segment_t*s2 = e->s2;
+#ifdef DEBUG
+    dict_put(status->intersecting_segs, s1, 0);
+    dict_put(status->intersecting_segs, s2, 0);
+#endif
+    segment_t*left = actlist_left(status->actlist, s2);
+    segment_t*right = actlist_right(status->actlist, s1);
+    assert(left == s1);
+    assert(right == s2);
+    actlist_swap(status->actlist, s1, s2);
+    assert(actlist_right(status->actlist, s2) == s1);
+    assert(actlist_left(status->actlist, s1) == s2);
+    left = actlist_left(status->actlist, s2);
+    right = actlist_right(status->actlist, s1);
+    if(left)
+        schedule_crossing(status, left, s2, status->y);
+    if(right)
+        schedule_crossing(status, s1, right, status->y);
+}
+
+void insert_point_into_segment(segment_t*s, point_t p)
+{
+    if(s->pos.x == p.x && s->pos.y == p.y) {
+#ifdef DEBUG
+        fprintf(stderr, "Notice: tried to add (%d,%d) to segment [%d] twice\n", p.x, p.y, s->nr);
+#endif
+        return;
+    }
+#ifdef DEBUG
+    printf("[%d] gets extra point (%d,%d)\n", s->nr, p.x, p.y);
+#endif
+    s->pos = p;
+}
+
+typedef struct _box {
+    point_t left1, left2, right1, right2;
+} box_t;
+static inline box_t box_new(int x, int y)
+{
+    box_t box;
+    box.right1.x = box.right2.x = x;
+    box.left1.x = box.left2.x = x-1;
+    box.left1.y = box.right1.y = y-1;
+    box.left2.y = box.right2.y = y;
+    return box;
+}
+        
+/* possible optimizations:
+   1.) keep two different active lists around, one for negative and one for
+       positive slopes
+   2.) delay starting events until after this function (tricky, because we *do*
+       need the start coordinates)
+*/
+/*
+   SLOPE_POSITIVE:
+       +     \ +        
+------ I      \I       
+      -I\----  I      
+       I \   --I\---
+       I  \    I \  -------
+       +   \   +  \
+*/
+void add_points_to_positively_sloped_segments(status_t*status, xrow_t*xrow, int32_t y)
+{
+    int t;
+    for(t=0;t<xrow->num;t++) {
+        box_t box = box_new(xrow->x[t], y);
+        segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
+        if(seg) 
+            seg = seg->right;
+        else    
+            seg = actlist_leftmost(status->actlist);
+        while(seg) {
+            if(seg->a.y == y) {
+                // this segment just started, ignore it
+            } else if(seg->delta.x < 0) {
+                // ignore segment w/ negative slope
+            } else {
+                double d1 = LINE_EQ(box.right1, seg);
+                double d2 = LINE_EQ(box.right2, seg);
+                if(d1>=0 || d2>=0) {
+#ifdef DEBUG
+                    dict_put(status->segs_with_point, seg, 0);
+#endif
+                    insert_point_into_segment(seg, box.right2);
+                } else {
+                    break;
+                }
+            }
+            seg = seg->right;
+        }
+    }
+}
+/* SLOPE_NEGATIVE:
+   |   +   /|  +  /    /
+   |   I  / |  I /    /
+   |   I /  |  I/    /
+   |   I/   |  I    /
+   |   I    | /I   /
+   |  /+    |/ +  /
+*/
+void add_points_to_negatively_sloped_segments(status_t*status, xrow_t*xrow, int32_t y)
+{
+    int t;
+    for(t=xrow->num-1;t>=0;t--) {
+        box_t box = box_new(xrow->x[t], y);
+        segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
+        while(seg) {
+            if(seg->a.y == y) {
+                // this segment just started, ignore it
+            } else if(seg->delta.x >= 0) {
+                // ignore segment w/ positive slope
+            } else {
+                double d1 = LINE_EQ(box.left1, seg);
+                double d2 = LINE_EQ(box.left2, seg);
+                if(d1<0 || d2<0) {
+#ifdef DEBUG
+                    dict_put(status->segs_with_point, seg, 0);
+#endif
+                    insert_point_into_segment(seg, box.right2);
+                } else {
+                    break;
+                }
+            }
+            seg = seg->left;
+        }
+    }
+}
+
+void event_apply(status_t*status, event_t*e)
+{
+    switch(e->type) {
+        case EVENT_END: {
+            //delete segment from list
+            event_dump(e);
+            segment_t*s = e->s1;
+            insert_point_into_segment(s, s->b);
+            segment_t*left = actlist_left(status->actlist, s);
+            segment_t*right = actlist_right(status->actlist, s);
+            actlist_delete(status->actlist, s);
+            dict_clear(&s->scheduled_crossings);
+            if(left && right)
+                schedule_crossing(status, left, right, status->y+1);
+            break;
+        }
+        case EVENT_START: {
+            //insert segment into list
+            event_dump(e);
+            segment_t*s = e->s1;
+            actlist_insert(status->actlist, e->p, s);
+            segment_t*left = actlist_left(status->actlist, s);
+            segment_t*right = actlist_right(status->actlist, s);
+            if(left)
+                schedule_crossing(status, left, s, status->y+1);
+            if(right)
+                schedule_crossing(status, s, right, status->y+1);
+            break;
+        }
+        case EVENT_CROSS: {
+            // exchange two (or more) segments
+            event_t*ee = heap_peek(status->queue);
+            if(ee->p.x != e->p.x ||
+               ee->p.y != e->p.y ||
+               ee->type != e->type) {
+                event_dump(e);
+                exchange_two(status, e);
+            } else {
+                exchange_many(status, e);
+            }
+        }
+    }
+}
+
+#ifdef DEBUG
+void check_status(status_t*status)
+{
+    DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
+        if(!dict_contains(status->segs_with_point, s)) {
+            fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n", 
+                    s->nr, 
+                    s->delta.x<0?"-":"+",
+                    status->y);
+            assert(0);
+        }
+    }
+}
+#endif
+
+void gfxpoly_process(segment_t*poly)
+{
+    heap_t* queue = heap_new(sizeof(event_t), compare_events);
+    segments_enqueue(poly, queue);
+    status_t status;
+    memset(&status, 0, sizeof(status_t));
+    status.queue = queue;
+    status.actlist = actlist_new();
+#ifdef DEBUG
+    status.seen_crossings = dict_new2(&point_type);
+#endif
+    
+    xrow_t*xrow = xrow_new();
+
+    event_t*e = heap_chopmax(queue);
+    while(e) {
+        status.y = e->p.y;
+#ifdef DEBUG
+        status.intersecting_segs = dict_new2(&ptr_type);
+        status.segs_with_point = dict_new2(&ptr_type);
+        printf("----------------------------------- %d\n", status.y);
+        actlist_verify_and_dump(status.actlist, status.y-1);
+#endif
+        xrow_reset(xrow);
+        do {
+            xrow_add(xrow, e->p.x);
+            event_apply(&status, e);
+            free(e);
+            e = heap_chopmax(queue);
+        } while(e && status.y == e->p.y);
+
+        xrow_sort(xrow);
+        add_points_to_positively_sloped_segments(&status, xrow, status.y);
+        add_points_to_negatively_sloped_segments(&status, xrow, status.y);
+#ifdef DEBUG
+        check_status(&status);
+        dict_destroy(status.intersecting_segs);
+        dict_destroy(status.segs_with_point);
+#endif
+    }
+#ifdef DEBUG
+    dict_destroy(status.seen_crossings);
+#endif
+    heap_destroy(queue);
+    gfxpoly_destroy(poly);
+    xrow_destroy(xrow);
+}
diff --git a/lib/gfxpoly/poly.h b/lib/gfxpoly/poly.h
new file mode 100644
index 0000000..e9da73c
--- /dev/null
+++ b/lib/gfxpoly/poly.h
@@ -0,0 +1,48 @@
+#ifndef __poly_h__
+#define __poly_h__
+
+#include <stdint.h>
+#include "../q.h"
+
+typedef enum {DIR_UP, DIR_DOWN} segment_dir_t;
+typedef enum {EVENT_CROSS, EVENT_END, EVENT_START} eventtype_t;
+typedef enum {SLOPE_POSITIVE, SLOPE_NEGATIVE} slope_t;
+
+typedef struct _point {
+    int32_t x;
+    int32_t y;
+} point_t;
+
+typedef struct _segment {
+    point_t a;
+    point_t b;
+    point_t delta;
+    double k; //k = a.x*b.y-a.y*b.x = delta.y*a.x - delta.x*a.y (=0 for points on the segment)
+    segment_dir_t dir;
+    int nr;
+    struct _segment*left;
+    struct _segment*right;
+    int tmp;
+    point_t pos;
+
+    dict_t scheduled_crossings;
+} segment_t;
+
+#define LINE_EQ(p,s) ((double)(s)->delta.y*(p).x - (double)(s)->delta.x*(p).y - (s)->k)
+
+typedef segment_t gfxpoly_t;
+gfxpoly_t* gfxpoly_new();
+void gfxpoly_dump(gfxpoly_t*poly);
+
+typedef struct _event {
+    eventtype_t type;
+    point_t p;
+    segment_t*s1;
+    segment_t*s2;
+} event_t;
+
+void segment_init(segment_t*s, int32_t x1, int32_t y1, int32_t x2, int32_t y2);
+segment_t*segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2);
+void segment_insert_before(segment_t**list, segment_t*add);
+
+#endif
diff --git a/lib/gfxpoly/test.c b/lib/gfxpoly/test.c
new file mode 100644
index 0000000..e4e8455
--- /dev/null
+++ b/lib/gfxpoly/test.c
@@ -0,0 +1,81 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <memory.h>
+#include <math.h>
+#include "../gfxtools.h"
+#include "poly.h"
+#include "convert.h"
+
+gfxline_t*mkstar(int x1, int y1, int x2, int y2)
+{
+    gfxline_t*l=0,*line = 0;
+    int x;
+    for(x=x1;x<=x2;x+=50) {
+        l = malloc(sizeof(gfxline_t));
+        l->type = gfx_moveTo;
+        l->x = x;l->y = y1;
+        line = gfxline_append(line, l);
+
+        l = malloc(sizeof(gfxline_t));
+        l->type = gfx_lineTo;
+        l->x = x2-x;l->y = y2;
+        line = gfxline_append(line, l);
+    }
+    return line;
+}
+
+int test1()
+{
+    gfxline_t*box1 = gfxline_makerectangle(50,50,150,150);
+
+    // put box2 and box3 on top of each other *snicker*
+    gfxline_t*box2 = gfxline_makerectangle(100,100,200,200);
+    gfxline_t*box3 = gfxline_makerectangle(100,100,200,200);
+    gfxline_t*star = mkstar(50,50, 150,150);
+    gfxline_t*b = 0;
+    b = gfxline_append(b, box1);
+    b = gfxline_append(b, box2);
+    b = gfxline_append(b, box3);
+    b = gfxline_append(b, star);
+
+    gfxmatrix_t matrix;
+    memset(&matrix, 0, sizeof(gfxmatrix_t));
+    double ua=0.1;
+    matrix.m00=cos(ua);matrix.m10=sin(ua);
+    matrix.m01=-sin(ua);matrix.m11=cos(ua);
+
+    gfxline_transform(b, &matrix);
+    gfxpoly_t*poly = gfxpoly_fillToPoly(b);
+    gfxline_free(box1);
+    gfxline_free(box2);
+    gfxline_free(box3);
+
+    gfxpoly_dump(poly);
+    gfxpoly_process(poly);
+}
+
+int test2()
+{
+#define N 1000
+    int t;
+    gfxline_t* line = malloc(sizeof(gfxline_t)*N);
+    for(t=0;t<N;t++) {
+        line[t].type = t?gfx_lineTo:gfx_moveTo;
+        line[t].x = lrand48()%65536;
+        line[t].y = lrand48()%65536;
+        line[t].next = &line[t+1];
+    }
+    line[N-1].x = line[0].x;
+    line[N-1].y = line[0].y;
+    line[N-1].next = 0;
+    
+    gfxpoly_t*poly = gfxpoly_fillToPoly(line);
+    gfxpoly_dump(poly);
+    gfxpoly_process(poly);
+    gfxline_free(line);
+}
+
+int main()
+{
+    test2();
+}
diff --git a/lib/gfxpoly/xrow.c b/lib/gfxpoly/xrow.c
new file mode 100644
index 0000000..123e00c
--- /dev/null
+++ b/lib/gfxpoly/xrow.c
@@ -0,0 +1,55 @@
+#include "../mem.h"
+#include "xrow.h"
+
+xrow_t* xrow_new()
+{
+    xrow_t*r = rfx_calloc(sizeof(xrow_t));
+    r->size = 16;
+    r->x = rfx_alloc(sizeof(r->x[0])*r->size);
+    return r;
+}
+
+void xrow_add(xrow_t*r, int32_t x)
+{
+    if(r->num >= r->size) {
+        r->size *= 2;
+        r->x = rfx_realloc(r->x, sizeof(r->x[0])*r->size);
+    }
+    r->x[r->num++]=x;
+}
+
+int compare_int32(const void*_i1,const void*_i2)
+{
+    int32_t*i1 = (int32_t*)_i1;
+    int32_t*i2 = (int32_t*)_i2;
+    return i1-i2;
+}
+
+void xrow_sort(xrow_t*r)
+{
+    if(!r->num)
+        return;
+    qsort(r->x, r->num, sizeof(r->x[0]), compare_int32);
+    int t;
+    int pos = 1;
+    int32_t lastx=r->x[0];
+    for(t=1;t<r->num;t++) {
+        if(r->x[t]!=lastx) {
+            r->x[pos++] = lastx = r->x[t];
+        }
+    }
+    r->num = pos;
+}
+
+void xrow_reset(xrow_t*r)
+{
+    r->num = 0;
+}
+
+void xrow_destroy(xrow_t*r)
+{
+    if(r->x) {
+        free(r->x);r->x = 0;
+    }
+    free(r);
+}
diff --git a/lib/gfxpoly/xrow.h b/lib/gfxpoly/xrow.h
new file mode 100644
index 0000000..cc32436
--- /dev/null
+++ b/lib/gfxpoly/xrow.h
@@ -0,0 +1,18 @@
+#ifndef __xrow_h__
+#define __xrow_h__
+
+#include <stdint.h>
+
+typedef struct _xrow {
+    int32_t*x;
+    int num;
+    int size;
+} xrow_t;
+
+xrow_t* xrow_new();
+void xrow_add(xrow_t*xrow, int32_t x);
+void xrow_sort(xrow_t*xrow);
+void xrow_reset(xrow_t*xrow);
+void xrow_destroy(xrow_t*xrow);
+
+#endif
diff --git a/lib/q.c b/lib/q.c
index 94c0b3e..3416a0f 100644
--- a/lib/q.c
+++ b/lib/q.c
@@ -197,35 +197,62 @@ void ringbuffer_clear(ringbuffer_t*r)
 
 // ------------------------------- heap_t -------------------------------
 
-void heap_init(heap_t*h,int n,int elem_size, int(*compare)(const void *, const void *))
+void heap_init(heap_t*h,int elem_size, int(*compare)(const void *, const void *))
 {
     memset(h, 0, sizeof(heap_t));
-    h->max_size = n;
     h->size = 0;
     h->elem_size = elem_size;
     h->compare = compare;
-    h->elements = (void**)rfx_calloc(n*sizeof(void*));
-    h->data = (char*)rfx_calloc(h->max_size*h->elem_size);
+    h->elements = 0;
+    h->max_size = 0;
+}
+heap_t* heap_new(int elem_size, int(*compare)(const void *, const void *))
+{
+    heap_t*h = malloc(sizeof(heap_t));
+    heap_init(h, elem_size, compare);
+    return h;
+}
+heap_t* heap_clone(heap_t*o)
+{
+    heap_t*h = malloc(sizeof(heap_t));
+    memcpy(h, o, sizeof(heap_t));
+    h->elements = rfx_alloc(sizeof(void*)*h->size);
+    int t;
+    for(t=0;t<h->size;t++) {
+        h->elements[t] = rfx_alloc(h->elem_size);
+        memcpy(h->elements[t], o->elements[t], h->elem_size);
+    }
+    return h;
 }
 void heap_clear(heap_t*h)
 {
+    int t;
+    for(t=0;t<h->size;t++) {
+        rfx_free(h->elements[t]);
+        h->elements[t]=0;
+    }
     rfx_free(h->elements);
-    rfx_free(h->data);
+}
+void heap_destroy(heap_t*h)
+{
+    heap_clear(h);
+    free(h);
 }
 
-#define HEAP_NODE_SMALLER(h,node1,node2) ((h)->compare((node1),(node2))>0)
+#define HEAP_NODE_LARGER(h,node1,node2) ((h)->compare((node1),(node2))>0)
+#define HEAP_NODE_SMALLER(h,node1,node2) ((h)->compare((node1),(node2))<0)
 
 static void up(heap_t*h, int node)
 {
     void*node_p = h->elements[node];
     int parent = node;
+    int tmp = node;
     do {
 	node = parent;
 	if(!node) break;
 	parent = (node-1)/2;
 	h->elements[node] = h->elements[parent];
-    } while(HEAP_NODE_SMALLER(h,h->elements[parent], node_p));
-
+    } while(HEAP_NODE_SMALLER(h, h->elements[parent], node_p));
     h->elements[node] = node_p;
 }
 static void down(heap_t*h, int node)
@@ -250,22 +277,33 @@ static void down(heap_t*h, int node)
 void heap_put(heap_t*h, void*e) 
 {
     int pos = h->size++;
-    memcpy(&h->data[pos*h->elem_size],e,h->elem_size);
-    h->elements[pos] = &h->data[pos];
+    void*data = rfx_alloc(h->elem_size);
+    memcpy(data,e,h->elem_size);
+
+    if(pos>=h->max_size) {
+        h->max_size = h->max_size<15?15:(h->max_size+1)*2-1;
+        h->elements = (void**)rfx_realloc(h->elements, h->max_size*sizeof(void*));
+        assert(pos<h->max_size);
+    }
+
+    h->elements[pos] = data;
     up(h, pos);
 }
 int heap_size(heap_t*h)
 {
     return h->size;
 }
-void* heap_max(heap_t*h)
+void* heap_peek(heap_t*h)
 {
+    if(!h || !h->size) 
+        return 0;
     return h->elements[0];
 }
 void* heap_chopmax(heap_t*h)
 {
+    if(!h->size)
+        return 0;
     void*p = h->elements[0];
-    assert(h->size);
     h->elements[0] = h->elements[--h->size];
     down(h,0);
     return p;
@@ -283,7 +321,7 @@ void heap_dump(heap_t*h, FILE*fi)
 }
 void** heap_flatten(heap_t*h)
 {
-    void**nodes = (void**)rfx_alloc(h->size*sizeof(void*));
+    void**nodes = (void**)rfx_alloc((h->size+1)*sizeof(void*));
     void**p = nodes;
    
     while(h->size) {
@@ -292,6 +330,7 @@ void** heap_flatten(heap_t*h)
 	printf("\n");*/
 	*p++ = heap_chopmax(h);
     }
+    *p++ = 0;
     return nodes;
 }
 
@@ -991,6 +1030,10 @@ dictentry_t* dict_put(dict_t*h, const void*key, void* data)
 {
     unsigned int hash = h->key_type->hash(key);
     dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
+    
+    if(!h->hashsize)
+        dict_expand(h, 1);
+
     unsigned int hash2 = hash % h->hashsize;
     
     e->key = h->key_type->dup(key);
diff --git a/lib/q.h b/lib/q.h
index 4674cf4..df1c074 100644
--- a/lib/q.h
+++ b/lib/q.h
@@ -197,9 +197,18 @@ void dict_free_all(dict_t*h, char free_keys, void (*free_data_function)(void*));
 void dict_clear(dict_t*h);
 void dict_destroy_shallow(dict_t*dict);
 void dict_destroy(dict_t*dict);
-#define DICT_ITERATE_DATA(d,t,v) int v##_i;dictentry_t*v##_e;t v;for(v##_i=0;v##_i<(d)->hashsize;v##_i++) for(v##_e=(d)->slots[v##_i]; v##_e && ((v=(t)v##_e->data)||1); v##_e=v##_e->next)
-#define DICT_ITERATE_KEY(d,t,v)  int v##_i;dictentry_t*v##_e;t v;for(v##_i=0;v##_i<(d)->hashsize;v##_i++) for(v##_e=(d)->slots[v##_i];v##_e && ((v=(t)v##_e->key)||1);v##_e=v##_e->next)
-#define DICT_ITERATE_ITEMS(d,t1,v1,t2,v2) int v1##_i;dictentry_t*v1##_e;t1 v1;t2 v2;for(v1##_i=0;v1##_i<(d)->hashsize;v1##_i++) for(v1##_e=(d)->slots[v1##_i]; v1##_e && (((v1=(t1)v1##_e->key)&&(v2=(t2)v1##_e->data))||1); v1##_e=v1##_e->next)
+#define DICT_ITERATE_DATA(d,t,v) \
+    int v##_i;dictentry_t*v##_e;t v;\
+    for(v##_i=0;v##_i<(d)->hashsize;v##_i++) \
+        for(v##_e=(d)->slots[v##_i]; v##_e && ((v=(t)v##_e->data)||1); v##_e=v##_e->next)
+#define DICT_ITERATE_KEY(d,t,v)  \
+    int v##_i;dictentry_t*v##_e;t v;\
+    for(v##_i=0;v##_i<(d)->hashsize;v##_i++) \
+        for(v##_e=(d)->slots[v##_i];v##_e && ((v=(t)v##_e->key)||1);v##_e=v##_e->next)
+#define DICT_ITERATE_ITEMS(d,t1,v1,t2,v2) \
+    int v1##_i;dictentry_t*v1##_e;t1 v1;t2 v2; \
+    for(v1##_i=0;v1##_i<(d)->hashsize;v1##_i++) \
+        for(v1##_e=(d)->slots[v1##_i]; v1##_e && (((v1=(t1)v1##_e->key)&&(v2=(t2)v1##_e->data))||1); v1##_e=v1##_e->next)
 
 void map_init(map_t*map);
 void map_put(map_t*map, string_t t1, string_t t2);
@@ -208,11 +217,14 @@ void map_dump(map_t*map, FILE*fi, const char*prefix);
 void map_clear(map_t*map);
 void map_destroy(map_t*map);
 
-void heap_init(heap_t*h,int n,int elem_size, int(*compare)(const void *, const void *));
+void heap_init(heap_t*h,int elem_size, int(*compare)(const void *, const void *));
+heap_t* heap_new(int elem_size, int(*compare)(const void *, const void *));
+heap_t* heap_clone(heap_t*o);
 void heap_clear(heap_t*h);
+void heap_destroy(heap_t*h);
 void heap_put(heap_t*h, void*e);
 int heap_size(heap_t*h);
-void* heap_max(heap_t*h);
+void* heap_peek(heap_t*h);
 void* heap_chopmax(heap_t*h);
 void heap_dump(heap_t*h, FILE*fi);
 void** heap_flatten(heap_t*h);