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
   (+0 other overloads)
Math.Min(val1: float, val2: float) : float
   (+0 other overloads)
Math.Min(val1: float32, val2: float32) : float32
   (+0 other overloads)
Math.Min(val1: uint64, val2: uint64) : uint64
   (+0 other overloads)
Math.Min(val1: int64, val2: int64) : int64
   (+0 other overloads)
Math.Min(val1: uint32, val2: uint32) : uint32
   (+0 other overloads)
Math.Min(val1: int, val2: int) : int
   (+0 other overloads)
Math.Min(val1: uint16, val2: uint16) : uint16
   (+0 other overloads)
Math.Min(val1: int16, val2: int16) : int16
   (+0 other overloads)
Math.Min(val1: byte, val2: byte) : byte
   (+0 other overloads)
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 Head : '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

Full name: Microsoft.FSharp.Collections.List.head
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
Raw view New version

More information

Link:http://fssnip.net/1y
Posted:8 years ago
Author:Martin Szarski
Tags: computational geometry , geometry , spatial