Add contains_point/rectangle

1 files changed, 112 insertions, 2 deletions

diff --git a/region-iter.c b/region-iter.c
index 0c58f1f..0d0e2a6 100644
--- a/region-iter.c
+++ b/region-iter.c
@@ -446,8 +446,41 @@ region_iter_get_row (region_iter_t *iter, row_t *row)
     return TRUE;
 }
 
+/* In time O(log n), locate the first box whose y2 is greater than y.
+ * Return @end if no such box exists.
+ */
+static pixman_box32_t *
+find_box_for_y (pixman_box32_t *begin, pixman_box32_t *end, int y)
+{
+    pixman_box32_t *mid;
+
+    if (end == begin)
+	return end;
+
+    if (end - begin == 1)
+    {
+	if (begin->y2 > y)
+	    return begin;
+	else
+	    return end;
+    }
+
+    mid = begin + (end - begin) / 2;
+    if (mid->y2 > y)
+    {
+	/* If no box is found in [begin, mid], the function
+	 * will return @mid, which is then known to be the
+	 * correct answer.
+	 */
+	return find_box_for_y (begin, mid, y);
+    }
+    else
+    {
+	return find_box_for_y (mid, end, y);
+    }
+}
+
 /* Skips forward to the first row whose y2 > @y */
-#if 0
 static pixman_bool_t
 region_iter_get_row_for_y (region_iter_t *iter, int y, row_t *row)
 {
@@ -479,7 +512,6 @@ region_iter_get_row_for_y (region_iter_t *iter, int y, row_t *row)
 
     return region_iter_get_row (iter, row);
 }
-#endif
 
 /* Overlapped iter
  */
@@ -704,6 +736,81 @@ segment_iter_get_segment (segment_iter_t *iter, segment_t *segment)
     return TRUE;
 }
 
+
+pixman_bool_t
+region_contains_point (pixman_region32_t *region,
+		       int                x,
+		       int                y,
+		       pixman_box32_t    *box)
+{
+    region_iter_t iter;
+    row_t row;
+
+    region_iter_init (&iter, region);
+    if (region_iter_get_row_for_y (&iter, y, &row) && row.y1 < y)
+    {
+	const pixman_box32_t *b;
+
+	for (b = row.first; b != row.last && b->x1 <= x; ++b)
+	{
+	    if (x < b->x2)
+	    {
+		if (box)
+		    *box = *b;
+
+		return TRUE;
+	    }
+	}
+    }
+
+    return FALSE;
+}
+
+pixman_region_overlap_t
+region_contains_rectangle (pixman_region32_t *region,
+			   pixman_box32_t    *prect)
+{
+    pixman_bool_t part_in = FALSE;
+    pixman_bool_t part_out = FALSE;
+    region_iter_t iter;
+    row_t row;
+
+    region_iter_init (&iter, region);
+    if (!region_iter_get_row_for_y (&iter, prect->y1, &row))
+	return PIXMAN_REGION_OUT;
+
+    if (row.y1 >= prect->y2)
+	return PIXMAN_REGION_OUT;
+    
+    do
+    {
+	row_iter_t row_iter;
+	segment_t segment;
+
+	row_iter_init (&row_iter, &row);
+	while (row_iter_get_segment (&row_iter, &segment) &&
+	       segment.x1 <= prect->x2)
+	{
+	    if (segment.x2 >= prect->x1)
+	    {
+		if (segment.type == ON)
+		    part_in = TRUE;
+		else
+		    part_out = TRUE;
+	    }
+
+	    if (part_in && part_out)
+		return PIXMAN_REGION_PART;
+	}
+    }
+    while (region_iter_get_row (&iter, &row) && row.y1 < prect->y2);
+
+    if (part_in)
+	return PIXMAN_REGION_IN;
+    else
+	return PIXMAN_REGION_OUT;
+}
+
 typedef enum
 {
     INTERSECT	= (1 << BOTH),
@@ -1136,6 +1243,9 @@ main ()
     pixman_region32_init_rect (&region, 0, 0, 100, 100);
     pixman_region32_union_rect (&region, &region, 50, 50, 100, 100);
 
+    assert (region_contains_point (&region, 75, 75, NULL));
+    assert (!region_contains_point (&region, 25, 125, NULL));
+    
     printf ("-=- more complex path\n");
 
     corners = region_path (&region, &n_corners);