• API
• FAQ
• Tools
• Archive
daily pastebin goal
38%
SHARE
TWEET

# Untitled

a guest Dec 7th, 2017 61 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top