我正在寻找凹壳问题的 python 实现。我的问题有点不同，因为我没有一组点，而是一组线，结果凹壳将大致沿线绑定（如左图所示）。
我知道没有单一的“正确答案”。但是一些近似值足以满足我的需要。一种可能的解决方案是获取每条线并将其插值到假设为 20 个点的范围内，然后找到所有创建点的凹壳。不确定。
编辑：
我认为这些线条增加了一些价值，使船体更清晰，更容易找到。
即使不使用线条（只是从点列表中找到一个凹壳），一个好的 python 实现也会有帮助
问问题
11746 次
3 回答
21
这是您的子问题的答案：
即使不使用线条（只是从点列表中找到一个凹壳），一个好的 python 实现也会有帮助
你可以使用alphashape。棘手的部分是选择alpha适合您需求的产品。Alphashape带有寻找最佳 alpha 值的功能。基本上它从0(= 凸包) 开始并增加 alpha 直到它开始失去点。我们从这个最佳值中取 95%，这当然是一个相当随意的解，但在许多情况下它会给你一个很好的近似值。
import alphashape
import matplotlib.pyplot as plt
from descartes import PolygonPatch
points = [(17, 158),(15, 135),(38, 183),(43, 19),(93, 88),(96, 140),(149, 163),(128, 248),(216, 265),(248, 210),(223, 167),(256, 151),(331, 214),(340, 187),(316, 53),(298, 35),(182, 0),(121, 42)]
alpha = 0.95 * alphashape.optimizealpha(points)
hull = alphashape.alphashape(points, alpha)
hull_pts = hull.exterior.coords.xy
fig, ax = plt.subplots()
ax.scatter(hull_pts[0], hull_pts[1], color='red')
ax.add_patch(PolygonPatch(hull, fill=False, color='green'))
一种可能的解决方案是获取每条线并将其插值到假设为 20 个点的范围内，然后找到所有创建点的凹壳。
这不会为您提供所需的输出，因为凹壳将跟随这些附加（假）点，并且它变得比原始点更凹。
我认为整个问题的最佳解决方案是从点的凹壳开始，以获得最佳 alpha optimizealpha，然后减少它，直到您的外壳不与@sgillen 建议的任何线相交。这可以类似于通过使用带有测试的二等分循环找到最佳 alpha 来完成any([polygon.crosses(line) for line in lines])。
于 2019-08-06T14:18:23.517 回答
5
这是一个关于使用 python 为一组点找到凹壳的github repo 。
我给你的建议如下。使用每条线的端点创建一组点。然后使用链接到代码为这些点生成一个凹壳，并对 alpha 的值进行一些猜测。完成此操作后，您可以检查生成的船体是否与您的任何线相交，以及它是否修改了 alpha。如果您愿意，您可以自动检查交叉点和调整。
您也可以尝试将线条的中点添加到您的点集，这可能会减少您需要尝试的 alpha 数量。
于 2019-08-03T01:06:50.120 回答
0
虽然这个问题可能已经得到回答，但这也是我的方法：
像其他人一样，您首先必须将线的端点转换为点列表。
之后，您可能需要 SciPy 库中的这个整洁的函数：scipy.spatial.ConvexHull(). 基本上，您只需将带有顶点的 numpy-array 传递给函数（使用 创建numpy.array()），它会返回一个 hull-Object
这是文档
使用.points- 属性，您可以获得所有点，或者使用.vertices- 属性，您可以获得形成船体的输入列表的索引。如果您对此感兴趣，还可以获得诸如面积或体积（用于 3D 形状）之类的东西。
~冈花
于 2019-08-07T21:15:39.280 回答