WinWrangler and Non-Euclidian Geometry
Monday, September 28th, 2009- In which our hero gets to dust of his dormant math geek genes.
Not so long ago Alessio Bolognino approached me with a patch adding a preliminary spatial window switching to WinWrangler, like Thomas blogged about a while ago in the Metacity blog. Before we move on let me quickly clarify that by “spatial window switching” I mean that you switch windows not by focus-order, but by selecting neighbouring windows in the directions up, down, left, or right. This makes good sense in a tiled window setup (like WinWrangler provides for any EWMH compliant WM).
The problems start to arise when you begin thinking about just how to select the expected neighbour window. The problem is easily solved if the windows are tiled in a perfect grid. Here the first problem lies – even though WinWrangler has manually constructed the window grid it is not guaranteed to be perfectly aligned. A skew grid can happen if the WM respects the size increment step hints from the apps. Concretely; Gnome Terminal likes to increment its size in steps corresponding to the current character size. Metacity respects these hints – Compiz doesn’t.
The initial approach used edge-detection of the windows, which led to some unexpected behavior in the skew grid case, as well as relying on some very strict logic to select the neighbour window. Strict logic maps surprisingly bad to human perception – surprisingly, yes; you think it maps bad, but in fact it maps really bad. 
I tried porting the window selection to something which was based on the windows’ centers of gravity instead of edge detection. This worked a lot better, but now I turned my testing towards a normal non-tiled session. Consider the setup below:
Window 1 has focus and I hit Left
Undoubtedly this is very subjective, but I would expect window 2 to get the focus. But as you can tell the red X (center of gravity) in 1 is closer to the X in 3 than it is to the X in 2. Meaning that my algorithm would select window 3 as the neighbour. Bummer.
While walking the dog I was thinking about hideously complicated algorithms to always “do what I think”. It was then I had one of those EUREKA moments. Just change the geometry!
This needs some explanation. You see I am really a Math major in Topology. I think that normal flat Euclidian geometry is for sissies. When measuring distances in a flat plane the distance between points (x1, y1) and (x2, y2) is found as we all learn in kindergarten:
Distance between two points in Euclidian geometry
But what if the points do not lie in a flat plane? Maybe we stretch the plane like a rubber membrane so the points lie on a curved surface:
Windows' centers of gravity on a curved surface
In this case the distance down to point 3 might actually be longer because the plane has been stretched. On such a plane differences in the Y-axis will yield a relatively bigger distance than it would in Euclidian space. The distance formular could now look like:
Non-Euclidian distance function, strecthing the plane in the Y-axis
As it turns out this actually selects the expected neighbour – “expected” for my deranged mind at least 
Needless to say we need to stretch the plane in the X-axis when we want to select windows up or down from the current active one. This is left as an exercise for the eager reader.
I really like this solution. It was a very simple code change to get it working and I got to go all nostalgic on my Topology past You can try it out from WinWrangler trunk (bzr branch lp:winwrangler) – it requires GtkHotkey 0.2.* it will not compile with GtkHotkey from trunk. You trigger the switching with the hotkey <Control><Super>Up|Down|Left|Right.
Happy window switching!
