diff --git a/Makefile.am b/Makefile.am
index e2430e0..4ae7c84 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -252,6 +252,8 @@ openbox_openbox_SOURCES = \
openbox/mwm.h \
openbox/openbox.c \
openbox/openbox.h \
+ openbox/overlap.c \
+ openbox/overlap.h \
openbox/ping.c \
openbox/ping.h \
openbox/place.c \
diff --git a/data/rc.xsd b/data/rc.xsd
index 95a6de5..8b4be27 100644
--- a/data/rc.xsd
+++ b/data/rc.xsd
@@ -470,6 +470,7 @@
+
diff --git a/openbox/config.c b/openbox/config.c
index 503f028..cb43255 100644
--- a/openbox/config.c
+++ b/openbox/config.c
@@ -28,6 +28,7 @@
#include "parser/parse.h"
#include "openbox.h"
#include "gettext.h"
+#include "place.h"
gboolean config_focus_new;
gboolean config_focus_follow;
@@ -522,9 +523,12 @@ static void parse_placement(ObParseInst *i, xmlDocPtr doc, xmlNodePtr node,
node = node->children;
- if ((n = parse_find_node("policy", node)))
+ if ((n = parse_find_node("policy", node))) {
if (parse_contains("UnderMouse", doc, n))
config_place_policy = OB_PLACE_POLICY_MOUSE;
+ else if (parse_contains("LeastOverlap", doc, n))
+ config_place_policy = OB_PLACE_POLICY_LEASTOVERLAP;
+ }
if ((n = parse_find_node("center", node)))
config_place_center = parse_bool(doc, n);
if ((n = parse_find_node("monitor", node))) {
diff --git a/openbox/geom.h b/openbox/geom.h
index 6a1725e..e04fe8e 100644
--- a/openbox/geom.h
+++ b/openbox/geom.h
@@ -101,6 +101,10 @@ typedef struct _Rect {
(r).height = MIN((a).y + (a).height - 1, \
(b).y + (b).height - 1) - (r).y + 1)
+/* Returns the 2-dimensional area of Rect r */
+#define RECT_AREA(r) \
+ (((r).width) * ((r).height))
+
typedef struct _Strut {
int left;
int top;
diff --git a/openbox/overlap.c b/openbox/overlap.c
new file mode 100644
index 0000000..687a741
--- /dev/null
+++ b/openbox/overlap.c
@@ -0,0 +1,119 @@
+#include "config.h"
+#include "geom.h"
+#include "overlap.h"
+
+#include
+
+static int compare_ints(const void* a, const void* b)
+{
+ const int* ia = (const int*)a;
+ const int* ib = (const int*)b;
+ return *ia - *ib;
+}
+
+void overlap_make_grid(int num_rects, Rect* rects, int* x_edges, int* y_edges)
+{
+ int i;
+ for (i = 0; i < num_rects; ++i) {
+ int j0 = i * 2;
+ int j1 = j0 + 1;
+ x_edges[j0] = rects[i].x;
+ x_edges[j1] = rects[i].x + rects[i].width;
+ y_edges[j0] = rects[i].y;
+ y_edges[j1] = rects[i].y + rects[i].height;
+ }
+ qsort(x_edges, 2*num_rects, sizeof(int), compare_ints);
+ qsort(y_edges, 2*num_rects, sizeof(int), compare_ints);
+}
+
+static int rect_total_overlap(Rect* rect, Rect* rects, int num_rects)
+{
+ int overlap = 0;
+ int i;
+ for (i = 0; i < num_rects; ++i) {
+ if (!RECT_INTERSECTS_RECT(*rect, rects[i]))
+ continue;
+ Rect rtemp;
+ RECT_SET_INTERSECTION(rtemp, *rect, rects[i]);
+ overlap += RECT_AREA(rtemp);
+ }
+ return overlap;
+}
+
+/* Given a list of Rect RECTS, a Point PT and a Size size, determine the
+ * direction from PT which results in the least total overlap with RECTS
+ * if a rectangle is placed in that direction. Return the top/left
+ * Point of such rectangle and the resulting overlap amount. Only
+ * consider placements within BOUNDS. */
+
+#define NUM_DIRECTIONS 4
+
+static void
+find_least_overlap_direction(Rect* rects, int num_rects, Point* pt, Size* size,
+ Rect* bounds, Point* top_left, int* overlap)
+{
+ static Size directions[NUM_DIRECTIONS] = {
+ {0, 0}, {0, -1}, {-1, 0}, {-1, -1}
+ };
+ *overlap = G_MAXINT;
+ int i;
+ for (i = 0; i < NUM_DIRECTIONS; ++i) {
+ Point best_point = {
+ .x = pt->x + (size->width * directions[i].width),
+ .y = pt->y + (size->height * directions[i].height)
+ };
+ Rect r;
+ RECT_SET_POINT(r, best_point.x, best_point.y);
+ RECT_SET_SIZE(r, size->width, size->height);
+ if (!RECT_CONTAINS_RECT(*bounds, r))
+ continue;
+ int this_overlap = rect_total_overlap(&r, rects, num_rects);
+ if (this_overlap < *overlap) {
+ *overlap = this_overlap;
+ *top_left = best_point;
+ }
+ if (*overlap == 0)
+ break;
+ }
+}
+
+/* Choose the placement on a grid with least overlap */
+
+void
+overlap_find_least_placement(Rect* rects, int num_rects,
+ Size* size, Rect* bounds,
+ int* xs, int num_xs, int* ys, int num_ys,
+ Point* top_left)
+{
+ top_left->x = top_left->y = 0;
+ int overlap = G_MAXINT;
+ int last_x = G_MAXINT;
+ int i;
+ for (i = 0; i < num_xs; ++i) {
+ if (xs[i] == last_x)
+ continue;
+ last_x = xs[i];
+ int last_y = G_MAXINT;
+ int j;
+ for (j = 0; j < num_ys; ++j) {
+ if (ys[j] == last_y)
+ continue;
+ last_y = ys[j];
+ int this_overlap;
+ Point grid_point = {.x = xs[i], .y = ys[j]};
+ Point best_point;
+ find_least_overlap_direction(rects, num_rects, &grid_point,
+ size, bounds, &best_point,
+ &this_overlap);
+ if (this_overlap < overlap) {
+ overlap = this_overlap;
+ *top_left = best_point;
+ }
+ if (overlap == 0)
+ break;
+ }
+ if (overlap == 0)
+ break;
+ }
+}
+
diff --git a/openbox/overlap.h b/openbox/overlap.h
new file mode 100644
index 0000000..b2ccfd1
--- /dev/null
+++ b/openbox/overlap.h
@@ -0,0 +1,9 @@
+#include "geom.h"
+
+void overlap_make_grid(int num_rects, Rect* rects, int* x_edges, int* y_edges);
+
+void
+overlap_find_least_placement(Rect* rects, int num_rects,
+ Size* size, Rect* bounds,
+ int* xs, int num_xs, int* ys, int num_ys,
+ Point* top_left);
diff --git a/openbox/place.c b/openbox/place.c
index d1d0481..e89cb6a 100644
--- a/openbox/place.c
+++ b/openbox/place.c
@@ -25,6 +25,7 @@
#include "config.h"
#include "dock.h"
#include "debug.h"
+#include "overlap.h"
extern ObDock *dock;
@@ -468,6 +469,72 @@ static gboolean place_transient_splash(ObClient *client, gint *x, gint *y)
return FALSE;
}
+static gboolean place_least_overlap(ObClient *c, gint *x, gint *y)
+{
+ /* assemble the list of "interesting" windows to calculate overlap against */
+ GSList* interesting_clients = NULL;
+ int num_interesting = 0;
+
+ /* if we're "showing desktop", ignore all existing windows */
+ if (!screen_showing_desktop) {
+ GList* it;
+ for (it = client_list; it != NULL; it = g_list_next(it)) {
+ ObClient* maybe_client = (ObClient*) it->data;
+ if (maybe_client == c)
+ continue;
+ if (maybe_client->iconic)
+ continue;
+ if (c->desktop != DESKTOP_ALL) {
+ if (maybe_client->desktop != c->desktop &&
+ maybe_client->desktop != DESKTOP_ALL) continue;
+ } else {
+ if (maybe_client->desktop != screen_desktop &&
+ maybe_client->desktop != DESKTOP_ALL) continue;
+ }
+ if (maybe_client->type == OB_CLIENT_TYPE_SPLASH ||
+ maybe_client->type == OB_CLIENT_TYPE_DESKTOP) continue;
+ /* it is interesting, so add it */
+ interesting_clients = g_slist_prepend(interesting_clients, maybe_client);
+ num_interesting += 1;
+ }
+ }
+ /* allocate arrays for the grid and overlap rectangles
+ * reserve an extra slot for the monitor rectangle */
+ Rect overlap_rects[num_interesting + 1];
+ GSList* it;
+ int i = 0;
+ for (it = interesting_clients; it != NULL; it = g_slist_next(it)) {
+ ObClient* interesting_client = (ObClient*) it->data;
+ overlap_rects[i] = interesting_client->frame->area;
+ i += 1;
+ }
+ g_slist_free(interesting_clients);
+
+ /* add the monitor */
+ Rect **areas = pick_head(c);
+ Rect* bounds = &overlap_rects[num_interesting];
+ *bounds = *areas[0];
+ for (i = 0; i < screen_num_monitors; ++i)
+ g_free(areas[i]);
+ g_free(areas);
+
+ /* calculate grid */
+ int num_edges = 2 * (num_interesting + 1);
+ int x_edges[num_edges];
+ int y_edges[num_edges];
+ overlap_make_grid(num_interesting + 1, overlap_rects, x_edges, y_edges);
+ /* do it */
+ Point top_left;
+ Size size;
+ SIZE_SET(size, c->frame->area.width, c->frame->area.height);
+ overlap_find_least_placement(overlap_rects, num_interesting, &size, bounds,
+ x_edges, num_edges, y_edges, num_edges,
+ &top_left);
+ *x = top_left.x;
+ *y = top_left.y;
+ return TRUE;
+}
+
/* Return TRUE if we want client.c to enforce on-screen-keeping */
gboolean place_client(ObClient *client, gint *x, gint *y,
ObAppSettings *settings)
@@ -488,7 +555,10 @@ gboolean place_client(ObClient *client, gint *x, gint *y,
(userplaced = place_per_app_setting(client, x, y, settings)) ||
(config_place_policy == OB_PLACE_POLICY_MOUSE &&
place_under_mouse(client, x, y)) ||
- place_nooverlap(client, x, y) ||
+ (config_place_policy == OB_PLACE_POLICY_SMART &&
+ place_nooverlap(client, x, y)) ||
+ (config_place_policy == OB_PLACE_POLICY_LEASTOVERLAP &&
+ place_least_overlap(client, x, y)) ||
place_random(client, x, y);
g_assert(ret);
diff --git a/openbox/place.h b/openbox/place.h
index 6a9add4..1c4b338 100644
--- a/openbox/place.h
+++ b/openbox/place.h
@@ -28,7 +28,8 @@ struct _ObAppSettings;
typedef enum
{
OB_PLACE_POLICY_SMART,
- OB_PLACE_POLICY_MOUSE
+ OB_PLACE_POLICY_MOUSE,
+ OB_PLACE_POLICY_LEASTOVERLAP,
} ObPlacePolicy;
typedef enum