凸包精度不足 - 有什么替代方案？

Question

我有一个包含大约25000个点的集合，我想找出它的边界。使用凸包算法可以做到这一点，但结果是我只得到了大约19个坐标，这显然太少了。

这里有一段来自SciPy文档的示例代码。如果你运行这段代码，你会发现得到的点的数量非常有限。

from scipy.spatial import ConvexHull
import numpy as np
import matplotlib.pyplot as plt

points = np.random.rand(50, 2)   # 30 random points in 2-D
hull = ConvexHull(points, incremental=False)

plt.plot(points[:,0], points[:,1], 'o')
for simplex in hull.simplices:
    plt.plot(points[simplex,0], points[simplex,1], 'r-')

plt.show()

有没有办法得到更多的点，以提高边界的准确性？还是说我需要用不同的代码？

Answer 1

那么你的外壳就不是凸的了！

你可以试试这个链接：http://www.geosensor.net/papers/duckham08.PR.pdf，里面有一个算法，可能能帮你得到你想要的结果，也就是一种能比较好地跟随一组点“边界”的方法。

你也可以试试“阿尔法形状”。