已知坐标点集合,获取边缘点集合
时间: 2023-12-18 18:48:18 浏览: 145
获取边缘点集合的算法通常被称为“凸包算法”,其目的是找到一个最小的凸多边形,使得包含所有给定的点。常见的凸包算法有 Graham Scan 算法,Jarvis 算法和 QuickHull 算法。
以 Graham Scan 算法为例,其步骤如下:
1. 找到点集中 y 坐标最小的点(如果有多个,选择 x 坐标最小的点),将其标记为 P0。
2. 将所有其他点按照极角从小到大排序,如果极角相同,则按照距离 P0 的距离从小到大排序。
3. 将排序后的点依次加入凸包中,如果加入该点会使凸包非凸,则将该点与凸包上倒数第二个点之间的所有点删除,直到凸包变为凸形。
4. 直到所有点都被加入凸包中,算法结束。
以下是一个 Python 实现的例子:
```python
def graham_scan(points):
# 找到 y 坐标最小的点
p0 = min(points, key=lambda p: (p[1], p[0]))
# 按照极角排序
points = sorted(points, key=lambda p: math.atan2(p[1]-p0[1], p[0]-p0[0]))
# 加入凸包
hull = [p0, points[0]]
for p in points[1:]:
while len(hull) >= 2 and not is_convex(hull[-2], hull[-1], p):
hull.pop()
hull.append(p)
return hull
# 判断三点是否构成凸形
def is_convex(p1, p2, p3):
return (p2[1]-p1[1])*(p3[0]-p2[0]) > (p3[1]-p2[1])*(p2[0]-p1[0])
```
其中,points 是点集合,每个点是一个二元组 (x, y)。函数 graham_scan 返回的是凸包点集合,按照顺序连接即可得到凸包。
阅读全文