Python凹壳多边形：一组线的集合

Question

我正在寻找一个Python实现的凸包问题。我的问题有点不同，因为我没有一组点，而是一组线段，凸包结果将粗略地沿着线段边界限制（如左图所示）。

我知道没有单一的“正确答案”。但对于我的需求，一些近似解决方案就足够了。 一种可能的解决方案是取每条直线并将其插值到一定范围内，比如20个点，并找到所有创建点的凸包。不确定。

编辑：

我认为线条增加了一些价值，使得凸壳更清晰，更易于找到。

即使没有使用线条（只从点列表中找到凸包），该问题的良好Python实现也将非常有帮助。

- user972014

---

你能否根据线段的端点创建一组点呢？这样就可以转化成“普通”的凸包问题了。 - Calvin Godfrey

首先，我仍然需要一个Python实现（即使它不支持行信息，我也很想有一个）。其次，我认为这些行本身添加了一些应该被使用的问题信息。 - user972014

为什么这些线会添加任何信息呢？最终，凸壳是关于（端）点的，你可以从这些点生成线条（反之亦然）。由于你没有展示任何启动代码，很难帮助你完成特定实现。能提供一个例子吗？ - a_guest

您的问题表述有些混淆。您需要澄清是否期望交点对于船体的形成有所贡献。否则，这些线条就是无关且分散注意力的信息。 - Tasos Papastylianou

有许多基于顶点的O(n log n)凸包算法，但连接n个点的线的数量可能高达O(n^2)（理论最大值为n(n-1)/2）- 即使是创造这些线本身的行为在渐近意义下也可能比直接从点计算凸包更昂贵。 - meowgoesthedog

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个点，然后找出所有创建点的凸多边形。

这不会给您所需的输出，因为凸多边形将跟随这些额外（虚假）点，并且比使用原始点更加凸出。
我认为整个问题的最佳解决方案是从通过optimizealpha获得的最佳 alpha 的点的凸多边形开始，然后逐渐减小它，直到您的凸多边形不与任何线相交，如 @sgillen 所建议的那样。可以类似于使用一个二分循环来找到最佳 alpha，测试any([polygon.crosses(line) for line in lines])。

- Stef

---

我认为alphashape仅支持Python 3。 - zyy

有没有一种方法可以查询一个点是否在多边形凹壳内？ - azerila

@Alipapa https://dev59.com/HGQn5IYBdhLWcg3wiXqd ? - Stef

Answer 2

这里有一个使用Python找到一组点的凹壳的GitHub库。

我向您推荐以下操作。使用每条线的端点创建一组点。然后使用链接的代码生成这些点的凹壳，猜测alpha的值。完成后，您可以检查生成的壳是否与您的线相交，如果是，则修改alpha。如果愿意，您也可以自动化执行交叉和调整检查。

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

- sgillen