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#.

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

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