28 people like it.

# Closest Pair of Points

Closest Pair of points problem in the planar case.

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: ``` ``````open System 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 ``````
namespace System
val dist : x1:float * y1:float -> x2:float * y2:float -> float

Full name: Script.dist
val x1 : float
val y1 : float
val x2 : float
val y2 : float
type Math =
static val PI : float
static val E : float
static member Abs : value:sbyte -> sbyte + 6 overloads
static member Acos : d:float -> float
static member Asin : d:float -> float
static member Atan : d:float -> float
static member Atan2 : y:float * x:float -> float
static member BigMul : a:int * b:int -> int64
static member Ceiling : d:decimal -> decimal + 1 overload
static member Cos : d:float -> float
...

Full name: System.Math
Math.Sqrt(d: float) : float
val closestBf : points:seq<float * float> -> (float * float) * (float * float)

Full name: Script.closestBf
val points : seq<float * float>
val n : int
module Seq

from Microsoft.FSharp.Collections
val length : source:seq<'T> -> int

Full name: Microsoft.FSharp.Collections.Seq.length
Multiple items
val list : (float * float) list

--------------------
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
val toList : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.Seq.toList
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
val i : int
val j : int
val minBy : projection:('T -> 'U) -> source:seq<'T> -> 'T (requires comparison)

Full name: Microsoft.FSharp.Collections.Seq.minBy
val a : float * float
val b : float * float
val closestInternal : points:seq<float * float> -> (float * float) * (float * float)

Full name: Script.closestInternal
val sorted : seq<float * float>
val sortBy : projection:('T -> 'Key) -> source:seq<'T> -> seq<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Seq.sortBy
val x : float
val y : float
val left : seq<float * float>
val take : count:int -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.take
val right : seq<float * float>
val skip : count:int -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.skip
val lMin : (float * float) * (float * float)
val rMin : (float * float) * (float * float)
val lDist : float
val rDist : float
val minDist : float
Math.Min(val1: decimal, val2: decimal) : decimal
Math.Min(val1: float, val2: float) : float
Math.Min(val1: float32, val2: float32) : float32
Math.Min(val1: uint64, val2: uint64) : uint64
Math.Min(val1: int64, val2: int64) : int64
Math.Min(val1: uint32, val2: uint32) : uint32
Math.Min(val1: int, val2: int) : int
Math.Min(val1: uint16, val2: uint16) : uint16
Math.Min(val1: int16, val2: int16) : int16
Math.Min(val1: byte, val2: byte) : byte
val dividingX : float
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list -> 'T list
static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val rev : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.rev
val head : list:'T list -> 'T

val fst : tuple:('T1 * 'T2) -> 'T1

Full name: Microsoft.FSharp.Core.Operators.fst
val closePoints : seq<float * float>
val takeWhile : predicate:('T -> bool) -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.takeWhile
val pairs : ((float * float) * (float * float)) list
val skipWhile : predicate:('T -> bool) -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.skipWhile
val collect : mapping:('T -> #seq<'U>) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.collect
val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map
val append : list1:'T list -> list2:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.append
val sortBy : projection:('T -> 'Key) -> list:'T list -> 'T list (requires comparison)

Full name: Microsoft.FSharp.Collections.List.sortBy