# F# rectangle packing algorithm

I would appreciate it if someone experienced in F# and/or functional programming to look over my code. This is practically the first thing I wrote in the language so I'm sure it's filled with non-idiomatic stuff and unoptimized code.

I'm not interested in implementing a more efficient algorithm. Just implementing this one more efficiently.

If it makes it easier to follow my code the procedure is simple. A "spot" is rectangle on the screen. It has X, Y, Width and Height. It represents a place where you can place a rectangle that's smaller or equal to the spot.

Take a list of rectangles (mutable). Make a list one one possible spot where the first rectangle can fit. It's at (0, 0) with the size (max, max).

Then for every rectangle find the best spot where it can fit and where the maximum value out of his up most Y coordinate and right most X coordinate is minimal. In essence, if we had only that rectangle placed and we wanted to close it in a square that started at (0, 0), find the position where that square would have the lowest area and side's length.

We add two new possible spots. One on the top left corner of the placed rectangle, one at the bottom right. We also go through all other spots we didn't take and cut them if they intersect with our rectangle so when we test new rectangles later we don't get an intersection (due to the rectangle not fitting because we cut the width and height of the spot).

Currently, I have the same thing written in C# and it's a bit faster when I benchmark it. I'm not sure if this can be improved. Buiding it in release mode actually made it slower though that might just be me messing something up.

Anyways, here's the monstrosity:

type IRectangle =
abstract member X : double with get, set
abstract member Y : double with get, set
abstract member Width : double
abstract member Height : double
abstract member Id : int

type internal Spot(x: double, y: double, width: double, height: double) =
member this.x = x
member this.y = y
member this.width = width
member this.height = height

member this.cut = fun (rect: IRectangle) ->
let intervalIntersect : double -> double -> double -> double -> bool =
fun start1 end1 start2 end2 -> min (end1 - start2) (end2 - start1) > 0.0;

let horizontalIntersect = intervalIntersect x (x + width) rect.X (rect.X + rect.Width)
let verticalIntersect   = intervalIntersect y (y + height) rect.Y (rect.Y + rect.Height)

if (horizontalIntersect && rect.Y >= y) then
Spot(x, y, width, min (rect.Y - y) height)
elif (verticalIntersect && rect.X >= x) then
Spot(x, y, min (rect.X - x) width, height)
else this

module Packer =
let private initialSpots: Spot list = [Spot(0.0, 0.0, System.Double.MaxValue, System.Double.MaxValue)]

let private bestSpot (rect: IRectangle) (spots: Spot list) =
spots
|> Seq.filter (fun spot -> spot.width >= rect.Width && spot.height >= rect.Height)
|> Seq.sortBy (fun spot -> max (spot.x + rect.Width) (spot.y + rect.Height))

let private putRectangle (rect: IRectangle) (spots: Spot list): Spot list =
let best = bestSpot rect spots
rect.X <- best.x
rect.Y <- best.y
let right = Spot(best.x + rect.Width, best.y, best.width - rect.Width, best.height)
let top = Spot(best.x, best.y + rect.Height, best.width, best.height - rect.Height)
spots
|> Seq.filter (fun spot -> spot <> best)
|> Seq.map (fun spot -> spot.cut rect)
|> Seq.append [right; top]
|> List.ofSeq

let rec private putRectangles (rectangles: IRectangle list) (spots: Spot list) =
match rectangles, spots with
| [], _ -> ()
| rect::rest, _ -> putRectangles rest (putRectangle rect spots)

let packRectangles (rectangles: IRectangle list) =
let ordered = Seq.sortBy (fun (rect: IRectangle) -> -(rect.Width * rect.Height)) rectangles
putRectangles (List.ofSeq ordered) initialSpots
List.ofSeq ordered


The interface is there because I need to interop with C#.

• Others have answered this well enough, but one other little improvement: Seq.sortBy + Seq.head can be replaced with Seq.maxBy. – Daniel Jan 16 '14 at 15:38

Your code is nice, there is no immediate horribleness, so my post will be nitpicking.

In terms of personal style, I would remove all private/internal modifiers, this is really for interop with the legacy language C# :)

I think your interval function is experiencing some repetition in terms of the expression used, but I don't have time to work out a reduction at the moment.

