Edited at

Find available space in a crowded interface with the optimal rectangle algorithm

More than 1 year has passed since last update.

A dynamic modern UI may have many elements on the screen at once. In a recent application, we required a route polyline of arbitrary shape to be added to a map view that was covered by various other views/fragments. It was preferable that this route fit in the largest empty space available, which required:


  • computing the screen coordinates of that empty space efficiently

  • scaling the underlying map region so that the route is shown only in that available space

We adopted the Maximal Rectangle algorithm for the first task and provide working Swift and Kotlin versions below, adapted from:

http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529


Procedure

The steps were as follows:

* Build a 2D grid of type Boolean representing the map view; initialize all elements with "zeros"

* For each of the existing UI views/fragments, find those grid elements in which their boundaries lies and set those elements to "true"

* Incorporate some padding to the map edge and UI element edges if necessary.

* Call the "optimal rectangle algorithm" method below to find the optimal contiguous rectangle of "zeros"


"Optimal" Rectangle Algorithm

The implementation below iteratively computes and compares "intermediate" rectangles. The function calcScore(width, height) tests each intermediate "maximal rectangle" - the intermediate rectangle with the highest calcScore will be chosen as the solution to this algorithm.

In the simplest case where we try to find the largest available rectangle, we get the maximal rectangle using

calcScore(width, height) = width x height.

However, this can sometimes provide rectangle sizes or locations that are unfavorable. In our case, we experimented with modified forms of "calcScore" that gave preference to:


  • lower aspect ratios to avoid too narrow rectangles, e.g.:

    calcScore(width, height) = f( min(width, height) / max(width, height) )


  • rectangles closer to the screen center, e.g.:

    calcScore(centerRect, centerScreen) = f( 1 / (1 + pow(centerRect.x - centerScreen.x, 2.0) + pow(centerRect.y - centerScreen.y, 2.0))


  • rectangle whose aspect ratios match the aspect ratio of the new UI element to add. For example, if we add a map route to a map view, we can calculate the aspect ratio of that route using Principal Component Analysis and find a matching optimal rectangle in which to display it.



Note

With a 2D grid with nRows x nColumns, the algorithm has complexity of roughly O(nRows + nColumns). We parametrise the

accuracy/performance of this method with the size of each grid element "pixelSize". Larger "pixelSize" means a quicker algorithm but more wasted space/less accuracy.

For a variety of iOS mobile devices with screen dimensions in the range 400 to 2000, we find "pixelSize" of 20 was a good starting point.


Source code (Swift 3.0)

public val maximalRectangle: rectangleType?

get() {
data class stackType(
var m0: Int,
var w0: Int)

if (this.grid.isEmpty()) {
return null
}
var cache=Array(this.nColumns + 1, { 0 })

fun updateCache(n: Int) {
for (m in 0..this.nColumns - 1) {
if (this.grid[n][m] == true) {
cache[m]+=1
} else {
cache[m]=0
}
}
}

var bestArea: Int=0
var bestL=point(x=0, y=0)
var bestU=point(x=-1, y=-1)

var stack: MutableList<stackType> = mutableListOf()
for (n in 0..(this.nRows - 1)) {
updateCache(n=n)
var width=0
for (m in 0..this.nColumns) {
if (cache[m] > width) {
stack.add(stackType(m0=m, w0=width))
width=cache[m]
}
if (cache[m] < width) {
lateinit var p: stackType
do {
p=stack.last()
val area = calcScore(width=width, height=m - p.m0)
if (area > bestArea) {
bestArea=area
bestL=point(x=p.m0, y=n)
bestU=point(x=m - 1, y=n - width + 1)
}
width=p.w0
} while (cache[m] < width)
width=cache[m]
if (width != 0) {
stack.add(stackType(m0=p.m0, w0=p.w0))
}
}
}
}
if (bestL.x < 0 || bestL.y < 0 || bestU.x < 0 || bestU.y < 0) {
print("error: no maximal rectangle can be found")
return null
}

return rectangleType(
left = (bestL.x * pixelSize,
right = (bestU.x * pixelSize,
bottom = (bestL.y * pixelSize,
top = (bestU.y * pixelSize
)
}


Source code (Kotlin)

public val maximalRectangle: rectangleType?

get() {
if (this.grid.isEmpty()) {
print("error: grid is empty")
return null
}
var cache=Array(this.nColumns + 1, { 0 })

fun updateCache(n: Int) {
for (m in 0..this.nColumns - 1) {
if (this.grid[n][m] == true) {
cache[m]+=1
} else {
cache[m]=0
}
}
}

var bestArea: Int=0
var bestL=point(x=0, y=0)
var bestU=point(x=-1, y=-1)

data class stackType(
var m0: Int,
var w0: Int) {}

var stack: MutableList<stackType> = mutableListOf()
for (n in 0..(this.nRows - 1)) {
updateCache(n=n)
var width=0
for (m in 0..this.nColumns) {
if (cache[m] > width) {
stack.add(stackType(m0=m, w0=width))
width=cache[m]
}
if (cache[m] < width) {
lateinit var p: stackType
do {
p=stack.last()
val area=calcScore(width=width, height=m - p.m0)
if (area > bestArea) {
bestArea=area
bestL=point(x=p.m0, y=n)
bestU=point(x=m - 1, y=n - width + 1)
}
width=p.w0
} while (cache[m] < width)
width=cache[m]
if (width != 0) {
stack.add(stackType(m0=p.m0, w0=p.w0))
}
}
}
}
if (bestL.x < 0 || bestL.y < 0 || bestU.x < 0 || bestU.y < 0) {
print("error: no maximal boxangle can be found")
return null
}

return rectangleType(
left = (bestL.x + 0).toDouble() * pixelSize,
right = (bestU.x - 0).toDouble() * pixelSize,
bottom = (bestL.y - 0).toDouble() * pixelSize,
top = (bestU.y + 0).toDouble() * pixelSize
)
}