

 This page uses content from Wikipedia. The original article was at Closest pair of points problem. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)



Task

Provide a function to find the closest two points among a set of given points in two dimensions,   i.e. to solve the   Closest pair of points problem   in the   planar   case.

The straightforward solution is a   O(n2)   algorithm   (which we can call brute-force algorithm);   the pseudo-code (using indexes) could be simply:

bruteForceClosestPair of P(1), P(2), ... P(N)
if N < 2 then
  return ∞
else
  minDistance ← |P(1) - P(2)|
  minPoints ← { P(1), P(2) }
  foreach i ∈ [1, N-1]
    foreach j ∈ [i+1, N]
      if |P(i) - P(j)| < minDistance then
        minDistance ← |P(i) - P(j)|
        minPoints ← { P(i), P(j) } 
      endif
    endfor
  endfor
  return minDistance, minPoints
 endif

A better algorithm is based on the recursive divide&conquer approach,   as explained also at   Wikipedia's Closest pair of points problem,   which is   O(n log n);   a pseudo-code could be:

closestPair of (xP, yP)
               where xP is P(1) .. P(N) sorted by x coordinate, and
                     yP is P(1) .. P(N) sorted by y coordinate (ascending order)
if N ≤ 3 then
  return closest points of xP using brute-force algorithm
else
  xL ← points of xP from 1 to ⌈N/2⌉
  xR ← points of xP from ⌈N/2⌉+1 to N
  xm ← xP(⌈N/2⌉)x
  yL ← { p ∈ yP : px ≤ xm }
  yR ← { p ∈ yP : px > xm }
  (dL, pairL) ← closestPair of (xL, yL)
  (dR, pairR) ← closestPair of (xR, yR)
  (dmin, pairMin) ← (dR, pairR)
  if dL < dR then
    (dmin, pairMin) ← (dL, pairL)
  endif
  yS ← { p ∈ yP : |xm - px| < dmin }
  nS ← number of points in yS
  (closest, closestPair) ← (dmin, pairMin)
  for i from 1 to nS - 1
    k ← i + 1
    while k ≤ nS and yS(k)y - yS(i)y < dmin
      if |yS(k) - yS(i)| < closest then
        (closest, closestPair) ← (|yS(k) - yS(i)|, {yS(k), yS(i)})
      endif
      k ← k + 1
    endwhile
  endfor
  return closest, closestPair
endif



References and further readings

   Closest pair of points problem
   Closest Pair (McGill)
   Closest Pair (UCSB)
   Closest pair (WUStL)
   Closest pair (IUPUI) 


declare
  fun {Distance X1#Y1 X2#Y2}
     {Sqrt {Pow X2-X1 2.0} + {Pow Y2-Y1 2.0}}
  end
 
  %% brute force
  fun {BFClosestPair Points=P1|P2|_}
     Ps = {List.toTuple unit Points} %% for efficient random access
     N = {Width Ps}
     MinDist = {NewCell {Distance P1 P2}}
     MinPoints = {NewCell P1#P2}
  in
     for I in 1..N-1 do
        for J in I+1..N do
           IJDist = {Distance Ps.I Ps.J}
        in
           if IJDist < @MinDist then
              MinDist := IJDist
              MinPoints := Ps.I#Ps.J
           end
        end
     end
     @MinPoints
  end
 
  %% divide and conquer
  fun {ClosestPair Points}
     case {ClosestPair2
           {Sort Points {LessThanBy X}}
           {Sort Points {LessThanBy Y}}}
     of Distance#Pair then
        Pair
     end
  end
 
  %% XP: points sorted by X, YP: sorted by Y
  %% returns a pair Distance#Pair
  fun {ClosestPair2 XP YP}
     N = {Length XP} = {Length YP}
  in
     if N =< 3 then
        P = {BFClosestPair XP}
     in
        {Distance P.1 P.2}#P
     else
        XL XR
        {List.takeDrop XP (N div 2) ?XL ?XR}
        XM = {Nth XP (N div 2)}.X
        YL YR
        {List.partition YP fun {$ P} P.X =< XM end ?YL ?YR}
        DL#PairL = {ClosestPair2 XL YL}
        DR#PairR = {ClosestPair2 XR YR}
        DMin#PairMin = if DL < DR then DL#PairL else DR#PairR end
        YSList = {Filter YP fun {$ P} {Abs XM-P.X} < DMin end}
        YS = {List.toTuple unit YSList} %% for efficient random access
        NS = {Width YS}
        Closest = {NewCell DMin}
        ClosestPair = {NewCell PairMin}
     in
        for I in 1..NS-1 do
           for K in I+1..NS while:YS.K.Y - YS.I.Y < DMin do
              DistKI = {Distance YS.K YS.I}
           in
              if DistKI < @Closest then
                 Closest := DistKI
                 ClosestPair := YS.K#YS.I
              end
           end
        end
        @Closest#@ClosestPair
     end
  end
 
  %% To access components when points are represented as pairs
  X = 1
  Y = 2
 
  %% returns a less-than predicate that accesses feature F
  fun {LessThanBy F}
     fun {$ A B}
        A.F < B.F
     end
  end
 
  fun {Random Min Max}
     Min +
     {Int.toFloat {OS.rand}} * (Max-Min)
     / {Int.toFloat {OS.randLimits _}}
  end
 
  fun {RandomPoint}
     {Random 0.0 100.0}#{Random 0.0 100.0}
  end
 
  Points = {MakeList 5}
in
  {ForAll Points RandomPoint}
  {Show Points}
  {Show {ClosestPair Points}}