user
|  |
| --- |
| 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)
assistant
(formerly Perl 6)

**Translation of**: Perl 5

Using concurrency, the 'simple' routine beats the (supposedly) more efficient one for all but the smallest sets of input.

```
sub MAIN ($N = 5000) {
    my @points = (^$N).map: { [rand × 20 - 10, rand × 20 - 10] }

    my @candidates = @points.sort(*.[0]).rotor( 10 => -2, :partial).race.map: { closest-pair-simple(@$_) }
    say 'simple ' ~ (@candidates.sort: *.[2]).head(1).gist;
    @candidates    = @points.sort(*.[0]).rotor( 10 => -2, :partial).race.map: { closest-pair(@$_)        }
    say 'real '   ~ (@candidates.sort: *.[2]).head(1).gist;
}

sub dist-squared(@a, @b) { (@a[0] - @b[0])² + (@a[1] - @b[1])² }

sub closest-pair-simple(@points is copy) {
    return ∞ if @points < 2;
    my ($a, $b, $d) = |@points[0,1], dist-squared(|@points[0,1]);
    while @points {
        my \p = pop @points;
        for @points -> \l {
            ($a, $b, $d) = p, l, $_ if $_ < $d given dist-squared(p, l);
        }
    }
    $a, $b, $d.sqrt
}

sub closest-pair(@r) {
    closest-pair-real (@r.sort: *.[0]), (@r.sort: *.[1])
}

sub closest-pair-real(@rx, @ry) {
    return closest-pair-simple(@rx) if @rx ≤ 3;

    my \N  = @rx;
    my \midx = ceiling(N/2) - 1;
    my @PL := @rx[     0 ..  midx];
    my @PR := @rx[midx+1 ..^ N   ];
    my \xm  = @rx[midx;0];
    (.[0] ≤ xm ?? my @yR !! my @yL).push: @$_ for @ry;
    my (\al, \bl, \dL) = closest-pair-real(@PL, @yR);
    my (\ar, \br, \dR) = closest-pair-real(@PR, @yL);
    my ($w1, $w2, $closest) = dR < dL ?? (ar, br, dR) !! (al, bl, dL);
    my @yS = @ry.grep: { (xm - .[0]).abs < $closest }

    for 0 ..^ @yS -> \i {
        for i+1 ..^ @yS -> \k {
            next unless @yS[k;1] - @yS[i;1] < $closest;
            ($w1, $w2, $closest) = |@yS[k, i], $_ if $_ < $closest given dist-squared(|@yS[k, i]).sqrt;
        }
    }
    $w1, $w2, $closest
}

```

Output:

```
simple (([-1.1560800527301716 -9.214015073077793] [-1.1570263876019649 -9.213340680530798] 0.0011620477602117762))
  real (([-1.1570263876019649 -9.213340680530798] [-1.1560800527301716 -9.214015073077793] 0.0011620477602117762))
```