Beginning of linear algorithm

1 files changed, 16 insertions, 224 deletions

diff --git a/region_to_path.c b/region_to_path.c
index 437bd08..bf1f2dd 100644
--- a/region_to_path.c
+++ b/region_to_path.c
@@ -176,238 +176,23 @@ add_hsegment (cairo_t *cr, hsegment_t *h, gboolean go_right)
 static void
 region_to_path (cairo_t *cr, cairo_region_t *region)
 {
-    int i;
-    GArray *hsegments = g_array_new (TRUE, TRUE, sizeof (hsegment_t));
-    GArray *vsegments = g_array_new (TRUE, TRUE, sizeof (vsegment_t));
-    hsegment_t h;
-    vsegment_t v;
-    
-    h.left = h.right = NULL;
-    v.top = v.bottom = NULL;
+    int n_rects = cairo_region_num_rectangles (region);
+    int n_segments = 2 * n_rects;
     
-    for (i = 0; i < cairo_region_num_rectangles (region); ++i)
+    hsegment_t *hsegments = g_new (hsegment_t, n_segments);
+    vsegment_t *vsegments = g_new (vsegment_t, n_segments);
+
+    int i;
+
+    for (i = 0; i < n_rects; ++i)
     {
 	cairo_rectangle_int_t rect;
-	
+
 	cairo_region_get_rectangle (region, i, &rect);
-	
-	h.x1 = rect.x;
-	h.x2 = rect.x + rect.width;
-	
-	h.y = rect.y;
-	
-	g_array_append_val (hsegments, h);
-	
-	h.y = rect.y + rect.height;
-	
-	g_array_append_val (hsegments, h);
-	
-	v.y1 = rect.y;
-	v.y2 = rect.y + rect.height;
-	
-	v.x = rect.x;
-	
-	g_array_append_val (vsegments, v);
-	
-	v.x = rect.x + rect.width;
-	
-	g_array_append_val (vsegments, v);
-    }
-    
-    g_array_sort (hsegments, compare_hsegments);
-    g_array_sort (vsegments, compare_vsegments);
-    
-    /* Deal with overlapping hsegments */
-    for (i = 1; i < hsegments->len; ++i)
-    {
- 	hsegment_t *this = &g_array_index (hsegments, hsegment_t, i);
- 	hsegment_t *prev = &g_array_index (hsegments, hsegment_t, i - 1);
-	
-	if (this->y == prev->y && this->x1 < prev->x2)
-	{
-	    int tmp = prev->x2;
-	    
-#if 0
-	    g_print ("[%d: %d %d] and [%d: %d %d]    ->     ",
-		     prev->y, prev->x1, prev->x2,
-		     this->y, this->x1, this->x2);
-#endif
-	    
-	    prev->x2 = this->x1;
-	    this->x1 = tmp;
-	    
-	    if (this->x1 > this->x2)
-	    {
-		tmp = this->x2;
-		this->x2 = this->x1;
-		this->x1 = tmp;
-	    }
-	    
-#if 0
-	    g_print ("[%d: %d %d] and [%d: %d %d]\n",
-		     prev->y, prev->x1, prev->x2,
-		     this->y, this->x1, this->x2);
-#endif
-	}
-    }
-    
-    /* Coalesce abutting vsegments */
-    for (i = 1; i < vsegments->len; ++i)
-    {
-	vsegment_t *this = &g_array_index (vsegments, vsegment_t, i);
-	vsegment_t *prev = &g_array_index (vsegments, vsegment_t, i - 1);
-	
-	if (this->x == prev->x && this->y1 == prev->y2)
-	{
-#if 0
-	    g_print ("   prev %d %d %d \n", this->x, this->y1, this->y2);
-#endif
 
-	    /* Add 'prev' into 'this' rather than the other way around.
-	     * This way, the next iteration only has to look at its 'prev',
-	     * not two steps behind
-	     */
-	    
-	    prev->y2 = prev->y1;
-	    this->y1 = prev->y1;
-	    
-#if 0
-	    g_print ("generated segment: %d: %d %d\n", prev->x, prev->y1, prev->y2);
-#endif
-	}
-    }
-    
-    /* Finally, for each non-empty hsegment, find the corresponding
-     * vsegments
-     * FIXME: this should be done with binary search
-     */
-    for (i = 0; i < hsegments->len; ++i)
-    {
-	hsegment_t *h = &g_array_index (hsegments, hsegment_t, i);
-	int j;
 	
-	if (h->x1 == h->x2)
-	    continue;
-
-	g_assert (!h->left);
-	g_assert (!h->right);
 	
-	for (j = 0; j < vsegments->len; ++j)
-	{
-	    vsegment_t *v = &g_array_index (vsegments, vsegment_t, j);
-	    
-	    if (v->y1 == v->y2)
-		continue;
-	    
-	    if (v->y1 == h->y)
-	    {
-		if (v->x == h->x1)
-		{
-		    if (h->left)
-		    {
-			g_print ("  [ %d: %d %d ] already has left\n",
-				 h->y, h->x1, h->x2);
-		    }
-		    
-		    g_assert (v->top == NULL);
-		    g_assert (h->left == NULL);
-		    
-		    v->top = h;
-		    h->left = v;
-		}
-		
-		if (v->x == h->x2)
-		{
-		    if (h->right)
-		    {
-			g_print ("  [ %d: %d %d ] already has right: %d %d %d\n",
-				 h->y, h->x1, h->x2,
-				 v->x, v->y1, v->y2);
-		    }
-		    g_assert (v->top == NULL);
-		    g_assert (h->right == NULL);
-		    
-		    v->top = h;
-		    h->right = v;
-		}
-	    }
-	    
-	    if (v->y2 == h->y)
-	    {
-		if (v->x == h->x1)
-		{
-		    g_assert (v->bottom == NULL);
-		    g_assert (h->left == NULL);
-		    
-		    v->bottom = h;
-		    h->left = v;
-		}
-		
-		if (v->x == h->x2)
-		{
-		    if (h->right)
-		    {
-			g_print ("  [ %d: %d %d ] already has right: %d %d %d\n",
-				 h->y, h->x1, h->x2,
-				 v->x, v->y1, v->y2);
-		    }
-		    
-		    g_assert (v->bottom == NULL);
-		    g_assert (h->right == NULL);
-		    
-		    v->bottom = h;
-		    h->right = v;
-		}
-	    }
-	}
-
-	g_assert (h->left);
-	g_assert (h->right);
-    }
-
-    for (i = 0; i < hsegments->len; ++i)
-    {
-	hsegment_t *h = &g_array_index (hsegments, hsegment_t, i);
-
-	if (h->x1 != h->x2)
-	{
-	    g_assert (h->left);
-	    g_assert (h->right);
-	}
-    }
-
-    for (i = 0; i < vsegments->len; ++i)
-    {
-	vsegment_t *v = &g_array_index (vsegments, vsegment_t, i);
-
-	if (v->y1 != v->y2)
-	{
-	    if (!v->bottom)
-	    {
-		g_print ("no bottom for %d %d %d\n", v->x, v->y1, v->y2);
-	    }
-	    
-	    g_assert (v->top);
-	    g_assert (v->bottom);
-	}
     }
-    
-    if (cr)
-    {
-	for (i = 0; i < hsegments->len; ++i)
-	{
-	    hsegment_t *h = &g_array_index (hsegments, hsegment_t, i);
-	    
-	    if (h->left)
-	    {
-		cairo_move_to (cr, h->x1, h->y);
-		add_hsegment (cr, h, TRUE);
-	    }
-	}
-    }
-    
-    g_array_free (hsegments, TRUE);
-    g_array_free (vsegments, TRUE);
 }
 
 static gboolean
@@ -422,6 +207,13 @@ on_expose (GtkWidget *widget, GdkEvent *event, gpointer data)
 	int i;
 	
 	region = cairo_region_create();
+
+	rect.x = 20;
+	rect.y = 50;
+	rect.width = 10;
+	rect.height = 10;
+	
+	cairo_region_subtract_rectangle (region, &rect);
 	
 	for (i = 0; i < sizeof (rects) / sizeof (rects[0]); ++i)
 	    cairo_region_union_rectangle (region, &rects[i]);