Add routines to find all the "screen edges" (where struts are considered

2005-10-31  Elijah Newren  <newren@gmail.com>

	Add routines to find all the "screen edges" (where struts are
	considered to be offscreen), plus a thorough testing case.

	* src/boxes.[ch] (meta_rectangle_free_list_and_elements):
	* src/testboxes.c (test_regions_okay, test_region_fitting,
	  test_clamping_to_region, test_clipping_to_region,
	  test_shoving_into_region):
	* src/workspace.c (meta_workspace_free,
	  meta_workspace_invalidate_work_area):
	meta_rectangle_free_spanning_set() was renamed to
	meta_rectangle_free_list_and_elements()

	* src/boxes.c:

	(meta_rectangle_region_to_string):
	Output SOMETHING if the list is empty

	(meta_rectangle_edge_to_string, meta_rectangle_edge_list_to_string):
	new printing functions for edges

	(meta_rectangle_get_minimal_spanning_set_for_region):
	clean up the overview comment a little

	(struts_are_disjoint):
	(sort_edges):
	(edges_overlap):
	(rectangle_and_edge_intersection):
	(add_edges):
	(split_edge):
	(fix_up_edges):
	(meta_rectangle_find_onscreen_edges):
	New functions to do various parts of finding all the screen edges

	* src/boxes.h:

	(BOX_LEFT, BOX_RIGHT, BOX_TOP, BOX_BOTTOM):
	convenience macros that I should have defined a long time ago

	(enum MetaEdgeType):
	(struct MetaEdge):
	new types for edges

	(meta_rectangle_edge_to_string):
	(meta_rectangle_edge_list_to_string):
	(meta_rectangle_find_onscreen_edges):
	new functions

	* src/common.h:

	(enum MetaDirection):
	direction stuff seems to be used everywhere so add a type here;
	only used in boxes for now, but add a note explaining several
	other places where it could be used to remove duplicative enums

	* src/testboxes.c:

	(new_onscreen_edge):
	(verify_edge_lists_are_equal):
	(test_find_onscreen_edges):
	new functions for testing the new "screen edge" finding abilities

	(main):
	add test_find_onscreen_edges() to the list

	(get_strut_list):
	new function factored out from get_screen_region()

	(get_screen_region):
	call get_strut_list() since it now has most of the code this
	function used to have.

	(get_screen_edges):
	new function to compute the screen edges using the struts in
	get_strut_list() and the meta_rectangle_find_onscreen_edges()
	function.

6 files changed, 861 insertions, 48 deletions

diff --git a/ChangeLog b/ChangeLog
index cd3f5b25..5845bfb1 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,81 @@
+2005-10-31  Elijah Newren  <newren@gmail.com>
+
+	Add routines to find all the "screen edges" (where struts are
+	considered to be offscreen), plus a thorough testing case.
+
+	* src/boxes.[ch] (meta_rectangle_free_list_and_elements):
+	* src/testboxes.c (test_regions_okay, test_region_fitting,
+	  test_clamping_to_region, test_clipping_to_region,
+	  test_shoving_into_region):
+	* src/workspace.c (meta_workspace_free,
+	  meta_workspace_invalidate_work_area):
+	meta_rectangle_free_spanning_set() was renamed to
+	meta_rectangle_free_list_and_elements()
+
+	* src/boxes.c:
+
+	(meta_rectangle_region_to_string):
+	Output SOMETHING if the list is empty
+
+	(meta_rectangle_edge_to_string, meta_rectangle_edge_list_to_string):
+	new printing functions for edges
+
+	(meta_rectangle_get_minimal_spanning_set_for_region):
+	clean up the overview comment a little
+
+	(struts_are_disjoint):
+	(sort_edges):
+	(edges_overlap):
+	(rectangle_and_edge_intersection):
+	(add_edges):
+	(split_edge):
+	(fix_up_edges):
+	(meta_rectangle_find_onscreen_edges):
+	New functions to do various parts of finding all the screen edges
+
+	* src/boxes.h:
+
+	(BOX_LEFT, BOX_RIGHT, BOX_TOP, BOX_BOTTOM):
+	convenience macros that I should have defined a long time ago
+
+	(enum MetaEdgeType):
+	(struct MetaEdge):
+	new types for edges
+
+	(meta_rectangle_edge_to_string):
+	(meta_rectangle_edge_list_to_string):
+	(meta_rectangle_find_onscreen_edges):
+	new functions
+
+	* src/common.h:
+
+	(enum MetaDirection):
+	direction stuff seems to be used everywhere so add a type here;
+	only used in boxes for now, but add a note explaining several
+	other places where it could be used to remove duplicative enums
+
+	* src/testboxes.c:
+
+	(new_onscreen_edge):
+	(verify_edge_lists_are_equal):
+	(test_find_onscreen_edges):
+	new functions for testing the new "screen edge" finding abilities
+
+	(main):
+	add test_find_onscreen_edges() to the list
+
+	(get_strut_list):
+	new function factored out from get_screen_region()
+
+	(get_screen_region):
+	call get_strut_list() since it now has most of the code this
+	function used to have.
+
+	(get_screen_edges):
+	new function to compute the screen edges using the struts in
+	get_strut_list() and the meta_rectangle_find_onscreen_edges()
+	function.
+
 2005-10-28  Elijah Newren  <newren@gmail.com>
 
 	Three major changes: (1) Caching the spanning_rectangles in each
diff --git a/src/boxes.c b/src/boxes.c
index 9dc83603..31d8f5a1 100644
--- a/src/boxes.c
+++ b/src/boxes.c
@@ -60,6 +60,10 @@ meta_rectangle_region_to_string (GList      *region,
    * rectangle.
    */
   char rect_string[27];
+
+  if (region == NULL)
+    snprintf (output, 10, "(EMPTY)");
+
   char *cur = output;
   GList *tmp = region;
   while (tmp)
@@ -76,6 +80,60 @@ meta_rectangle_region_to_string (GList      *region,
   return output;
 }
 
+char*
+meta_rectangle_edge_to_string (const MetaEdge *edge,
+                               char           *output)
+{
+  /* 25 = 2 commas, space, plus, trailing \0 + 5 for each digit.
+   * Should be more than enough space.  Note that of this space, the
+   * trailing \0 will be overwritten for all but the last rectangle.
+   *
+   * Plus 2 for parenthesis, 4 for 2 more numbers, 2 more commas, and
+   * 2 more spaces, for a total of 10 more.
+   */
+  snprintf (output, 35, "[%d,%d +%d,%d], %2d, %2d", 
+            edge->rect.x, edge->rect.y, edge->rect.width, edge->rect.height,
+            edge->side_type, edge->edge_type);
+
+  return output;
+}
+
+char*
+meta_rectangle_edge_list_to_string (GList      *edge_list,
+                                    const char *separator_string,
+                                    char       *output)
+{
+  /* 27 = 2 commas, 2 square brackets, space, plus, trailing \0 + 5 for
+   * each digit.  Should be more than enough space.  Note that of this
+   * space, the trailing \0 will be overwritten for all but the last
+   * rectangle.
+   *
+   * Plus 2 for parenthesis, 4 for 2 more numbers, 2 more commas, and
+   * 2 more spaces, for a total of 10 more.
+   */
+  char rect_string[27 + 10];
+
+  if (edge_list == NULL)
+    snprintf (output, 10, "(EMPTY)");
+
+  char *cur = output;
+  GList *tmp = edge_list;
+  while (tmp)
+    {
+      MetaEdge      *edge = tmp->data;
+      MetaRectangle *rect = &edge->rect;
+      snprintf (rect_string, 37, "([%d,%d +%d,%d], %2d, %2d)", 
+                rect->x, rect->y, rect->width, rect->height,
+                edge->side_type, edge->edge_type);
+      cur = g_stpcpy (cur, rect_string);
+      tmp = tmp->next;
+      if (tmp)
+        cur = g_stpcpy (cur, separator_string);
+    }
+
+  return output;
+}
+
 int
 meta_rectangle_area (const MetaRectangle *rect)
 {
@@ -548,13 +606,14 @@ meta_rectangle_get_minimal_spanning_set_for_region (
   MetaRectangle *temp_rect;
 
   /* The algorithm is basically as follows:
-   *   Ignore directional expansions until the end
    *   Initialize rectangle_set to basic_rect
    *   Foreach strut:
    *     Foreach rectangle in rectangle_set:
    *       - Split the rectangle into new rectangles that don't overlap the
    *         strut (but which are as big as possible otherwise)
-   *   Now do directional expansion of all rectangles in rectangle_set
+   *       - Remove the old (pre-split) rectangle from the rectangle_set,
+   *         and replace it with the new rectangles generated from the
+   *         splitting
    */
 
   temp_rect = g_new (MetaRectangle, 1);
@@ -689,12 +748,12 @@ meta_rectangle_expand_region (GList     *region,
 }
 
 void
-meta_rectangle_free_spanning_set (GList *spanning_rects)
+meta_rectangle_free_list_and_elements (GList *filled_list)
 {
-  g_list_foreach (spanning_rects, 
+  g_list_foreach (filled_list, 
                   (void (*)(gpointer,gpointer))&g_free, /* ew, for ugly */
                   NULL);
-  g_list_free (spanning_rects);
+  g_list_free (filled_list);
 }
 
 gboolean
@@ -1050,3 +1109,421 @@ meta_rectangle_find_linepoint_closest_to_point (double x1,    double y1,
   *valx = (py*diffx*diffy + px*diffx*diffx + y2*x1*diffy - y1*x2*diffy) / den;
   *valy = (px*diffx*diffy + py*diffy*diffy + x2*y1*diffx - x1*y2*diffx) / den;
 }
+
+/***************************************************************************/
+/*                                                                         */
+/* Switching gears to code for edges instead of just rectangles            */
+/*                                                                         */
+/***************************************************************************/
+
+/* Just make sure the given rectangle list is composed of disjoint rectangles */
+static gboolean
+struts_are_disjoint (const GSList *struts)
+{
+  const GSList *tmp;
+  gboolean disjoint = TRUE;
+
+  tmp = struts;
+  while (tmp && disjoint)
+    {
+      const GSList *compare;
+
+      MetaRectangle *cur = tmp->data;
+      compare = tmp->next;
+      while (compare && disjoint)
+        {
+          MetaRectangle *comp = compare->data;
+          disjoint = disjoint && !meta_rectangle_overlap (cur, comp);
+          compare = compare->next;
+        }
+
+      tmp = tmp->next;
+    }
+
+  return disjoint;
+}
+
+/* To make things easily testable, provide a nice way of sorting edges */
+static gint
+sort_edges (gconstpointer a, gconstpointer b)
+{
+  const MetaEdge *a_edge_rect = (gconstpointer) a;
+  const MetaEdge *b_edge_rect = (gconstpointer) b;
+
+  int a_compare, b_compare;
+
+  a_compare = a_edge_rect->side_type;
+  b_compare = b_edge_rect->side_type;
+
+  if (a_compare == b_compare)
+    {
+      if (a_edge_rect->side_type == META_DIRECTION_LEFT ||
+          a_edge_rect->side_type == META_DIRECTION_RIGHT)
+        {
+          a_compare = a_edge_rect->rect.x;
+          b_compare = b_edge_rect->rect.x;
+          if (a_compare == b_compare)
+            {
+              a_compare = a_edge_rect->rect.y;
+              b_compare = b_edge_rect->rect.y;
+            }
+        }
+      else if (a_edge_rect->side_type == META_DIRECTION_TOP ||
+               a_edge_rect->side_type == META_DIRECTION_BOTTOM)
+        {
+          a_compare = a_edge_rect->rect.y;
+          b_compare = b_edge_rect->rect.y;
+          if (a_compare == b_compare)
+            {
+              a_compare = a_edge_rect->rect.x;
+              b_compare = b_edge_rect->rect.x;
+            }
+        }
+      else
+        g_assert ("Some idiot wanted to sort sides of different types.\n");
+    }
+
+  return a_compare - b_compare; /* positive value denotes a > b ... */
+}
+
+/* Determine whether two given edges overlap */
+static gboolean
+edges_overlap (const MetaEdge *edge1,
+               const MetaEdge *edge2)
+{
+  switch (edge1->side_type)
+    {
+    case META_DIRECTION_LEFT:
+    case META_DIRECTION_RIGHT:
+      return (edge2->side_type == META_DIRECTION_LEFT || 
+              edge2->side_type == META_DIRECTION_RIGHT)               &&
+             meta_rectangle_vert_overlap (&edge1->rect, &edge2->rect) &&
+             edge1->rect.x == edge2->rect.x;
+    case META_DIRECTION_TOP:
+    case META_DIRECTION_BOTTOM:
+      return (edge2->side_type == META_DIRECTION_TOP || 
+              edge2->side_type == META_DIRECTION_BOTTOM)               &&
+             meta_rectangle_horiz_overlap (&edge1->rect, &edge2->rect) &&
+             edge1->rect.y == edge2->rect.y;
+    }
+
+  g_assert (0 == 1);
+}
+
+static gboolean
+rectangle_and_edge_intersection (const MetaRectangle *rect,
+                                 const MetaEdge      *edge,
+                                 MetaEdge            *overlap,
+                                 int                 *handle_type)
+{
+  const MetaRectangle *rect2  = &edge->rect;
+  MetaRectangle *result = &overlap->rect;
+  gboolean intersect = TRUE;
+
+  overlap->edge_type = edge->edge_type;
+  overlap->side_type = edge->side_type;
+  
+  result->x = MAX (rect->x, rect2->x);
+  result->y = MAX (rect->y, rect2->y);
+  result->width  = MIN (BOX_RIGHT (*rect),  BOX_RIGHT (*rect2))  - result->x;
+  result->height = MIN (BOX_BOTTOM (*rect), BOX_BOTTOM (*rect2)) - result->y;
+
+  /* Find out if we didn't get any intersections; have to do it this way since
+   * edges have a thickness of 0
+   */
+  if (((edge->side_type == META_DIRECTION_TOP ||
+        edge->side_type == META_DIRECTION_BOTTOM) &&
+       (result->width <= 0 || result->height <  0)) ||
+      ((edge->side_type == META_DIRECTION_LEFT ||
+        edge->side_type == META_DIRECTION_RIGHT) &&
+       (result->width <  0 || result->height <= 0)))
+    {
+      result->width = 0;
+      result->height = 0;
+      intersect = FALSE;
+    }
+  else
+    {
+      /* Need to figure out the handle_type, a somewhat weird quantity:
+       *   0 - overlap is in middle of rect
+       *  -1 - overlap is at the side of rect, and is on the opposite side
+       *       of rect than the edge->side_type side
+       *   1 - overlap is at the side of rect, and the side of rect it is
+       *       on is the edge->side_type side
+       */
+      switch (edge->side_type)
+        {
+        case META_DIRECTION_LEFT:
+          if (result->x == rect->x)
+            *handle_type = 1;
+          else if (result->x == BOX_RIGHT (*rect))
+            *handle_type = -1;
+          else
+            *handle_type = 0;
+          break;
+        case META_DIRECTION_RIGHT:
+          if (result->x == rect->x)
+            *handle_type = -1;
+          else if (result->x == BOX_RIGHT (*rect))
+            *handle_type = 1;
+          else
+            *handle_type = 0;
+          break;
+        case META_DIRECTION_TOP:
+          if (result->y == rect->y)
+            *handle_type = 1;
+          else if (result->y == BOX_BOTTOM (*rect))
+            *handle_type = -1;
+          else
+            *handle_type = 0;
+          break;
+        case META_DIRECTION_BOTTOM:
+          if (result->y == rect->y)
+            *handle_type = -1;
+          else if (result->y == BOX_BOTTOM (*rect))
+            *handle_type = 1;
+          else
+            *handle_type = 0;
+          break;
+        }
+    }
+  return intersect;
+}
+
+/* Add all edges of the given rect to cur_edges and return the result.  If
+ * rect_is_internal is false, the side types are switched (LEFT<->RIGHT and
+ * TOP<->BOTTOM).
+ */
+static GList*
+add_edges (GList               *cur_edges, 
+           const MetaRectangle *rect,
+           gboolean             rect_is_internal)
+{
+  MetaEdge *temp_edge;
+  int i;
+
+  for (i=0; i<4; i++)
+    {
+      temp_edge = g_new (MetaEdge, 1);
+      temp_edge->rect = *rect;
+      switch (i)
+        {
+        case 0:
+          temp_edge->side_type = 
+            rect_is_internal ? META_DIRECTION_LEFT : META_DIRECTION_RIGHT;
+          temp_edge->rect.width = 0;
+          break;
+        case 1:
+          temp_edge->side_type = 
+            rect_is_internal ? META_DIRECTION_RIGHT : META_DIRECTION_LEFT;
+          temp_edge->rect.x     += temp_edge->rect.width;
+          temp_edge->rect.width  = 0;
+          break;
+        case 2:
+          temp_edge->side_type = 
+            rect_is_internal ? META_DIRECTION_TOP : META_DIRECTION_BOTTOM;
+          temp_edge->rect.height = 0;
+          break;
+        case 3:
+          temp_edge->side_type = 
+            rect_is_internal ? META_DIRECTION_BOTTOM : META_DIRECTION_TOP;
+          temp_edge->rect.y      += temp_edge->rect.height;
+          temp_edge->rect.height  = 0;
+          break;
+        }
+      temp_edge->edge_type = META_EDGE_ONSCREEN;
+      cur_edges = g_list_prepend (cur_edges, temp_edge);
+    }
+
+  return cur_edges;
+}
+
+/* Remove any part of old_edge that intersects remove and add any resulting
+ * edges to cur_list.  Return cur_list when finished.
+ */
+static GList*
+split_edge (GList *cur_list, 
+            const MetaEdge *old_edge, 
+            const MetaEdge *remove)
+{
+  MetaEdge *temp_edge;
+  switch (old_edge->side_type)
+    {
+    case META_DIRECTION_LEFT:
+    case META_DIRECTION_RIGHT:
+      g_assert (meta_rectangle_vert_overlap (&old_edge->rect, &remove->rect));
+      if (BOX_TOP (old_edge->rect)  < BOX_TOP (remove->rect))
+        {
+          temp_edge = g_new (MetaEdge, 1);
+          *temp_edge = *old_edge;
+          temp_edge->rect.height = BOX_TOP (remove->rect)
+                                 - BOX_TOP (old_edge->rect);
+          cur_list = g_list_prepend (cur_list, temp_edge);
+        }
+      if (BOX_BOTTOM (old_edge->rect) > BOX_BOTTOM (remove->rect))
+        {
+          temp_edge = g_new (MetaEdge, 1);
+          *temp_edge = *old_edge;
+          temp_edge->rect.y      = BOX_BOTTOM (remove->rect);
+          temp_edge->rect.height = BOX_BOTTOM (old_edge->rect)
+                                 - BOX_BOTTOM (remove->rect);
+          cur_list = g_list_prepend (cur_list, temp_edge);
+        }
+      break;
+    case META_DIRECTION_TOP:
+    case META_DIRECTION_BOTTOM:
+      g_assert (meta_rectangle_horiz_overlap (&old_edge->rect, &remove->rect));
+      if (BOX_LEFT (old_edge->rect)  < BOX_LEFT (remove->rect))
+        {
+          temp_edge = g_new (MetaEdge, 1);
+          *temp_edge = *old_edge;
+          temp_edge->rect.width = BOX_LEFT (remove->rect)
+                                - BOX_LEFT (old_edge->rect);
+          cur_list = g_list_prepend (cur_list, temp_edge);
+        }
+      if (BOX_RIGHT (old_edge->rect) > BOX_RIGHT (remove->rect))
+        {
+          temp_edge = g_new (MetaEdge, 1);
+          *temp_edge = *old_edge;
+          temp_edge->rect.x     = BOX_RIGHT (remove->rect);
+          temp_edge->rect.width = BOX_RIGHT (old_edge->rect)
+                                - BOX_RIGHT (remove->rect);
+          cur_list = g_list_prepend (cur_list, temp_edge);
+        }
+      break;
+    }
+
+  return cur_list;
+}
+
+/* Split up edge and remove preliminary edges from strut_edges depending on
+ * if and how strut and edge intersect.
+ */
+static void
+fix_up_edges (MetaRectangle *strut,        MetaEdge *edge, 
+              GList         **strut_edges, GList    **edge_splits,
+              gboolean      *edge_needs_removal)
+{
+  MetaEdge overlap;
+  int      handle_type;
+
+  if (!rectangle_and_edge_intersection (strut, edge, &overlap, &handle_type))
+    return;
+
+  if (handle_type == 0 || handle_type == 1)
+    {
+      /* Put the result of removing overlap from edge into edge_splits */
+      *edge_splits = split_edge (*edge_splits, edge, &overlap);
+      *edge_needs_removal = TRUE;
+    }
+
+  if (handle_type == -1 || handle_type == 1)
+    {
+      /* Remove the overlap from strut_edges */
+      /* First, loop over the edges of the strut */
+      GList *tmp = *strut_edges;
+      while (tmp)
+        {
+          MetaEdge *cur = tmp->data;
+          /* If this is the edge that overlaps, then we need to split it */
+          if (edges_overlap (cur, &overlap))
+            {
+              /* Split this edge into some new ones */
+              *strut_edges = split_edge (*strut_edges, cur, &overlap);
+
+              /* Delete the old one */
+              GList *delete_me = tmp;
+              tmp = tmp->next;
+              g_free (cur);
+              *strut_edges = g_list_delete_link (*strut_edges, delete_me);
+            }
+          else
+            tmp = tmp->next;
+        }
+    }
+}
+
+/* This function is trying to find all the edges of an onscreen region. */
+GList*
+meta_rectangle_find_onscreen_edges (const MetaRectangle *basic_rect,
+                                    const GSList        *all_struts)
+{
+  GList        *ret;
+  GList        *edge_iter; 
+  const GSList *strut_iter;
+
+  /* The algorithm is basically as follows:
+   *   Make sure the struts are disjoint
+   *   Initialize the edge_set to the edges of basic_rect
+   *   Foreach strut:
+   *     Put together a preliminary new edge from the edges of the strut
+   *     Foreach edge in edge_set:
+   *       - Split the edge if it is partially contained inside the strut
+   *       - If the edge matches an edge of the strut (i.e. a strut just
+   *         against the edge of the screen or a not-next-to-edge-of-screen
+   *         strut adjacent to another), then both the edge from the
+   *         edge_set and the preliminary edge for the strut will need to
+   *         be split
+   *     Add any remaining "preliminary" strut edges to the edge_set
+   */
+
+  /* Make sure the struts are disjoint */
+  if (!struts_are_disjoint (all_struts))
+    {
+      meta_warning ("Struts must be disjoint for %s to work!\n", __FUNCTION__);
+      return NULL;
+    }
+
+  /* Start off the list with the edges of basic_rect */
+  ret = add_edges (NULL, basic_rect, TRUE);
+
+  strut_iter = all_struts;
+  while (strut_iter)
+    {
+      MetaRectangle *strut = (MetaRectangle*) strut_iter->data;
+
+      /* Only look at the onscreen portion of the strut, and get the new
+       * possible edges we may need to add from that.
+       */
+      meta_rectangle_intersect (strut, basic_rect, strut);
+      GList *new_strut_edges = add_edges (NULL, strut, FALSE);
+
+      edge_iter = ret;
+      while (edge_iter)
+        {
+          MetaEdge *cur_edge = edge_iter->data;
+          GList *splits_of_cur_edge = NULL;
+          gboolean edge_needs_removal = FALSE;
+
+          fix_up_edges (strut,            cur_edge, 
+                        &new_strut_edges, &splits_of_cur_edge,
+                        &edge_needs_removal);
+
+          if (edge_needs_removal)
+            {
+              /* Delete the old edge */
+              GList *delete_me = edge_iter;
+              edge_iter = edge_iter->next;
+              g_free (cur_edge);
+              ret = g_list_delete_link (ret, delete_me);
+
+              /* Add the new split parts of the edge */
+              ret = g_list_concat (splits_of_cur_edge, ret);
+            }
+          else
+            {
+              edge_iter = edge_iter->next;
+            }
+
+          /* edge_iter was already advanced above */
+        }
+
+      ret = g_list_concat (new_strut_edges, ret);
+      strut_iter = strut_iter->next;
+    }
+
+  /* Sort the list */
+  ret = g_list_sort (ret, sort_edges);
+
+  return ret;
+}
diff --git a/src/boxes.h b/src/boxes.h
index 1547699c..07d23aed 100644
--- a/src/boxes.h
+++ b/src/boxes.h
@@ -23,6 +23,7 @@
 #define META_BOXES_H
 
 #include <glib.h>
+#include "common.h"
 
 typedef struct _MetaRectangle MetaRectangle;
 
@@ -34,13 +35,10 @@ struct _MetaRectangle
   int height;
 };
 
-typedef enum
-{
-  META_RECTANGLE_LEFT      = 1 << 0,
-  META_RECTANGLE_RIGHT     = 1 << 1,
-  META_RECTANGLE_TOP       = 1 << 2,
-  META_RECTANGLE_BOTTOM    = 1 << 3
-} MetaRectDirection;
+#define BOX_LEFT(box)    ((box).x)                /* Leftmost pixel of rect */
+#define BOX_RIGHT(box)   ((box).x + (box).width)  /* One pixel past right   */
+#define BOX_TOP(box)     ((box).y)                /* Topmost pixel of rect  */
+#define BOX_BOTTOM(box)  ((box).y + (box).height) /* One pixel past bottom  */
 
 typedef enum
 {
@@ -48,15 +46,38 @@ typedef enum
   FIXED_DIRECTION_Y = 1 << 1,
 } FixedDirections;
 
+typedef enum
+{
+  META_EDGE_WINDOW,
+  META_EDGE_XINERAMA,
+  META_EDGE_ONSCREEN
+} MetaEdgeType;
+
+typedef struct _MetaEdge MetaEdge;
+struct _MetaEdge
+{
+  MetaRectangle rect;      /* width or height should be 1 */
+  MetaDirection side_type; /* should only have 1 of the 4 directions set */
+  MetaEdgeType  edge_type;
+};
+
 /* Output functions -- note that the output buffer had better be big enough:
- *   region_to_string: 1 + (26+strlen(separator_string))*g_list_length (region)
  *   rect_to_string:   1 + 24
+ *   region_to_string: 1 + (26+strlen(separator_string))*g_list_length (region)
+ *   edge_to_string:   1 + 24 + 10
+ *   edge_list_to_...: 1 + (36+strlen(sep..._string))*g_list_length (edge_list)
  */
 char* meta_rectangle_to_string        (const MetaRectangle *rect,
                                        char                *output);
 char* meta_rectangle_region_to_string (GList               *region,
                                        const char          *separator_string,
                                        char                *output);
+char* meta_rectangle_edge_to_string   (const MetaEdge      *edge,
+                                       char                *output);
+char* meta_rectangle_edge_list_to_string (
+                                       GList               *edge_list,
+                                       const char          *separator_string,
+                                       char                *output);
 
 /* Basic comparison functions */
 int      meta_rectangle_area            (const MetaRectangle *rect);
@@ -125,10 +146,16 @@ GList*   meta_rectangle_expand_region   (GList               *region,
                                          const int            bottom_expand);
 
 /* Free the list created by
- * meta_rectangle_get_minimal_spanning_set_for_region()
+ *   meta_rectangle_get_minimal_spanning_set_for_region()
+ * or
+ *   meta_rectangle_find_onscreen_edges ()
  */
-void     meta_rectangle_free_spanning_set (GList *spanning_rects);
+void     meta_rectangle_free_list_and_elements (GList *filled_list);
 
+/* could_fit_in_region determines whether one of the spanning_rects is
+ * big enough to contain rect.  contained_in_region checks whether one
+ * actually contains it.
+ */
 gboolean meta_rectangle_could_fit_in_region (
                                          const GList         *spanning_rects,
                                          const MetaRectangle *rect);
@@ -169,4 +196,11 @@ void meta_rectangle_find_linepoint_closest_to_point (double x1,    double y1,
                                                      double px,    double py,
                                                      double *valx, double *valy);
 
+/* Finds all the edges of an onscreen region, returning a GList* of
+ * MetaEdgeRect's.
+ */
+GList*
+meta_rectangle_find_onscreen_edges (const MetaRectangle *basic_rect,
+                                    const GSList        *all_struts);
+
 #endif /* META_BOXES_H */
diff --git a/src/common.h b/src/common.h
index c7c8108e..f5d4065f 100644
--- a/src/common.h
+++ b/src/common.h
@@ -184,6 +184,22 @@ typedef enum
   META_VIRTUAL_MOD5_MASK     = 1 << 14
 } MetaVirtualModifier;
 
+/* Relative directions or sides seem to come up all over the place... */
+/* FIXME: Replace
+ *   place.[ch]:MetaWindowEdgePosition,
+ *   screen.[ch]:MetaScreenDirection,
+ *   workspace.[ch]:MetaMotionDirection,
+ * with the use of MetaDirection.
+ */
+typedef enum
+{
+  META_DIRECTION_LEFT      = 1 << 0,
+  META_DIRECTION_RIGHT     = 1 << 1,
+  META_DIRECTION_TOP       = 1 << 2,
+  META_DIRECTION_BOTTOM    = 1 << 3,
+  META_DIRECTION_UP        = 1 << 2, /* Alternate name for TOP */
+  META_DIRECTION_DOWN      = 1 << 3  /* Alternate name for BOTTOM */
+} MetaDirection;
 
 /* Function a window button can have.  Note, you can't add stuff here
  * without extending the theme format to draw a new function and
@@ -226,7 +242,3 @@ struct _MetaButtonLayout
   (ycoord) <  ((rect).y + (rect).height))
 
 #endif
-
-
-
-
diff --git a/src/testboxes.c b/src/testboxes.c
index d81997d6..be754b1e 100644
--- a/src/testboxes.c
+++ b/src/testboxes.c
@@ -68,6 +68,21 @@ new_meta_rect (int x, int y, int width, int height)
   return temporary;
 }
 
+static MetaEdge*
+new_onscreen_edge (int x, int y, int width, int height, int side_type)
+{
+  MetaEdge* temporary;
+  temporary = g_new (MetaEdge, 1);
+  temporary->rect.x = x;
+  temporary->rect.y = y;
+  temporary->rect.width  = width;
+  temporary->rect.height = height;
+  temporary->side_type = side_type;
+  temporary->edge_type = META_EDGE_ONSCREEN;
+
+  return temporary;
+}
+
 static void
 test_area ()
 {
@@ -205,15 +220,11 @@ free_strut_list (GSList *struts)
   g_slist_free (struts);
 }
 
-static GList*
-get_screen_region (int which)
+static GSList*
+get_strut_list (int which)
 {
-  GList *ret;
   GSList *struts;
-  MetaRectangle basic_rect;
 
-  basic_rect = meta_rect (0, 0, 1600, 1200);
-  ret = NULL;
   struts = NULL;
 
   g_assert (which >=0 && which <= 5);
@@ -247,9 +258,40 @@ get_screen_region (int which)
       break;
     }
 
+  return struts;
+}
+
+static GList*
+get_screen_region (int which)
+{
+  GList *ret;
+  GSList *struts;
+  MetaRectangle basic_rect;
+
+  basic_rect = meta_rect (0, 0, 1600, 1200);
+  ret = NULL;
+
+  struts = get_strut_list (which);
   ret = meta_rectangle_get_minimal_spanning_set_for_region (&basic_rect, struts);
+  free_strut_list (struts);
+
+  return ret;
+}
 
+static GList*
+get_screen_edges (int which)
+{
+  GList *ret;
+  GSList *struts;
+  MetaRectangle basic_rect;
+
+  basic_rect = meta_rect (0, 0, 1600, 1200);
+  ret = NULL;
+
+  struts = get_strut_list (which);
+  ret = meta_rectangle_find_onscreen_edges (&basic_rect, struts);
   free_strut_list (struts);
+
   return ret;
 }
 
@@ -489,8 +531,8 @@ test_regions_okay ()
   tmp = NULL;
   tmp = g_list_prepend (tmp, new_meta_rect (0, 0, 1600, 1200));
   verify_lists_are_equal (region, tmp);
-  meta_rectangle_free_spanning_set (tmp);
-  meta_rectangle_free_spanning_set (region);
+  meta_rectangle_free_list_and_elements (tmp);
+  meta_rectangle_free_list_and_elements (region);
 
   /*************************************************************/  
   /* Make sure test region 1 has the right spanning rectangles */
@@ -500,8 +542,8 @@ test_regions_okay ()
   tmp = g_list_prepend (tmp, new_meta_rect (0, 20,  400, 1180));
   tmp = g_list_prepend (tmp, new_meta_rect (0, 20, 1600, 1140));
   verify_lists_are_equal (region, tmp);
-  meta_rectangle_free_spanning_set (tmp);
-  meta_rectangle_free_spanning_set (region);
+  meta_rectangle_free_list_and_elements (tmp);
+  meta_rectangle_free_list_and_elements (region);
 
   /*************************************************************/
   /* Make sure test region 2 has the right spanning rectangles */
@@ -514,8 +556,8 @@ test_regions_okay ()
   tmp = g_list_prepend (tmp, new_meta_rect (   0,   20,  800, 1130));
   tmp = g_list_prepend (tmp, new_meta_rect (   0,   20, 1600, 1080));
   verify_lists_are_equal (region, tmp);
-  meta_rectangle_free_spanning_set (tmp);
-  meta_rectangle_free_spanning_set (region);
+  meta_rectangle_free_list_and_elements (tmp);
+  meta_rectangle_free_list_and_elements (region);
 
   /*************************************************************/
   /* Make sure test region 3 has the right spanning rectangles */
@@ -540,8 +582,8 @@ test_regions_okay ()
   printf ("%s vs. %s\n", region_list, tmp_list);
 #endif
   verify_lists_are_equal (region, tmp);
-  meta_rectangle_free_spanning_set (tmp);
-  meta_rectangle_free_spanning_set (region);
+  meta_rectangle_free_list_and_elements (tmp);
+  meta_rectangle_free_list_and_elements (region);
 
   /*************************************************************/
   /* Make sure test region 4 has the right spanning rectangles */
@@ -550,8 +592,8 @@ test_regions_okay ()
   tmp = NULL;
   tmp = g_list_prepend (tmp, new_meta_rect ( 800,   20,  800, 1180));
   verify_lists_are_equal (region, tmp);
-  meta_rectangle_free_spanning_set (tmp);
-  meta_rectangle_free_spanning_set (region);
+  meta_rectangle_free_list_and_elements (tmp);
+  meta_rectangle_free_list_and_elements (region);
 
   /*************************************************************/
   /* Make sure test region 5 has the right spanning rectangles */
@@ -581,7 +623,7 @@ test_region_fitting ()
       g_assert (meta_rectangle_contained_in_region (region, &rect) == FALSE ||
                 meta_rectangle_could_fit_in_region (region, &rect) == TRUE);
     }
-  meta_rectangle_free_spanning_set (region);
+  meta_rectangle_free_list_and_elements (region);
 
   /* Do some manual tests too */
   region = get_screen_region (1);
@@ -598,14 +640,14 @@ test_region_fitting ()
   g_assert (meta_rectangle_could_fit_in_region (region, &rect));
   g_assert (!meta_rectangle_contained_in_region (region, &rect));
 
-  meta_rectangle_free_spanning_set (region);
+  meta_rectangle_free_list_and_elements (region);
 
   region = get_screen_region (2);
   rect = meta_rect (1000, 50, 600, 1100);
   g_assert (meta_rectangle_could_fit_in_region (region, &rect));
   g_assert (!meta_rectangle_contained_in_region (region, &rect));
 
-  meta_rectangle_free_spanning_set (region);
+  meta_rectangle_free_list_and_elements (region);
 
   printf ("%s passed.\n", __PRETTY_FUNCTION__);
 }
@@ -635,7 +677,7 @@ test_clamping_to_region ()
       g_assert (meta_rectangle_could_fit_in_region (region, &rect) == TRUE);
       g_assert (rect.x == temp.x && rect.y == temp.y);
     }
