一组线的 Python 凹壳多边形

Question

我正在寻找用于 Concave Hull 问题的 Python 实现。我的问题有点不同，因为我没有一组点，而是一组线，其中结果 Concave-Hull 将大致沿线绑定（如左图所示）。

我知道没有单一的“正确答案”。但是一些近似值足以满足我的需要。一种可能的解决方案是取每条线并将其插入到一个范围内，比如 20 个点，然后找到所有创建点的凹包。不确定。

编辑：

我认为线条增加了一些价值，使船体更清晰，更容易找到。

这个问题的一个很好的 python 实现，即使不使用线（只是从点列表中找到一个凹壳）也会有帮助

Answer 1

这是您子问题的答案：

这个问题的一个很好的 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])。

Answer 2

这是一个关于使用 python 查找一组点的凹壳的github 存储库。

我给你的建议如下。使用每条线的端点创建一组点。然后使用链接到的代码为这些点生成凹壳，并对 alpha 值进行一些猜测。完成此操作后，您可以检查生成的外壳是否与您的任何线相交，以及它是否确实修改了 alpha。如果您愿意，您可以自动检查交叉点和调整。

您还可以尝试将线条的中点添加到点集中，这可能会减少您需要尝试的 alpha 数量。