Second, lets remove this type annotation, it is unnecessary as F# can trivially work out the type based on the expression.

let initialSpots: Spot list = [Spot(0.0, 0.0, System.Double.MaxValue, System.Double.MaxValue)]


to

let initialSpots = [Spot(0.0, 0.0, System.Double.MaxValue, System.Double.MaxValue)]


Next, the optimiser may get rid of it, but you may be able to refactor this:

spots
|> Seq.filter (fun spot -> spot <> best)
|> Seq.map (fun spot -> spot.cut rect)
|> Seq.append [right; top]
|> List.ofSeq


To this (you may need to tweak ordering of yield):

Edit (thanks, I messed something up, I blame the weather)

[ yield! [right;top]
for spot in spots do
if spot <> best then
yield spot.cut rect ]


Edit2: Removed complexity statement. This will mean that you don't loop over the 'spots' data at worst twice.

Also the following:

let packRectangles (rectangles: IRectangle list) =
let ordered = Seq.sortBy (fun (rect: IRectangle) -> -(rect.Width * rect.Height)) rectangles
putRectangles (List.ofSeq ordered) initialSpots
List.ofSeq ordered


Could be changed to:

let packRectangles (rectangles: IRectangle list) =
let ordered = List.sortBy (fun (rect: IRectangle) -> -(rect.Width * rect.Height)) rectangles
putRectangles ordered initialSpots
ordered

• 1. How does your if get rid of O(n) filter? The if is also O(n). 2. I think that right and top should be appended only once at the end of the whole result, not after each spot, like your code does. – svick Jan 16 '14 at 16:17
• He probably meant that there are two O(n) operations there (the filter and the map). Also, I'm not sure how scoping works in F# but I'm guessing that indent before right and top are a mistake. – Darwin Jan 16 '14 at 17:38
• @svick i removed the o(n), I wrongly assumed that since both map and filter iterate over the sequence twice, that they will at worst case cause 1 unnecessary iteration. – DavidK Jan 16 '14 at 22:16
• out of curiosity i ghetto bench-marked it: codepad.org/KcqQN5tl – DavidK Jan 16 '14 at 22:45
• @DavidK Ah, indentation in query expressions can have such a big impact? I didn't know that. – svick Jan 17 '14 at 0:20

    let intervalIntersect : double -> double -> double -> double -> bool =
fun start1 end1 start2 end2 -> min (end1 - start2) (end2 - start1) > 0.0;


could be

let intervalIntersect  = fun start1 end1 start2 end2 -> min (end1 - start2) (end2 - start1) > 0.0;


There are many places where you have unnecersary types

Also, it is more idiomatic in F# to use float rather than double (although they are exactly the same)

Some of the helper functions could also be moved outside where they are called - i.e.

member this.cut = fun (rect: IRectangle) ->
let intervalIntersect : double -> double -> double -> double -> bool =
fun start1 end1 start2 end2 -> min (end1 - start2) (end2 - start1) > 0.0;

let horizontalIntersect = intervalIntersect x (x + width) rect.X (rect.X + rect.Width)
let verticalIntersect   = intervalIntersect y (y + height) rect.Y (rect.Y + rect.Height)

if (horizontalIntersect && rect.Y >= y) then
Spot(x, y, width, min (rect.Y - y) height)
elif (verticalIntersect && rect.X >= x) then
Spot(x, y, min (rect.X - x) width, height)
else this


becomes

let intervalIntersect  = fun start1 end1 start2 end2 -> min (end1 - start2) (end2 - start1) > 0.0;
let horizontalIntersect = intervalIntersect x (x + width) rect.X (rect.X + rect.Width)
let verticalIntersect   = intervalIntersect y (y + height) rect.Y (rect.Y + rect.Height)
member this.cut = fun (rect: IRectangle) ->
if (horizontalIntersect && rect.Y >= y) then
Spot(x, y, width, min (rect.Y - y) height)
elif (verticalIntersect && rect.X >= x) then
Spot(x, y, min (rect.X - x) width, height)
else this

• Why is moving the functions outside better here? Because they sound like they could be used elsewhere too? – svick Jan 16 '14 at 16:23