daily pastebin goal
56%
SHARE
TWEET

Untitled

a guest Dec 7th, 2017 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import random
  2. import sys
  3. import matplotlib.pyplot as plt
  4. from matplotlib.image import BboxImage
  5. from matplotlib.transforms import Bbox, TransformedBbox
  6. import numpy as np
  7. import time
  8.  
  9. CLOCKWISE = -1
  10. COLLINEAR = 0
  11. COUNTERCLOCKWISE = +1
  12. eps = sys.float_info.epsilon
  13.  
  14.  
  15. def orientation(a, b):
  16.     x0, y0 = a
  17.     x1, y1 = b
  18.     cross = x0 * y1 - x1 * y0
  19.     if cross > eps:
  20.         return COUNTERCLOCKWISE
  21.     elif cross < -eps:
  22.         return CLOCKWISE
  23.     else:
  24.         return COLLINEAR
  25.  
  26.  
  27. def same_halfplane(a, b):
  28.     x0, y0 = a
  29.     x1, y1 = b
  30.     dot = x0 * x1 + y0 * y1
  31.     if dot >= eps:
  32.         return True
  33.     elif dot < eps:
  34.         return False
  35.  
  36.  
  37. def jarvis(points):
  38.     points = points[:]
  39.     r0 = min(points)
  40.     hull = [r0]
  41.     r, u = r0, None
  42.     remainingPoints = [x for x in points if x not in hull]
  43.     while u != r0 and remainingPoints:
  44.         u = random.choice(remainingPoints)
  45.         for t in points:
  46.             a = (u[0] - r[0], u[1] - r[1])
  47.             b = (t[0] - u[0], t[1] - u[1])
  48.             if (t != u and
  49.                 (orientation(a, b) == CLOCKWISE or
  50.                  (orientation(a, b) == COLLINEAR and
  51.                   same_halfplane(a, b)))):
  52.                 u = t
  53.         r = u
  54.         points.remove(r)
  55.         hull.append(r)
  56.         try:
  57.             remainingPoints.remove(r)
  58.         except ValueError:
  59.             # ValueError: list.remove(x): x not in list
  60.             pass
  61.     return hull
  62.  
  63. #if __name__ == '__main__':
  64.  
  65. X = random.sample(range(100), 30)
  66. Y = random.sample(range(100), 30)
  67.  
  68. points = list(zip(X, Y))
  69. print(points)
  70. hull = jarvis(points)
  71. px, py = zip(*points)
  72. hx, hy = zip(*hull)
  73.  
  74. plt.plot(hx, hy, 'g-', markersize=10)
  75. plt.plot(px,py, 'p')
  76.  
  77.  
  78. plt.show()
RAW Paste Data
Top