Convex hull problem. Given n points on the plane, find a minimum point set such that the convex polygon composed of the point set surrounds all n points. Based on the divide-and-conquer strategy, an algorithm is designed to solve the convex hull problem. Implement the algorithm and test it.
Divide and conquer algorithm idea:
- If the number of points in the point set is less than or equal to 3, you can directly return these points as the convex hull, because the convex hull includes at least 3 points.
- Sort the point set using the leftmost point
P
1
P_1
P1? and the rightmost point
P
n
P_n
The straight line connected by Pn? is divided into two subsets: the upper package and the lower package.
- Get the point farthest from the straight line
P
m
a
x
P_{max}
Pmax?
- draw a straight line
P
1
P
m
a
x
and
P
n
P
m
a
x
P_1 P_{max} and P_n P_{max}
P1?Pmax? and Pn?Pmax?, find the upper envelope for the left and right sides respectively.
- Recursively perform convex hull calculation on the upper hull.
- The same applies to subcontracting
The straight line function formed by two points is:
y
?
y
1
y
2
?
y
1
=
x
?
x
1
x
2
?
x
1
\frac{y-y_1}{y_2-y_1} = \frac{x-x_1}{x_2-x_1}
y2y1?y?y1=x2x1?x?x1
Substituting the distance formula from the point to the straight line, the distance is:
∣
(
x
2
?
x
1
)
y
3
?
(
y
2
?
y
1
)
x
3
?
(
x
2
?
x
1
)
y
1
+
(
y
2
?
y
1
)
x
1
∣
(
x
2
?
x
1
)
2
+
(
y
2
?
y
1
)
2
\frac{|(x_2-x_1)y_3-(y_2-y_1)x_3-(x_2-x_1)y_1 + (y_2-y_1)x_1|}{\sqrt{(x_2-x_1)^2 + (y_2-y_1) ^2}}
(x2x1?)2 + (y2y1?)2
∣
(
x
2
?
x
1
)
y
3
?
(
y
2
?
y
1
)
x
3
?
(
x
2
?
x
1
)
y
1
+
(
y
2
?
y
1
)
x
1
∣
=
∣
x
1
?
y
2
+
x
3
?
y
1
+
x
2
?
y
3
?
x
3
?
y
2
?
x
2
?
y
1
?
x
1
?
y
3
∣
|(x_2-x_1)y_3-(y_2-y_1)x_3-(x_2-x_1)y_1 + (y_2-y_1)x_1| \ =|x1 * y2 + x3 * y1 + x2 * y3 – x3 * y2 – x2 * y1 – x1 * y3 |
∣(x2x1?)y3(y2y1?)x3(x2x1?)y1? + (y2y1?)x1?∣=∣x1?y2 + x3?y1 + x2?y3?x3?y2?x2?y1?x1?y3∣
The maximum is sufficient.
code show as below:
import random
import matplotlib.pyplot as plt
from typing import List
# slot is for reducing memory overhead, lt is for sorting, and iter is for convenience of value acquisition
class point:
__slots__ = ['x', 'y']
def __init__(self, x:float, y:float) -> None:
self.x = x
self.y = y
def __lt__(self, other):
if self.x == other.x:
return self.y < other.y
return self.x < other.x
def __iter__(self):
yield self.x
yield self.y
def cacl_dis(a:Point, b:Point, c:Point) -> float:
x1, y1 = a
x2, y2 = b
x3, y3 = c
return x1 * y2 + x3 * y1 + x2 * y3 - x3 * y2 - x2 * y1 - x1 * y3
def border_point_up(left_point:Point, right_point:Point, lists:List[Point], border_points:List[Point]) -> None:
dis_max = 0
max_point = None
for item in lists:
if item == left_point or item == right_point:
continue
else:
dis = cacl_dis(left_point, right_point, item)
if dis > dis_max:
max_point = item
dis_max = dis
if dis_max != 0:
border_points.append(max_point)
border_point_up(left_point, max_point, lists, border_points)
border_point_up(max_point, right_point, lists, border_points)
def border_point_down(left_point:Point, right_point:Point, lists:List[Point], border_points:List[Point]) -> None:
dis_max = 0
max_point = ()
for item in lists:
if item == left_point or item == right_point:
continue
else:
dis = cacl_dis(left_point, right_point, item)
if dis < dis_max:
max_point = item
dis_max = dis
if dis_max != 0:
border_points.append(max_point)
border_point_down(left_point, max_point, lists, border_points)
border_point_down(max_point, right_point, lists, border_points)
def order_border(lists: List[Point]) -> List[Point]:
lists.sort()
first_x, first_y = lists[0] # The leftmost point
last_x, last_y = lists[-1] # rightmost point
list_border_up = [] # Upper half border
for item in lists:
x, y = item
if y > max(first_y, last_y):
list_border_up.append(item)
if min(first_y, last_y) < y < max(first_y, last_y):
if cacl_dis(lists[0], lists[-1], item) > 0:
list_border_up.append(item)
else:
continue
list_border_down = [_ for _ in lists if _ not in list_border_up] # Lower half border
list_end = list_border_up + list_border_down[::-1] # The final clockwise output boundary point
return list_end
def draw(list_points:List[Point], list_borders:List[Point]) -> None:
list_all_x = []
list_all_y = []
for item in list_points:
a, b = item
list_all_x.append(a)
list_all_y.append(b)
list_borders.append(list_borders[0])
plt.scatter(list_all_x, list_all_y)
for i in range(len(list_borders) - 1):
one_, oneI = list_borders[i]
two_, twoI = list_borders[i + 1]
plt.plot([one_, two_], [oneI, twoI], color='red')
plt.scatter([one_, two_], [oneI, twoI], color='red')
plt.show()
# Generate a random point set
def generate_random_points(n:int, xmin:float, xmax:float, ymin:float, ymax:float)->List[Point]:
return [Point(random.uniform(xmin, xmax), random.uniform(ymin, ymax)) for _ in range(n)]
if __name__ == "__main__":
n=100
x_min, x_max = 0, 100
y_min, y_max = 0, 100
list_points = generate_random_points(n, x_min, x_max, y_min, y_max)
list_points.sort()
border_points = [] # Set of border points
border_point_up(list_points[0], list_points[-1], list_points, border_points) # Upper border point set
border_point_down(list_points[0], list_points[-1], list_points, border_points) # Lower border point set
border_points.append(list_points[0])
border_points.append(list_points[-1])
draw(list_points, order_border(border_points))
Here, 100 points are randomly initialized to test the code, and the results are displayed through matplotlib:
