close算法python实现
时间: 2023-09-29 16:08:30 浏览: 119
close算法是一种寻找给定点集的凸包的算法,下面是一份Python实现代码:
```python
def orientation(p, q, r):
"""
求向量 pq 与 pr 的叉积
"""
return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
def close(points):
"""
求点集 points 的凸包
"""
# 先按照 x 坐标排序,若 x 坐标相同则按照 y 坐标排序
points = sorted(set(points))
# 求下凸壳
lower = []
for p in points:
while len(lower) >= 2 and orientation(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)
# 求上凸壳
upper = []
for p in reversed(points):
while len(upper) >= 2 and orientation(upper[-2], upper[-1], p) <= 0:
upper.pop()
upper.append(p)
# 合并下凸壳和上凸壳
return lower[:-1] + upper[:-1]
```
该算法的核心思想是通过求向量的叉积来判断三个点的位置关系,从而确定凸包的形状。具体来说,对于三个点 $p,q,r$,若 $\overrightarrow{pq}$ 在 $\overrightarrow{pr}$ 的顺时针方向,则 $r$ 在 $p$ 和 $q$ 的凸包内;反之,若 $\overrightarrow{pq}$ 在 $\overrightarrow{pr}$ 的逆时针方向,则 $r$ 不在凸包内。