-  meta_rectangle_free_spanning_set (region);
+  meta_rectangle_free_list_and_elements (region);
 
   /* Do some manual tests too */
   region = get_screen_region (1);
@@ -697,7 +739,7 @@ test_clamping_to_region ()
                                            &min_size);
   g_assert (rect.width == 100 && rect.height == 999999);
 
-  meta_rectangle_free_spanning_set (region);
+  meta_rectangle_free_list_and_elements (region);
 
   printf ("%s passed.\n", __PRETTY_FUNCTION__);
 }
@@ -743,7 +785,7 @@ test_clipping_to_region ()
           g_assert (meta_rectangle_contained_in_region (region, &rect) == TRUE);
         }
     }
-  meta_rectangle_free_spanning_set (region);
+  meta_rectangle_free_list_and_elements (region);
 
   /* Do some manual tests too */
   region = get_screen_region (2);
@@ -782,7 +824,7 @@ test_clipping_to_region ()
                                  &rect);
   g_assert (meta_rectangle_equal (&rect, &temp));
 
-  meta_rectangle_free_spanning_set (region);
+  meta_rectangle_free_list_and_elements (region);
 
   printf ("%s passed.\n", __PRETTY_FUNCTION__);
 }
@@ -807,7 +849,7 @@ test_shoving_into_region ()
           g_assert (meta_rectangle_contained_in_region (region, &rect));
         }
     }
