Created
January 16, 2014 09:33
-
-
Save LukaHorvat/8452156 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment