Created
December 30, 2010 08:56
-
-
Save mszarski/759610 to your computer and use it in GitHub Desktop.
Closest Pair of Points solution in F#
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
let dist (x1,y1) (x2,y2) = | |
Math.Sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)) | |
let closestBf points = | |
let n = Seq.length points | |
let list = points |> Seq.toList | |
seq { for i in 0..n-2 do | |
for j in i+1..n-1 do | |
yield list.[i], list.[j] } | |
|> Seq.minBy (fun (a, b) -> dist a b) | |
let rec closestInternal points = | |
match points with | |
| _ when points |> Seq.length < 4 -> closestBf points | |
| _ -> | |
//partition points about a vertical line | |
let sorted = points |> Seq.sortBy(fun (x,y) -> x) | |
let left = sorted |> Seq.take((points |> Seq.length)/2) | |
let right = sorted |> Seq.skip((points |> Seq.length)/2) | |
//recurse each side of the vertical line | |
let lMin = closestInternal left | |
let rMin = closestInternal right | |
//find minimum distance between closest pairs on each side of the line | |
let lDist = | |
match lMin with | |
| (a,b) -> dist a b | |
let rDist = | |
match rMin with | |
| (a,b) -> dist a b | |
let minDist = Math.Min(lDist,rDist) | |
let dividingX = left |> Seq.toList |> List.rev |> List.head |> fst | |
//find close points on the right to the dividing line | |
let closePoints = | |
right | |
|> Seq.takeWhile(fun (x,y) -> x - dividingX < minDist) | |
|> Seq.sortBy(fun (x,y) -> y) | |
//take the close points and merge them with the close points to the dividing line on the left hand side | |
let pairs = | |
left | |
|> Seq.skipWhile(fun (x,y) -> dividingX - x > minDist) | |
|> Seq.collect(fun (x,y) -> | |
closePoints | |
|> Seq.skipWhile(fun (x1,y1) -> y1 < y - minDist) | |
|> Seq.takeWhile(fun (x2,y2) -> y2 < y + minDist) | |
|> Seq.map(fun a -> ((x,y),a))) | |
|> Seq.toList | |
//return the closest pair of points from the three groups | |
pairs |> List.append [lMin;rMin] |> List.sortBy(fun (a,b) -> dist a b) |> List.head |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment