## Closest Pair, Part 1

### February 3, 2015

Today’s exercise comes from the field of computational geometry; given a set of points in two-dimensional space, find the pair with the smallest distance between them. The simple solution uses brute force to calculate the distance between all pairs, taking time O(n2).

Your task is to write a program that calculates the closest pair of points. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 11 Responses to “Closest Pair, Part 1”

1. matthew said

https://github.com/matthewarcus/misc/blob/master/closest.cpp

Divide and conquer, splitting region alternately horizontally and vertically (not sure if that’s really a benefit over always splitting the same way, but it’s more fun).

2. ```use strict;
use warnings;

sub closest {
my @m;
foreach my \$i (0..(@_-1)) {
foreach my \$j (0..(\$i-1)) {
my \$d = (\$_[\$i]-\$_[\$j])**2 + (\$_[\$i]-\$_[\$j])**2;
@m = (\$d,\$i,\$j) unless @m && \$m < \$d;
}
}
return @m;
}

my @p = map { [rand,rand] } 1..100; # Generate a random list of co-ordinates..
my (\$d2,\$p1,\$p2) = closest( @p );    # Get details
printf "(%f,%f) - (%f,%f) - %f\n", @{\$p[\$p1]},@{\$p[\$p2]}, sqrt \$d2; # Render them!

```
3. jeff said

my attempt in python:

```import random
import math

def closest(amt, pts):

dlist = []
for i in range(amt - 1):
pt = pts.pop(0)
x = pt
y = pt

for q in range(len(pts)):
xlen = x - pts[q]
ylen = y - pts[q]
distance = math.sqrt((xlen ** 2) + (ylen ** 2))
dlist.append([distance, i + 1, q + 2 + i])

for i, d in enumerate(dlist):
print "Point {} to {} = {}".format(d, d, d)

dlist.sort()

msg = "\nClosest points are {} and {} \nDistance = {}"
print msg.format(dlist, dlist, dlist)

def pointmaker(amt):

pts = []

for i in range(amt):
x = round(random.uniform(0, 100), 2)
y = round(random.uniform(0, 100), 2)

point = (x, y)
pts.append(point)

for i, pt in enumerate(pts):
print "Point {} - {}".format(i + 1, pt)
print""
closest(amt, pts)

pointmaker(8)
```

>>>
Point 1 – (3.44, 55.26)
Point 2 – (1.13, 95.38)
Point 3 – (96.25, 6.12)
Point 4 – (51.36, 25.47)
Point 5 – (98.23, 12.24)
Point 6 – (63.23, 13.53)
Point 7 – (9.95, 20.72)
Point 8 – (21.43, 99.51)

Point 1 to 2 = 40.1864467203
Point 1 to 3 = 105.016359202
Point 1 to 4 = 56.4249102791
Point 1 to 5 = 104.095458595
Point 1 to 6 = 72.9125297874
Point 1 to 7 = 35.1481393533
Point 1 to 8 = 47.7671707347
Point 2 to 3 = 130.442178761
Point 2 to 4 = 86.0840345244
Point 2 to 5 = 127.830628568
Point 2 to 6 = 102.741581164
Point 2 to 7 = 75.1791726477
Point 2 to 8 = 20.7158610731
Point 3 to 4 = 48.8828661189
Point 3 to 5 = 6.43232461867
Point 3 to 6 = 33.8412248596
Point 3 to 7 = 87.5262817672
Point 3 to 8 = 119.665051289
Point 4 to 5 = 48.7014352971
Point 4 to 6 = 16.8362852197
Point 4 to 7 = 41.6815378795
Point 4 to 8 = 79.8606692935
Point 5 to 6 = 35.0237647891
Point 5 to 7 = 88.6863506973
Point 5 to 8 = 116.250990964
Point 6 to 7 = 53.7629472778
Point 6 to 8 = 95.6023033195
Point 7 to 8 = 79.6219473512

Closest points are 3 and 5
Distance = 6.43232461867
>>>

4. Mike said

Brute force version in Python:

```def closest_pair(points):
"""returns the distance between a closest pair of points and
a pair of such points.
"""

min_dd = float("+inf")
min_pair = None

for p, q in combinations(points, 2):
dd = (q - p)**2 + (q - p)**2
if dd < min_dd:
min_dd = dd
min_pairs= (p, q)

return sqrt(min_dd), min_pair
```

A modified version that returns a list of all pairs that have the minimum distance.

```def all_closest_pairs(points):
"""returns the distance between the closest pair of points, and
a list of such point pairs.
"""

min_dd = float("+inf")
min_pairs = []

for p, q in combinations(points, 2):
dd = (q - p)**2 + (q - p)**2
if dd < min_dd:
min_dd = dd
min_pairs = [(p, q)]

elif dd == min_dd:
min_pairs.append((p, q))

return sqrt(min_dd), min_pairs
```
5. ```import math
def closestPoints(n):
#sort the points based on x coordinate.
#compare distances between consecutive points.
#sort points based on y coordinate.
#compare distances between consecutive points.
#take the smallest of the two.
factor = 1.618
step = int(len(n)/factor)
while step > 0:
for i in range(0,len(n)-step):
j = i
while j+step < len(n) and n[j+step] < n[j]:
n[j+step],n[j],n[j+step],n[j] = (n[j],
n[j+step],n[j],n[j+step])
j+= step
step = int(step/factor)
minx = 10**100
for i in range(0,len(n)-1):
if math.sqrt((n[i]-n[i+1])**2 +(n[i]-n[i+1])**2) < minx:
minx =  math.sqrt((n[i]-n[i+1])**2 +(n[i]-n[i+1])**2)

while step > 0:
for i in range(0,len(n)-step):
j = i
while j+step < len(n) and n[j+step] < n[j]:
n[j+step],n[j],n[j+step],n[j] = (n[j],
n[j+step],n[j],n[j+step])
j+= step
step = int(step/factor)
miny = 10**100
for i in range(0,len(n)-1):
if math.sqrt((n[i]-n[i+1])**2 +(n[i]-n[i+1])**2) < minx:
miny =  math.sqrt((n[i]-n[i+1])**2 +(n[i]-n[i+1])**2)
if minx < miny:
return minx
else:
return miny
```
6. small error, i have < minx in the second run, should be < miny.

