RFC: new ExpoLayout Algorithm
Summary
The ExpoLayout Algorithm is an window layout algorithm, used in the Gridview, Overview, and Present Windows effects. The current algorithm sometimes makes inefficient use of screen space, and can generate undesirable window placements [0].
This RFC discusses issues with the current algorithm, proposes criteria for judging good algorithms, and proposes a new algorithm that (try to) satisfy the proposed criteria.
Concrete Proposals

Proposes new layout algorithm. 
Tentative proposal to deprecate some of the old layout algorithms in favor of the new one.
I am happy to focus on the first proposal for now.
Demo
See the code at https://invent.kde.org/fanzhuyifan/expoview.
The screenshots for the following demos are generated by Natural (no fill gap), Natural (fill gap), closest, and new algorithm, in that order.
The current algorithm
Abstractly, the ExpoLayout Algorithm takes as input the geometry of the available region, and the geometries of a list of windows. It positions and scales the windows such that they all fit in the available region without overlapping.
Currently, two different layout modes are supported, LayoutClosest
and LayoutNatural
, implemented by ExpoLayout::calculateWindowTransformationsClosest
and ExpoLayout::calculateWindowTransformationsNatural
, respectively.
In LayoutClosest
the algorithm creates a rectangular grid of slots, and assign windows to those slots.
In LayoutNatural
, the algorithm incrementally adjusts the windows, scaling or moving them, based on nearby available space and overlaps.
Since neither explicitly considers the window sizes, this often leads to suboptimal layouts.
Some concrete examples of problems
For example, see and .
These two are all taken under the LayoutNatural
mode.
The issues are
 The
xclock
windows have drastically different sizes even though they originally have the same size  The screen space use is inefficient  there are large gaps in the image on the right.
What makes a good layout algorithm?
A good layout algorithm should make efficient and aesthetic use of screen space, make incremental and aesthetic adjustments upon creation or deletion of window, and always be fast and robust.
Make efficient and aesthetic use of screen space
 windows should try to use as much use of screen space as possible
 windows should be aligned, when possible
 the size differences between windows shouldn't be too big
Make incremental and aesthetic adjustments upon creation or deletion of window
 Upon incremental changes to the windows (single addition or deletion), (most of the time) the layout shouldn't be completely different
Fast
 The run time needs to be linear (up to logarithm factors) in the number of windows, and it should be at least as fast as the existing algorithm for the user
Robust
 The algorithm must terminate and not crash for input containing all possible sizes, including negative, and extremely large
Algorithm proposal
The outline of the proposed algorithm is
 adjustSizesOfWindows
 findGoodPacking
 refinePacking
The details of those steps are described in the following sections.
The most important part is the second step, findGoodPacking
.
adjustSizesOfWindows
In this step, we
 set minimum size of windows
 set maximum size of windows (no bigger than screen)

optionally adjust sizes of windows such that they don't differ by too much  add margins
findGoodPacking
Changed to the O(n log n)
algorithm in [2].
In this step, we use the NextFit Decreasing Height (NFDH) strip packing algorithm (O(n log n)
) to pack a strip [1, 2].
We use binary search on the logarithm of the strip width to find the strip width such that the aspect ratio of the final packing is closest to the aspect ratio of the available region, within some tolerance.
Input:
windows: sizes of windows
area: size of available area
tol: tolerance
sortedWindows = sort windows by decreasing (height, width, unique id)
targetRatio = area.height / area.width
stripWidthMin = max(width of window for window in sortedWindows)
stripWidthMax = sum(width of window for window in sortedWindows)
height, placementHigh = NFDH(stripWidthMin, sortedWindows)
ratioHigh = height / stripWidthMin
if ratioHigh <= targetRatio:
return stripWidthMin, placementHigh
height, placementLow = NFDH(stripWidthMax, sortedWindows)
ratioLow = height / stripWidthMax
if ratioLow >= targetRatio:
return stripWidthMax, placementLow
bestPlacement = ratioHigh  targetRatio < targetRatio  ratioLow ? placementHigh : placementLow
while (stripWidthMax / stripWidthMin > 1 + tol):
stripWidth = sqrt(stripWidthMin * stripWidthMax)
height, placement = NFDH(stripWidth, sortedWindows)
ratio = height / stripWidth
if ratio > targetRatio:
ratioHigh = ratio
placementHigh = placement
stripWidthMin = stripWidth
else:
ratioLow = ratio
placementLow = placement
stripWidthMax = stripWidth
if (ratioHigh  targetRatio < targetRatio  ratioLow):
return stripWidthMin, placementHigh
else:
return stripWidthMax, placementLow
Since the algorithm performs binary search on the logarithm of the strip width, it needs very few iterations to converge.
refinePacking
In this step, we
 scale the packing to fit the available area
 add even horizontal spacing between windows of the same level
 add even vertical spacing between the levels
 centeralign the windows of the same level
References
 [0] https://bugs.kde.org/show_bug.cgi?id=477833
 [1] https://stackoverflow.com/questions/1213394/whatalgorithmcanbeusedforpackingrectanglesofdifferentsizesintothesm
 [2] https://intranet.csc.liv.ac.uk/~epa/surveyhtml.html
 [3] Hirschberg, Daniel S., and Lawrence L. Larmore. "The least weight subsequence problem." SIAM Journal on Computing 16.4 (1987): 628638.