Convex hull

A Convex Hull is a concept in computational geometry (graphics). A convex hull of point set Q is a minimum convex polygon that satisfies points in Q either on the edge of or inside the polygon.

Before formally discussing the convex hull problem, there is an auxiliary concept called “direction”.

The direction of the ordered points

The Orientation of an ordered point in a plane can be three kinds:

  • Rotate CounterClockwise
  • Clockwise Clockwise

  • Collinear Colinear

For some \ (a (x_1, y_1) \], \ (a) (x_2, y_2 \), c (x_3, y_3) $$,

The slope of line AB is zero

$$ \sigma = \frac{y_2 – y_1}{x_2 – x_1} $$

The slope of line segment BC is zero

$$ \tau = \frac{y_3 – y_2}{x_3 – x_2} $$

  • If \(Sigma < \tau\), the direction is counterclockwise (turn left)
  • If \(sigma = \tau\), the direction is collinear
  • If \(sigma > \tau\), the direction is clockwise (turn right)

Therefore, the orientation of the three ordered points depends on the expression.

$$ (y_2 – y_1) \times (x_3 – x_2) – (y_3 – y_2) \times (x_2 – x_1) $$

  • If the expression is negative, the direction is counterclockwise
  • If this expression is 0, the direction is collinear
  • If this expression is positive, the direction is clockwise

Graham Scan

The algorithm can be divided into two main parts:

  1. pretreatment

    1. Find the bottom left point. Make this point p0 as the first element of the output convex hull points[0].
    2. Sort the remaining N – 1 points in the order of polar Angle with P0. If the Angle is the same, only the point farthest from P0 is reserved

  1. Accept or reject the point

    1. Create empty stack S and push the next point on the top of the stack.
    2. Process each remaining points[I] :

    3. Traces the current three points: the next point at the top of the stack, the point at the top of the stack, and points[I], the point currently being analyzed. There are two lines between three points, regarded as two vectors, and the cross product between them is calculated to return the relationship between three points:

      <0, indicating that the third point is left, the second point (top element) is retained, and the third point is added to the stack

      \>0, if the third point is turned to the right, delete the second point (top element) and add the third point to the stack

      =0, indicating that the three points are collinear (>0 can be used)

  

Step 1.1 of the algorithm (finding the bottom-left point) takes O(n) time, and step 1.2 (sorting points) takes O(n * logn) time.

In step 2, each element is pushed and pushed at most once, assuming that the stack operation takes O(1) time, then step 2 takes O(n) time in total. So the overall time complexity is order n logn.

code

Import random import matplotlib.pyplot as PLT import matplotlib.animation as animation import math # (start,end) Return list [(x1,y1)...(xn,yn)]) def sample(n, start=0, end=101): return list(zip([random.randint(start, end) for _ in range(n)], [random.randint(start, End) for _ in range(n)]) "" # Calculate the cross product between two vectors. Returns the relationship between three points: <0, indicates that the third point turns left, retains the second point (stack top element), adds the third point >0, indicates that the third point turns right, deletes the second point (stack top element), adds the third point =0, indicates that the three points are collinear "" Return ((b [1] - [1] a) * (c [0] - [0]) b) - (b (c [1] - [1]) * (b [0] - [0])) behind # respectively calculate n - 1 point and the starting point of the slope, Def compute(next): start = points[0] # compute(next): start = points[0] # compute(next) = points[0] Math.atan2 (start[2] -next [2], start[1] -next [1]) # return Angle # if start[0] == next[0]: # If the x coordinates are the same, Return 99999 slope = (start[1] -next [1])/(start[0] -next [0]) return slope def (start[1] -next [0] For I in range(len(points)) for I in range(len(points)) Elif points[I][0]==Min: if points[I][1]<=points[index][1]: elif points[I][0]==Min: if points[I][1]<=points[index][1]: elif points[I][0]==Min: if points[I][1]<=points[index][1]: Min = points[I][0] = points[0] points[0] = points[index] = temp # Sorted = points[:1] + sorted = points[:1] + sorted = points[:1] + sorted = points[:1] + sorted = points[:1]; The last half is a stack of n-1 points sorted by slope. Note: "+" is concatenation, not addition. # Use lists to simulate a stack. Convex_ull = [] for points: "" # if you can connect to the third vertex clockwise (turn right), delete the top element and add this vertex; Convex_hull [-1] : vertex p: vertex p: vertex p: vertex p: vertex p: vertex p: vertex p: vertex p: vertex p: vertex p: vertex p: vertex p: vertex p: vertex p: vertex p: vertex p: vertex p: vertex p: vertex p: vertex p: vertex p: vertex p: vertex While Len (Convex_Hull) > 1 and CCW (Convex_Hull [-1], Convex_Hull [-1], p) >= 0: Convex_hall.pop () convex_hall.append (p) return convex_hull def show_result(points, results): "" Return: picture """ all_x = [] all_y = [] for item in points: a, b = item all_x.append(a) all_y.append(b) for i in range(len(results)-1): Item_1 =results[I] item_2 =results[I +1] # Item_, oneI = item_1 two_, twoI = item_2 plt.plot([one_, two_], [oneI, twoI]) plt.scatter(all_x, all_y) plt.show() if __name__ == '__main__': # points = [(101, 47), (32, 40), (21, 90), (65, 100), (98, 64), (81, 43), (51, 20), (75, 82), (90, 34), (38, 101)] points = sample (100) hull = Graham_Scan (points) print (hull) # visualization, the correctness of the result is helpful to check hull. Append (hull [0]) # connect the last point and the source point, Show_Result (points, Hull)

Program run result

Order of join points:

[(2, 5), (21, 0), (91, 1), (101, 9), (99, 62), (91, 88), (75, 101), (27, 98), (12, 96), (2, 92), (2, 53)]

Visualization:

https://ysw1912.github.io/pos…


https://en.wikipedia.org/wiki…