Algorithm: Closest Pair Of Points

Data hosted with ♥ by Pastebin.com - Download Raw - See Original

1. #+-------------------------
2. # Author: Nehal J Wani
3. # Date: Aug 20, 2012
4. # Algorithms, Closest Pair
5. #+-------------------------
6.  
7. #Calculate the eucledian distance
8. def eDist(pair):
9.     return (pair[0][0]-pair[1][0])**2+(pair[0][1]-pair[1][1])**2
10.  
11. #Sort input according to x-coordinate and y-coordinate
12. def closestPair(P):
13.     Px=sorted(P,key=lambda x:x[0])
14.     Py=sorted(P,key=lambda y:y[1])
15.     return closestPairRec(Px,Py)
16.  
17. #Applying brute force for less than three points
18. def pairByBruteForce(P):
19.     bestPair=(P[0],P[1])
20.     bestDist=eDist(bestPair)
21.     for i in range(len(P)):
22.         for j in range(i+1,len(P)):
23.             dist=eDist((P[i],P[j]))
24.             if dist<bestDist:
25.                 bestDist=dist
26.                 bestPair=(P[i],P[j])
27.     return bestPair
28.  
29. #Divide & Conquer
30. def closestPairRec(Px,Py):
31.     n=len(Px)
32.  
33.     #Base case
34.     if len(Px)<=3:
35.         return pairByBruteForce(Px)
36.  
37.     #Dividing input into halves
38.     Qx=Px[:n/2]
39.     Qy=Py[:n/2]
40.     Rx=Px[n/2:]
41.     Ry=Py[n/2:]
42.  
43.     #Closest points in left half and right half
44.     (q0,q1)=closestPairRec(Qx,Qy)
45.     (r0,r1)=closestPairRec(Rx,Ry)
46.  
47.     dQ=eDist((q0,q1))
48.     dR=eDist((r0,r1))
49.  
50.     if dQ>dR:
51.         bestPair=(r0,r1)
52.         delta=dR
53.     else:
54.         bestPair=(q0,q1)
55.         delta=dQ
56.  
57.     #Separator line
58.     x_=Qx[-1][0]
59.    
60.     #Split-point 'unlucky' case
61.     S=filter(lambda x: abs(x[0]-x_)<delta,Qx+Rx)
62.     Sy=sorted(S,key=lambda y:y[1])
63.    
64.     if len(Sy)<=7 and len(Sy)>1:
65.         splitPair=pairByBruteForce(Sy)
66.         if eDist(splitPair)<delta:
67.             bestPair=splitPair
68.  
69.     #Find the points with distance < delta
70.     for i in range(len(Sy)-7):
71.         for j in range(i+1,i+8):
72.             dist=eDist((Sy[i],Sy[j]))
73.             if dist<delta:
74.                 delta=dist
75.                 bestPair=(Sy[i],Sy[j])
76.     return bestPair
77.  
78.  
79. P=[(0,0),(7,6),(2,20),(12,5),(16,16),(5,8),(19,7),(14,22),(8,19),(7,29),(10,11),(1,13)]
80. print closestPair(P)