GdkSpan

[Alexander Larsson <alla lysator liu se>]

For my next checkin to GtkFB i need to do some generic Gdk changes. I
added a new type GdkSpan, and two functions that handle intersection these
with regions.

Is this patch ok? I'd also be very glad if someone (owen?) reviewed the
intersection functions, since these kind of functions are very sensitive
to boundary condition errors, and quite hard to test.

/ Alex

Index: gdktypes.h
===================================================================
RCS file: /cvs/gnome/gtk+/gdk/gdktypes.h,v
retrieving revision 1.56
diff -u -p -r1.56 gdktypes.h
--- gdktypes.h	2000/09/07 18:07:59	1.56
+++ gdktypes.h	2000/11/20 13:31:58
@@ -67,6 +67,7 @@ extern "C" {
 typedef struct _GdkPoint	      GdkPoint;
 typedef struct _GdkRectangle	      GdkRectangle;
 typedef struct _GdkSegment	      GdkSegment;
+typedef struct _GdkSpan	              GdkSpan;
 
 /*
  * Note that on some platforms the wchar_t type
@@ -182,6 +183,13 @@ struct _GdkSegment
   gint y1;
   gint x2;
   gint y2;
+};
+
+struct _GdkSpan
+{
+  gint x;
+  gint y;
+  gint width;
 };
 
 #ifdef __cplusplus
Index: gdkregion.h
===================================================================
RCS file: /cvs/gnome/gtk+/gdk/gdkregion.h,v
retrieving revision 1.2
diff -u -p -r1.2 gdkregion.h
--- gdkregion.h	2000/03/28 01:24:42	1.2
+++ gdkregion.h	2000/11/20 13:31:58
@@ -29,6 +29,19 @@ typedef enum
   GDK_OVERLAP_RECTANGLE_PART
 } GdkOverlapType;
 
+/* Types of intersections between a span and a region
+ * GDK_INTERSECT_SPAN_SIMPLE: The intersection is a span
+ * GDK_INTERSECT_SPAN_COMPLEX: The intersection consists of several spans
+ * GDK_INTERSECT_SPAN_EMPTY: The intersection is empty
+ */
+typedef enum
+{
+  GDK_INTERSECT_SPAN_SIMPLE,
+  GDK_INTERSECT_SPAN_COMPLEX,
+  GDK_INTERSECT_SPAN_EMPTY
+} GdkSpanIntersectType;
+
+
 GdkRegion *gdk_region_new       (void);
 GdkRegion *gdk_region_polygon   (GdkPoint     *points,
 				 gint          npoints,
@@ -65,6 +78,11 @@ void gdk_region_subtract        (GdkRegi
 				 GdkRegion    *source2);
 void gdk_region_xor             (GdkRegion    *source1,
 				 GdkRegion    *source2);
+
+GdkSpanIntersectType gdk_region_span_simple_intersect (GdkRegion *region,
+						       GdkSpan   *span);
+GList *              gdk_region_span_intersect        (GdkRegion *region,
+						       GdkSpan   *span);
 
 #ifdef __cplusplus
 }
Index: gdkregion-generic.c
===================================================================
RCS file: /cvs/gnome/gtk+/gdk/gdkregion-generic.c,v
retrieving revision 1.4
diff -u -p -r1.4 gdkregion-generic.c
--- gdkregion-generic.c	2000/08/09 02:56:13	1.4
+++ gdkregion-generic.c	2000/11/20 13:31:58
@@ -1505,3 +1505,122 @@ gdk_region_rect_in (GdkRegion    *region
 	      GDK_OVERLAP_RECTANGLE_PART : GDK_OVERLAP_RECTANGLE_IN) : 
 	  GDK_OVERLAP_RECTANGLE_OUT);
 }
+
+GdkSpanIntersectType
+gdk_region_span_simple_intersect (GdkRegion *region,
+				  GdkSpan   *span)
+{
+  gint left, right, y;
+  gint clipped_left, clipped_right;
+  GdkRegionBox *pbox;
+  GdkRegionBox *pboxEnd;
+  gboolean partIn;
+
+  if (!region->numRects)
+    return GDK_INTERSECT_SPAN_EMPTY;
+
+  y = span->y;
+  left = span->x;
+  right = span->x + span->width; /* right is not in the span! */
+    
+  if (! ((region->extents.y1 <= y) &&
+	 (region->extents.y2 > y) &&
+	 (region->extents.x1 < right) &&
+	 (region->extents.x2 > left)) ) 
+    return GDK_INTERSECT_SPAN_EMPTY;
+
+  clipped_left = left;
+  clipped_right = right;
+
+  partIn = FALSE;
+  /* can stop when we passed y */
+  for (pbox = region->rects, pboxEnd = pbox + region->numRects;
+       pbox < pboxEnd;
+       pbox++)
+    {
+      if (pbox->y2 <= y)
+	continue; /* Not quite there yet */
+
+      if (pbox->y1 > y)
+	break; /* passed the spanline */
+
+      if ((right > pbox->x1) && (left < pbox->x2)) 
+	{
+	  /* Span partially intersected pbox */
+	  if (partIn)
+	    return GDK_INTERSECT_SPAN_COMPLEX;
+	  
+	  partIn = TRUE;
+
+	  if (left < pbox->x1)
+	    clipped_left = pbox->x1;
+	  
+	  if (right > pbox->x2)
+	    clipped_right = pbox->x2;
+	}
+    }
+  
+  if (partIn)
+    {
+      span->x = clipped_left;
+      span->width = clipped_right - clipped_left;
+      return GDK_INTERSECT_SPAN_SIMPLE;
+    }
+  
+  return GDK_INTERSECT_SPAN_EMPTY;
+}
+
+GList *
+gdk_region_span_intersect (GdkRegion *region,
+			   GdkSpan   *span)
+{
+  gint left, right, y;
+  gint clipped_left, clipped_right;
+  GdkRegionBox *pbox;
+  GdkRegionBox *pboxEnd;
+  GList *spans;
+  GdkSpan *clipped_span;
+
+  /* No optimization cases. Those are normally handled
+   * by gdk_region_span_simple_intersect()
+   */
+  
+  y = span->y;
+  left = span->x;
+  right = span->x + span->width; /* right is not in the span! */
+    
+  spans = NULL;
+
+  /* can stop when we passed y */
+  for (pbox = region->rects, pboxEnd = pbox + region->numRects;
+       pbox < pboxEnd;
+       pbox++)
+    {
+      if (pbox->y2 <= y)
+	continue; /* Not quite there yet */
+
+      if (pbox->y1 > y)
+	break; /* passed the spanline */
+
+      if ((right > pbox->x1) && (left < pbox->x2))
+	{
+	  /* Span partially intersected pbox */
+	  clipped_left = left;
+	  clipped_right = right;
+	  
+	  if (left < pbox->x1)
+	    clipped_left = pbox->x1;
+	  
+	  if (right > pbox->x2)
+	    clipped_right = pbox->x2;
+
+	  clipped_span = g_new (GdkSpan, 1);
+	  clipped_span->y = y;
+	  clipped_span->x = clipped_left;
+	  clipped_span->width = clipped_right - clipped_left;
+	  spans = g_list_append (spans, clipped_span);
+	}
+    }
+  
+  return spans;
+}