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