Closest-pair problem: Difference between revisions

</lang>

Divide And Conquer:

<lang fsharp>

open System;

open System.Drawing;

open System.Diagnostics;

let GeneratePoints(n : int) =

let rand = new Random()

[1..n] |> List.map(fun(i) -> new PointF(float32(rand.NextDouble()), float32(rand.NextDouble())))

let Length(seg : PointF * PointF) =

let f = fst seg

let t = snd seg

let dx = f.X - t.X

let dy = f.Y - t.Y

Math.Sqrt((dx*dx + dy*dy) |> float)

let Shortest(a : PointF * PointF, b : PointF * PointF) =

if (Length(a) < Length(b)) then

a

else

b

let rec Closest(from : PointF, pts : PointF list) =

Trace.Assert(pts != [])

let toHd = (from, List.head pts)

let tl = List.tail pts

if (tl = []) then

toHd

else

Shortest(toHd, Closest(from, tl))

let rec ClosestBrute(pts : PointF list) =

let hd = List.head pts

let tl = List.tail pts

if (List.length pts = 2) then

(hd, List.head tl)

else

Shortest (Closest(hd, tl), ClosestBrute tl)

let rec ClosestBoundY(from : PointF, maxY : float32, ptsByY : PointF list, count : int) =

let hd = List.head ptsByY

let toHd = (from, hd)

if (count = 1) || (hd.Y >= maxY) then

toHd

else

let tl = List.tail pts

let bestOfRest = ClosestBoundY(from, maxY, tl, count-1)

Shortest(toHd, bestOfRest)

let rec ClosestWithinRange(ptsByY : PointF list, maxDy : float32, count : int) =

Trace.Assert(count >= 2)

let hd = List.head ptsByY

let tl = List.tail ptsByY

if (count = 2) then

(hd, List.head tl)

else

let fromHd = ClosestBoundY(hd, hd.Y + maxDy, tl, count-1)

let fromRest = ClosestWithinRange(tl, maxDy, count-1)

Shortest(fromHd, fromRest)

let rec ShiftToFirst (first : PointF list, second : PointF list, n : int) =

if (n = 0) then

(first, second)

else

let h = List.head second

let newFirst = List.Cons(h, first)

let newSecond = List.tail(second)

ShiftToFirst(newFirst, newSecond, n - 1)

let Halve(pts : PointF list) =

let n = (List.length pts) / 2

ShiftToFirst( [], pts, n)

let rec ClosestPair(pts : PointF list) =

Trace.Assert(List.length pts >= 2)

if (List.length(pts) <= 4) then

ClosestBrute pts

else

let ptsByX = pts |> List.sortBy(fun(p) -> p.X)

let (left, right) = Halve ptsByX

let leftResult = ClosestPair left

let rightResult = ClosestPair right

let bestInHalf = Shortest (leftResult, rightResult)

let bestLength = Length(bestInHalf) |> float32

let divideX = List.head(right).X

let inBand = pts |> List.filter(fun(p) -> Math.Abs(p.X - divideX) < bestLength)

let countInBand = List.length inBand

if countInBand < 2 then

bestInHalf

else

let byY = inBand |> List.sortBy(fun(p) -> p.Y)

let bestCross = ClosestWithinRange(byY, bestLength, countInBand)

Shortest(bestInHalf, bestCross)