7. Paul said

Here the brute force method in Python.

```from math import sqrt
from random import uniform as uni

def closest_pair(points):
d, p, q = min(((p - q) ** 2 + (p - q) ** 2, p, q)
for i, p in enumerate(points)
for q in points[i+1:])
return (sqrt(d), p, q)

def random_points(n, xmin=0, xmax=1, ymin=0, ymax=1):
return [(uni(xmin, xmax), uni(ymin, ymax)) for _ in xrange(n)]

print closest_pair(random_points(1000))
```
8. Ken said

Brute force in C# done very, very, very Sloppy

Cat Class I don’t know why I called it that

class Cat
{
List PointsList = new List();
double Shortest_Distance = 10000;
string ClosestPair;

public void CreatePoints()
{
int i = 0;

try
{
string Input;
do
{

if (Input != “End”)
{
string[] NewPointData = Input.Split(‘,’);
i++;
}
} while (Input != “End”);

Search();
}
catch (Exception ex)
{
Console.WriteLine(ex);
}
}

public void Search()
{
for (int i = 0; i < PointsList.Count; i++)
{
for (int j = 0; j < PointsList.Count; j++)
{
if (i != j)
{
float DeltaX = PointsList[j].Get_X – PointsList[i].Get_X;
float DeltaY = PointsList[j].Get_Y – PointsList[i].Get_Y;

if (DeltaY < 0)
DeltaY *= -1;
if (DeltaX < 0)
DeltaX *= -1;

double TempCsqr = Math.Sqrt((Math.Pow(DeltaX, 2) + Math.Pow(DeltaY, 2)));

Console.WriteLine("Current: " + TempCsqr);

if (TempCsqr < Shortest_Distance)
{
Shortest_Distance = TempCsqr;
ClosestPair = "(" + PointsList[j].Get_String + ")(" + PointsList[i].Get_String + ")";
}
}
Console.WriteLine ("Shortest: " + Shortest_Distance + "\n Closest Pair is" + ClosestPair);
}
}
}
}

Points Class:

namespace Points
{
class Point
{
int X, Y;

public Point(int _X, int _Y)
{
X = _X;
Y = _Y;
}

public int Get_X
{
get { return X; }
}

public int Get_Y
{
get { return Y; }
}

public string Get_String
{
get { return X.ToString() + "," + Y.ToString(); }
}
}
}

INPUT:

1,2
2,1
1,5
1,9
6,5
End

OUTPUT:

Shortest: 10000
Closest Pair is

Current: 1.4142135623731
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)

Current: 3
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)

Current: 7
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)

Current: 5.8309518948453
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)

Current: 1.4142135623731
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)

Current: 4.12310562561766
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)

Current: 8.06225774829855
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)

Current: 5.65685424949238
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)

Current: 3
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)

Current: 4.12310562561766
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)

Current: 4
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)

Current: 5
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)

Current: 7
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)

Current: 8.06225774829855
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)

Current: 4
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)

Current: 6.40312423743285
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)

Current: 5.8309518948453
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)

Current: 5.65685424949238
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)

Current: 5
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)

Current: 6.40312423743285
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)
Shortest: 1.4142135623731
Closest Pair is(2,1)(1,2)

9. Claire said

C++ Version：
#include
#include
#include
#include
using namespace std;

#define ArraySize 4

struct Point
{
Point(double xx, double yy):x(xx),y(yy){}

static double distance(const Point &p1, const Point &p2)
{
double dx = p2.x – p1.x;
double dy = p2.y – p1.y;
return sqrt(dx*dx + dy*dy);
}
double x;
double y;
};

void CalcDistance(vector pointsInput, vector& points, int size)
{
int num = 0;
int min = 0,p1 = 0, p2 = 0;
for( int i = 0; i< size – 1; i++)
{
for ( int j = i+1; j< size; j++)
{
points.push_back(Point::distance(pointsInput[i],pointsInput[j]));
cout<<"point "<<i+1 <<" and Point "<<j+1 <<" = " <<points.at(num) <<endl;
if(num == 0 )
{
min = points.at(0);
}
else if( points.at(num) < min )
{
min = points.at(num);
p1 = i + 1;
p2 = j + 1;
}
num++;
}
}

cout<<"The closest pair are "<<"point "<<p1 <<" and point "<<p2<<endl;
cout<< "The distance is "<< min << endl;
}

int main(int argc, char *argv[])
{
vector myPoints;
int count = 0;
double x;
double y;

while( count > x >> y;
Point point(x,y);
myPoints.push_back(point);
count++;
}

vector output;
CalcDistance(myPoints,output,ArraySize);
return 0;
}

10. Claire said

The comment is really weird, some pieces of my codes are missing. Here is the new code link http://codepad.org/mNXrJb9z