Subject: FVWM: idea for new window placement policy

From: Trent Piepho <[email-masked]>
Date: Tue, 22 Oct 1996 02:06:26 -0700 (PDT)

How about this for a new window placement policy, CleverPlacement?  Currently
we have SmartPlacement, which avoids all overlap and gives up if it can't,
and DumbPlacement (er, RandomPlacement), which sticks the windows semi-randomly
on the screen.  CleverPlacement should be like SmartPlacement, it tries to
avoid overlap.  If it can't avoid it entirely, it tries to minimize it.

If I have two windows, each 100% vertical size and 51% horizontal size, the
the best way to place them is so they fill the whole screen and overlap just
a bit in the middle.

Anyone have an idea on a heuristic to try and find the least overlapping
position?

|Gazing up to the breeze of the heavens \ on a quest, meaning, reason  |
|came to be, how it begun \ all alone in the family of the sun         |
|curiosity teasing everyone \ on our home, third stone from the sun.   |
|Trent Piepho ([email-masked])                   -- Metallica  |
--
Visit the official FVWM web page at <URL:http://www.hpc.uh.edu/fvwm/>.
To unsubscribe from the list, send "unsubscribe fvwm" in the body of a
message to [email-masked].
To report problems, send mail to [email-masked].

---

From: Dan Astoorian <[email-masked]>
Date: Tue, 22 Oct 1996 10:00:42 -0400

>Anyone have an idea on a heuristic to try and find the least overlapping

I was planning to do some work on this, but have just been too busy;
I'll share my thoughts and perhaps someone else will get around to
putting together some code before I do.

Currently, SmartPlacement is implemented something like this:
    Let x, y = 0
    loop
	try to place the window at (x,y)
	if the placement does not result in overlap
	    return (x,y)

	set x to the right margin of the overlapping window
	if x + window width > right side of screen
	    x = 0
	    y = y + 1
	    if y + window height > bottom of screen
		fail

Note that since y is only incremented by 1, it can take thousands of
iterations to conclude that there's no room on the desktop.

A possible optimization: keep a sorted list of the y coordinate of the
bottom edge of each existing window; then instead of adding 1, set y to
the next-higher element of the list.  (Why this algorithm works is left
as an exercise.)

Once this improvement is made, the following enhancement becomes
feasible: each time an (x,y) placement fails, calculate the area of
overlap between that placement and all windows on the screen.  Reject
the placement if this overlap exceeds the smallest found so far.  (In
fact, when traversing the list of windows to calculate the total
overlap, you can stop early once you've found enough overlapping area to
eliminate the placement as a candidate.)

If an overlap of 0 is found during this process, that position is
returned and CleverPlacement works like SmartPlacement.  If it hits the
bottom of the screen before finding such a 'perfect' placement, it uses
the best guess it found.

This method could be made even smarter if it kept a sorted list of the
right edges of each window as well as the bottom edges, and considered
each of those x positions as possible 'secondary' candidates even though
some of them had no chance of being the 'perfect' placement.

Another possible addition to the heuristic: when calculating overlap,
count window title bars and decorations as triple their actual area, in
order to discourage placing windows on top of them.

Thoughts?

--                          People shouldn't think that it's better to have
Dan Astoorian               loved and lost than never loved at all.  It's
http://www.utopia.csas.com  not, it's better to have loved and won.  All
[email-masked]       the other options really suck.    --Dan Redican
--
Visit the official FVWM web page at <URL:http://www.hpc.uh.edu/fvwm/>.
To unsubscribe from the list, send "unsubscribe fvwm" in the body of a
message to [email-masked].
To report problems, send mail to [email-masked].

---

From: Kai Grossjohann <[email-masked]>
Date: 22 Oct 1996 18:53:18 +0200

>>>>> Dan Astoorian writes:

  Dan> Another possible addition to the heuristic: when calculating
  Dan> overlap, count window title bars and decorations as triple
  Dan> their actual area, in order to discourage placing windows on
  Dan> top of them.

  Dan> Thoughts?

Another possible addition to the heuristic: when calculating overlap,
count window title bars and decorations as a third their actual area,
in order to encourage placing windows on top of them.

:-)  Sorry, couldn't resists...

De gustibus non disputandem,
kai
-- 
Life is hard and then you die.
--
Visit the official FVWM web page at <URL:http://www.hpc.uh.edu/fvwm/>.
To unsubscribe from the list, send "unsubscribe fvwm" in the body of a
message to [email-masked].
To report problems, send mail to [email-masked].

---

From: Anthony Martin <[email-masked]>
Date: Tue, 22 Oct 1996 11:04:15 -0700 (PDT)

> >avoid overlap.  If it can't avoid it entirely, it tries to minimize it.

I considered doing this myself when I was fixing up the SmartPlacement
code so that it didn't leave a 1 pixel gap around the windows.

> putting together some code before I do.

I'll do it (tonight?)

> Currently, SmartPlacement is implemented something like this:
...
> the next-higher element of the list.  (Why this algorithm works is left

Done.  I did this when I was fixing the placement code so that it didn't
leave a gap.  But my code, although cleaner than the existing code, was
also larger, and I thought less likely to be accepted.  The existing
SmartPlacement, although crude, is surprisingly compact.

> bottom of the screen before finding such a 'perfect' placement, it uses

This is basically what I had in mind.  I will take a look at it (implement
it?) tonight.

Tony.

---

From: [email-masked] (J.A.vanderMost)
Date: Wed, 23 Oct 1996 10:40:11 +0200 (METDST)

[..SNIP..]
>the next-higher element of the list.  (Why this algorithm works is left

What about shaped windows ? If you treat a shaped window as if it was a
rectangle then your method will work fine. If you want your new window to
use the "transparent" space of the shaped window then this method will
fail.

---------------------              --------------------------------------------
|                   /              |                                          |
| Shaped Window    /               |             Normal window                |
|                 /                |                                          |
|         --------                 |                                          |
|         |  ===================== |                                          |
|          \ |                   | |                                          |
|           \|    Space for      | |                                          |
|           /|    new window     | |                                          |
|          / |                   | |                                          |
|         |  |                   | |                                          |
|         |  |                   | |                                          |
|         |  ===================== |                                          |
|         |                        |                                          |
-----------                        --------------------------------------------

Jeroen van der Most

---

From: Dan Astoorian <[email-masked]>
Date: Wed, 23 Oct 1996 10:07:44 -0400

>use the "transparent" space of the shaped window then this method will

So will the current method.  The existing code determines overlap based
on the rectangular bounds of the windows on the screen and the window
being placed.  There is no case where my optimized method will fail to
place a window where the current code would have placed it anyway. 

Dealing with shaped windows is a *much* harder problem, and it's my
opinion that fvwm shouldn't try to solve it.