document.write('
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)
');