• From: Soren Sandmann Pedersen <sandmann redhat com>
• To: Elijah Newren <newren gmail com>
• Cc: metacity-devel-list gnome org
• Date: Tue, 15 Nov 2005 13:36:20 -0500

```Elijah Newren wrote:

```
```On 11/15/05, Soren Sandmann Pedersen <sandmann redhat com> wrote:
```
```I am probably missing something, but what about:
```
```
Well, I feel kind of sheepish for not being aware of GdkRegion.  :)

```
```- Generate a GdkRegion "strut_region" of all the struts
- rects = strut_region.get_rectangles();
- for each r in rects:
add r.x and r.x + r.width to list of x coordinates unless they
add r.y and r.y + r.height to list of y coordinates unless they
- for each x in x coordinates
for each y in y coordinates
add (x, y) to list of intersection points
```
```
That's going to generate some weird (x,y) points outside the domain;
is that intentional?

```
Yes, it's intended to generate all points that lie on an horizontal or vertical line of a corner of a strut. The idea is that all 'maximal rectangles' - ie., rectangles that can't be expanded in any direction without hitting a strut - have corners at those points. The key is that the best window position will be somewhere in the best (ie., closest)
```maximal rectangle that will contain the window. The algorithm then is

```
a) find the best rectangle that can contain the window by trying to position each corner of
```   the window on each of the points.

b) fine tune the position of the window within that rectangle.

```
```- for each point in list of intersection points
for each corner of the window
if positioning the window corner at the point doesn't
conflict,
```
```
What do you mean by "conflict"?  !gdk_region_rect_in ?

```
```             then we have found a possible window position
- look at all the generated window positions, and take the one closest
to the desired
position. Then move the corner that was attached to an intersection
point as far
towards the desired position as possible.
```
```
I don't fully understand what you mean here.  From what I think I
understand (correct me if I'm wrong), it looks like you're only
looking at corners of the window matching the (x,y) points of corners
of rectangles from the region and thus it appears that you might move
the window further than needed (you may only need to move it
vertically to get it back in the region, but the window corners may
not vertically align with corners of rectangles of the region).
```
Yeah, that's what the last sentence is supposed to take care of: After one corner of the window is positioned on one of the intersection points, move it towards the desired location
```until gdk_region_rect_in() stops returning RECTANGLE_OUT.

```
```So, it looks possible, but we do already have something that works[1]
and does the same thing (and isn't O(n^2) per meta_window_constrain()
call, not that it's likely to matter).  Maybe transitioning to
GdkRegion later makes sense (perhaps when we become more worried about
shaped windows?).
```
Yeah, working code tends to beat unproven algorithms made up on mailing lists :-)
```

Søren

```