-  meta_rectangle_free_spanning_set (region);
+  meta_rectangle_free_list_and_elements (region);
 
   /* Do some manual tests too */
   region = get_screen_region (2);
@@ -854,7 +896,174 @@ test_shoving_into_region ()
                                     &rect);
   g_assert (meta_rectangle_equal (&rect, &temp));
 
-  meta_rectangle_free_spanning_set (region);
+  meta_rectangle_free_list_and_elements (region);
+
+  printf ("%s passed.\n", __PRETTY_FUNCTION__);
+}
+
+static void
+verify_edge_lists_are_equal (GList *code, GList *answer)
+{
+  int which = 0;
+
+  while (code && answer)
+    {
+      MetaEdge *a = code->data;
+      MetaEdge *b = answer->data;
+
+      if (!meta_rectangle_equal (&a->rect, &b->rect) ||
+          a->side_type != b->side_type ||
+          a->edge_type != b->edge_type)
+        {
+          g_error ("%dth item in code answer answer lists do not match; "
+                   "code rect: %d,%d + %d,%d; answer rect: %d,%d + %d,%d\n",
+                   which,
+                   a->rect.x, a->rect.y, a->rect.width, a->rect.height,
+                   b->rect.x, b->rect.y, b->rect.width, b->rect.height);
+        }
+
+      code = code->next;
+      answer = answer->next;
+
+      which++;
+    }
+
+  /* Ought to be at the end of both lists; check if we aren't */
+  if (code)
+    {
+      MetaEdge *tmp = code->data;
+      g_error ("code list longer than answer list by %d items; "
+               "first extra item rect: %d,%d +%d,%d\n",
+               g_list_length (code),
+               tmp->rect.x, tmp->rect.y, tmp->rect.width, tmp->rect.height);
+    }
+
+  if (answer)
+    {
+      MetaEdge *tmp = answer->data;
+      g_error ("answer list longer than code list by %d items; "
+               "first extra item rect: %d,%d +%d,%d\n",
+               g_list_length (answer),
+               tmp->rect.x, tmp->rect.y, tmp->rect.width, tmp->rect.height);
+    }
+}
+
+static void
+test_find_onscreen_edges ()
+{
+  GList* edges;
+  GList* tmp;
+
+  int left   = META_DIRECTION_LEFT;
+  int right  = META_DIRECTION_RIGHT;
+  int top    = META_DIRECTION_TOP;
+  int bottom = META_DIRECTION_BOTTOM;
+
+  /*************************************************/  
+  /* Make sure test region 0 has the correct edges */
+  /*************************************************/  
+  edges = get_screen_edges (0);
+  tmp = NULL;
+  tmp = g_list_prepend (tmp, new_onscreen_edge (   0, 1200, 1600, 0, bottom));
+  tmp = g_list_prepend (tmp, new_onscreen_edge (   0,    0, 1600, 0, top));
+  tmp = g_list_prepend (tmp, new_onscreen_edge (1600,    0, 0, 1200, right));
+  tmp = g_list_prepend (tmp, new_onscreen_edge (   0,    0, 0, 1200, left));
+  verify_edge_lists_are_equal (edges, tmp);
+  meta_rectangle_free_list_and_elements (tmp);
+  meta_rectangle_free_list_and_elements (edges);
+
+  /*************************************************/  
+  /* Make sure test region 1 has the correct edges */
+  /*************************************************/  
+  edges = get_screen_edges (1);
+  tmp = NULL;
+  tmp = g_list_prepend (tmp, new_onscreen_edge (   0, 1200,  400, 0, bottom));
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 400, 1160, 1200, 0, bottom));
+  tmp = g_list_prepend (tmp, new_onscreen_edge (   0,   20, 1600, 0, top));
+  tmp = g_list_prepend (tmp, new_onscreen_edge (1600,   20, 0, 1140, right));
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 400, 1160, 0,   40, right));
+  tmp = g_list_prepend (tmp, new_onscreen_edge (   0,   20, 0, 1180, left));
+  verify_edge_lists_are_equal (edges, tmp);
+  meta_rectangle_free_list_and_elements (tmp);
+  meta_rectangle_free_list_and_elements (edges);
+
+  /*************************************************/  
+  /* Make sure test region 2 has the correct edges */
+  /*************************************************/  
+  edges = get_screen_edges (2);
+  tmp = NULL;
+  tmp = g_list_prepend (tmp, new_onscreen_edge (1200, 1200,  400, 0, bottom));
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 450, 1200,  350, 0, bottom));
+  tmp = g_list_prepend (tmp, new_onscreen_edge (   0, 1200,  300, 0, bottom));
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 300, 1150,  150, 0, bottom));
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 800, 1100,  400, 0, bottom));
+  tmp = g_list_prepend (tmp, new_onscreen_edge (   0,   20, 1600, 0, top));
+  tmp = g_list_prepend (tmp, new_onscreen_edge (1600,   20, 0, 1180, right));
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 800, 1100, 0,  100, right));
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 300, 1150, 0,   50, right));
+  tmp = g_list_prepend (tmp, new_onscreen_edge (1200, 1100, 0,  100, left));
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 450, 1150, 0,   50, left));
+  tmp = g_list_prepend (tmp, new_onscreen_edge (   0,   20, 0, 1180, left));
+  verify_edge_lists_are_equal (edges, tmp);
+  meta_rectangle_free_list_and_elements (tmp);
+  meta_rectangle_free_list_and_elements (edges);
+
+  /*************************************************/  
+  /* Make sure test region 3 has the correct edges */
+  /*************************************************/  
+  edges = get_screen_edges (3);
+  tmp = NULL;
+  tmp = g_list_prepend (tmp, new_onscreen_edge (1200, 1200,  400, 0, bottom));
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 380, 1200,  420, 0, bottom));
+  tmp = g_list_prepend (tmp, new_onscreen_edge (   0, 1200,  300, 0, bottom));
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 300, 1150,   80, 0, bottom));
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 800, 1100,  400, 0, bottom));
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 700,  525, 200,  0, bottom));
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 700,  675, 200,  0, top));
+  tmp = g_list_prepend (tmp, new_onscreen_edge (   0,   20, 1600, 0, top));
+  tmp = g_list_prepend (tmp, new_onscreen_edge (1600,   20, 0, 1180, right));
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 800, 1100, 0,  100, right));
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 700,  525, 0,  150, right));
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 300, 1150, 0,   50, right));
+  tmp = g_list_prepend (tmp, new_onscreen_edge (1200, 1100, 0,  100, left));
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 900,  525, 0,  150, left));
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 380, 1150, 0,   50, left));
+  tmp = g_list_prepend (tmp, new_onscreen_edge (   0,   20, 0, 1180, left));
+
+#if 0
+  #define FUDGE 50
+  char big_buffer1[1 + (16+FUDGE)*38], big_buffer2[1 + 16*38];
+  meta_rectangle_edge_list_to_string (edges, "\n ", big_buffer1);
+  meta_rectangle_edge_list_to_string (tmp,   "\n ", big_buffer2);
+  printf("Real edge list:\n %s\nComparison edges list:\n %s\n", 
+         big_buffer1, big_buffer2);
+#endif
+
+  verify_edge_lists_are_equal (edges, tmp);
+  meta_rectangle_free_list_and_elements (tmp);
+  meta_rectangle_free_list_and_elements (edges);
+
+  /*************************************************/  
+  /* Make sure test region 4 has the correct edges */
+  /*************************************************/  
+  edges = get_screen_edges (4);
+  tmp = NULL;
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 800, 1200, 800,  0, bottom));
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 800,   20, 800,  0, top));
+  tmp = g_list_prepend (tmp, new_onscreen_edge (1600,   20, 0, 1180, right));
+  tmp = g_list_prepend (tmp, new_onscreen_edge ( 800,   20, 0, 1180, left));
+  verify_edge_lists_are_equal (edges, tmp);
+  meta_rectangle_free_list_and_elements (tmp);
+  meta_rectangle_free_list_and_elements (edges);
+
+  /*************************************************/  
+  /* Make sure test region 5 has the correct edges */
+  /*************************************************/  
+  edges = get_screen_edges (5);
+  tmp = NULL;
+  verify_edge_lists_are_equal (edges, tmp);
+  meta_rectangle_free_list_and_elements (tmp);
+  meta_rectangle_free_list_and_elements (edges);
 
   printf ("%s passed.\n", __PRETTY_FUNCTION__);
 }
