fork(3) download
copy 
  1. """
  2.   Compute nearest pair of points using two algorithms
  3.  
  4.   First algorithm is 'brute force' comparison of every possible pair.
  5.   Second, 'divide and conquer', is based on:
  6.     www.cs.iupui.edu/~xkzou/teaching/CS580/Divide-and-conquer-closestPair.ppt 
  7. """
  8.  
  9. from random import randint, randrange
  10. from operator import itemgetter, attrgetter
  11.  
  12. infinity = float('inf')
  13.  
  14. # Note the use of complex numbers to represent 2D points making distance == abs(P1-P2)
  15.  
  16. def bruteForceClosestPair(point):
  17.     numPoints = len(point)
  18.  
  19.  
  20.     if numPoints < 2:
  21.         return infinity, (None, None)
  22.     return min( ((abs(point[i] - point[j]), (point[i], point[j]))
  23.                  for i in range(numPoints-1)
  24.                  for j in range(i+1,numPoints)),
  25.                 key=itemgetter(0))
  26.  
  27. def closestPair(point):
  28.     xP = sorted(point, key= attrgetter('real'))
  29.     yP = sorted(point, key= attrgetter('imag'))
  30.     return _closestPair(xP, yP)
  31.  
  32. def _closestPair(xP, yP):
  33.     numPoints = len(xP)
  34.     if numPoints <= 3:
  35.         return bruteForceClosestPair(xP)
  36.     Pl = xP[:numPoints/2]
  37.     Pr = xP[numPoints/2:]
  38.     Yl, Yr = [], []
  39.     xDivider = Pl[-1].real
  40.     for p in yP:
  41.         if p.real <= xDivider:
  42.             Yl.append(p)
  43.         else:
  44.             Yr.append(p)
  45.     dl, pairl = _closestPair(Pl, Yl)
  46.     dr, pairr = _closestPair(Pr, Yr)
  47.     dm, pairm = (dl, pairl) if dl < dr else (dr, pairr)
  48.     # Points within dm of xDivider sorted by Y coord
  49.     closeY = [p for p in yP  if abs(p.real - xDivider) < dm]
  50.     numCloseY = len(closeY)
  51.     if numCloseY > 1:
  52.         # There is a proof that you only need compare a max of 7 next points
  53.         closestY = min( ((abs(closeY[i] - closeY[j]), (closeY[i], closeY[j]))
  54.                          for i in range(numCloseY-1)
  55.                          for j in range(i+1,min(i+8, numCloseY))),
  56.                         key=itemgetter(0))
  57.         return (dm, pairm) if dm <= closestY[0] else closestY
  58.     else:
  59.         return dm, pairm
  60.  
  61. def times():
  62.     ''' Time the different functions
  63.     '''
  64.     import timeit
  65.  
  66.     functions = [bruteForceClosestPair, closestPair]
  67.     for f in functions:
  68.         print 'Time for', f.__name__, timeit.Timer(
  69.             '%s(pointList)' % f.__name__,
  70.             'from closestpair import %s, pointList' % f.__name__).timeit(number=1)
  71.  
  72.  
  73.  
  74. pointList = [randint(0,1000)+1j*randint(0,1000) for i in range(2000)]
  75.  
  76. if __name__ == '__main__':
  77.     pointList = [(5+9j), (9+3j), (2+0j), (8+4j), (7+4j), (9+10j), (1+9j), (8+2j), 10j, (9+6j)]
  78.     print pointList
  79.     print '  bruteForceClosestPair:', bruteForceClosestPair(pointList)
  80.     print '            closestPair:', closestPair(pointList)
  81.     for i in range(3):
  82.         pointList = [randrange(11)+1j*randrange(11) for i in range(10)]
  83.         print '\n', pointList 
  84.         print ' bruteForceClosestPair:', bruteForceClosestPair(pointList)
  85.         print '           closestPair:', closestPair(pointList)
  86.     print '\n'
  87.     times()
  88.     times()
  89.     times()
  90.  
  91. #testPl = [(5+9j), (9+3j), (2+0j), (8+4j), (7+4j), (9+10j), (1+9j), (8+2j), 10j, (9+6j)]
  92. #print(closestPair(testPl))
  93.  
  94.  
Runtime error #stdin #stdout #stderr 0.03s 10464KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
[(5+9j), (9+3j), (2+0j), (8+4j), (7+4j), (9+10j), (1+9j), (8+2j), 10j, (9+6j)]
  bruteForceClosestPair: (1.0, ((8+4j), (7+4j)))
            closestPair: (1.0, ((8+4j), (7+4j)))

[(7+7j), (7+1j), 2j, (7+0j), (2+3j), (2+3j), (10+3j), (3+8j), (9+5j), (3+2j)]
 bruteForceClosestPair: (0.0, ((2+3j), (2+3j)))
           closestPair: (0.0, ((2+3j), (2+3j)))

[(6+0j), (1+4j), (8+8j), (7+2j), (6+9j), (7+8j), (4+10j), 1j, (8+1j), (1+2j)]
 bruteForceClosestPair: (1.0, ((8+8j), (7+8j)))
           closestPair: (1.0, ((7+8j), (8+8j)))

[(6+1j), (9+9j), (9+5j), 10j, (6+1j), (2+8j), (2+10j), 9j, 7j, (3+8j)]
 bruteForceClosestPair: (0.0, ((6+1j), (6+1j)))
           closestPair: (0.0, ((6+1j), (6+1j)))


Time for bruteForceClosestPair
stderr
copy 
Traceback (most recent call last):
  File "prog.py", line 87, in <module>
  File "prog.py", line 70, in times
  File "/usr/lib/python2.7/timeit.py", line 195, in timeit
    timing = self.inner(it, self.timer)
  File "<timeit-src>", line 3, in inner
ImportError: No module named closestpair
https://ideone.com/1u27f9
Closest pair
language:
Python (cpython 2.7.16)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!