more bugfixes in new polygon intersector

[swftools.git] / lib / gfxpoly / active.c

diff --git a/lib/gfxpoly/active.c b/lib/gfxpoly/active.c
index d726a01..02638f5 100644 (file)
--- a/lib/gfxpoly/active.c
+++ b/lib/gfxpoly/active.c
@@ -1,4 +1,3 @@
-#include <assert.h>
 #include "../q.h"
 #include "active.h"
 
@@ -7,8 +6,32 @@ actlist_t* actlist_new()
     NEW(actlist_t, a);
     return a;
 }
+void actlist_destroy(actlist_t*a)
+{
+    free(a);
+}
 
-void actlist_verify_and_dump(actlist_t*a, int32_t y)
+void actlist_dump(actlist_t*a, int32_t y)
+{
+    segment_t*s = a->list;
+    double lastx;
+    char bad = 0;
+    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) 
+                    fprintf(stderr, "?%f<->%f? ", lastx, x);
+            }
+            lastx = x;
+        }
+        fprintf(stderr, "[%d]", s->nr);
+        s = s->right;
+        if(s) fprintf(stderr, " ");
+        else fprintf(stderr, "\n");
+    }
+}
+void actlist_verify(actlist_t*a, int32_t y)
 {
     segment_t*s = a->list;
     assert(!s || !s->left);
@@ -17,23 +40,23 @@ void actlist_verify_and_dump(actlist_t*a, int32_t y)
         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);
+                assert(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)) */
+       tree to run in ammortized O(log(n)) 
+       (update: currently only 2.5% of the algorithm's running time is spent here,
+        so maybe we don't need to bother)
+     */
     segment_t*last=0, *s = a->list;
     if(!s) return last;
     while(s) {
@@ -69,6 +92,7 @@ static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s)
         s->left->right = s;
     if(s->right) 
         s->right->left = s;
+    a->size++;
 }
 
 void actlist_insert(actlist_t*a, point_t p, segment_t*s)
@@ -88,6 +112,11 @@ void actlist_delete(actlist_t*a, segment_t*s)
         s->right->left = s->left;
     }
     s->left = s->right = 0;
+    a->size--;
+}
+int actlist_size(actlist_t*a)
+{
+    return a->size;
 }
 
 segment_t* actlist_leftmost(actlist_t*a)
@@ -95,6 +124,18 @@ segment_t* actlist_leftmost(actlist_t*a)
     return a->list;
 }
 
+segment_t* actlist_rightmost(actlist_t*a)
+{
+    /* this is only used in checks, so it doesn't matter that it's slow */
+    segment_t*s = a->list;
+    segment_t*last = 0;
+    while(s) {
+        last = s;
+        s = s->right;
+    }
+    return last;
+}
+
 segment_t* actlist_left(actlist_t*a, segment_t*s)
 {
     return s->left;
@@ -102,7 +143,8 @@ segment_t* actlist_left(actlist_t*a, segment_t*s)
 
 segment_t* actlist_right(actlist_t*a, segment_t*s)
 {
-    return s->right;
+    if(s) return s->right;
+    else  return a->list;
 }
 
 void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
@@ -110,32 +152,3 @@ 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;
-    }
-}