F# rectangle packing algorithm

Question

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))
 |> Seq.head
 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#.

• Daniel: Others have answered this well enough, but one other little improvement: Seq.sortBy + Seq.head can be replaced with Seq.maxBy.

Answer 1

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

• svick: 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.
• Darwin: 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.
• DavidK: @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: out of curiosity i ghetto bench-marked it: codepad.org/KcqQN5tl
• svick: @DavidK Ah, indentation in query expressions can have such a big impact? I didn't know that.

Answer 2

A few comments:

 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

• svick: Why is moving the functions outside better here? Because they sound like they could be used elsewhere too?