@@ -1029,6 +1238,9 @@ main()
   test_clipping_to_region ();
   test_shoving_into_region ();
 
+  /* And now the functions dealing with edges more than boxes */
+  test_find_onscreen_edges ();
+
   /* And now the misfit functions that don't quite fit in anywhere else... */
   test_gravity_resize ();
   test_find_closest_point_to_line ();
diff --git a/src/workspace.c b/src/workspace.c
index c47ec219..6a9c40d4 100644
--- a/src/workspace.c
+++ b/src/workspace.c
@@ -113,9 +113,9 @@ meta_workspace_free (MetaWorkspace *workspace)
   g_slist_free (workspace->all_struts);
 
   for (i = 0; i < screen->n_xinerama_infos; i++)
-    meta_rectangle_free_spanning_set (workspace->xinerama_region[i]);
+    meta_rectangle_free_list_and_elements (workspace->xinerama_region[i]);
   g_free (workspace->xinerama_region);
-  meta_rectangle_free_spanning_set (workspace->screen_region);
+  meta_rectangle_free_list_and_elements (workspace->screen_region);
 
   g_free (workspace);
 
@@ -452,9 +452,9 @@ meta_workspace_invalidate_work_area (MetaWorkspace *workspace)
   workspace->all_struts = NULL;
 
   for (i = 0; i < workspace->screen->n_xinerama_infos; i++)
-    meta_rectangle_free_spanning_set (workspace->xinerama_region[i]);
+    meta_rectangle_free_list_and_elements (workspace->xinerama_region[i]);
   g_free (workspace->xinerama_region);
-  meta_rectangle_free_spanning_set (workspace->screen_region);
+  meta_rectangle_free_list_and_elements (workspace->screen_region);
   workspace->xinerama_region = NULL;
   workspace->screen_region = NULL;