如果凸包是完全矩形(Python 3)，如何得到构成凸包的所有点？
如果凸包是完全矩形(Python 3)，如何得到构成凸包的所有点？
提问于 2018-06-16 21:58:23
打开图像以查看以下代码的结果
import numpy as np
from scipy.spatial import ConvexHull
import matplotlib.pyplot as plt
points = np.array([[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[2,4],[3,1],[3,2],[3,3],[3,4],[4,1],[4,2],[4,3],[4,4]])
hull = ConvexHull(points)
plt.plot(points[:,0], points[:,1], 'o')
for simplex in hull.simplices:
plt.plot(points[simplex, 0], points[simplex, 1], 'k-')
plt.plot(points[simplex,0], points[simplex,1], 'ro', alpha=.25, markersize=20)我想得到凸包上的点的坐标索引(黑色的点+线上的点)，.I选择矩形只是为了得到一个极端的情况。
hull.points只能给出标记为红色的点(仅矩形的角点)。
回答 1
Stack Overflow用户
发布于 2018-06-18 04:42:13
如果您确定凸包是一个边与x轴和y轴对齐的完美矩形，则查找所有边界点的索引很简单。要做到这一点，根本不需要计算凸包。这一描述符合您的示例。下面是一些代码，可以在这种情况下执行您想要的操作。这段代码的时间复杂度是O(n)，其中n是总点数。
# Find the indices of all boundary points, in increasing index order,
# assuming the hull is a rectangle aligned with the axes.
x_limits = (min(pt[0] for pt in points), max(pt[0] for pt in points))
y_limits = (min(pt[1] for pt in points), max(pt[1] for pt in points))
boundary_indices = [idx for idx, (x, y) in enumerate(points)
if x in x_limits or y in y_limits]然而，这种情况看起来很简单。以下是适用于所有二维情况的更通用代码，尤其是当点具有整数坐标时。这是因为如果精度不精确，查找一个点是否恰好在直线段上是很困难的。这段代码在时间复杂度O(n*m)中运行，其中n是点的数量，m是凸包中的顶点数量。
# Find the indices of all boundary points, in increasing index order,
# making no assumptions on the hull.
def are_collinear2d(pt1, pt2, pt3):
"""Return if three 2-dimensional points are collinear, assuming
perfect precision"""
return ((pt2[0] - pt1[0]) * (pt3[1] - pt1[1])
- (pt2[1] - pt1[1]) * (pt3[0] - pt1[0])) == 0
vertex_pairs = list(zip(vertices, vertices[1:] + vertices[0:1]))
boundary_indices = []
for idx, pt in enumerate(points):
for v1, v2 in vertex_pairs:
if are_collinear2d(pt, v1, v2):
boundary_indices.append(idx)
break页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50888553
复制相关文章
相似问题