Python 一组线的凹壳多边形

Question

我正在寻找凹壳问题的 python 实现。我的问题有点不同，因为我没有一组点，而是一组线，其中结果 Concave-Hull 将粗略地沿着线（如左图所示）。

我明白没有单"correct answer"。但是一些近似值就足以满足我的需要。一种可能的解决方案是获取每条线并将其插入到一个范围内，比方说 20 个点，然后找到所有创建的点的凹包。不确定。

编辑：

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

该问题的良好 python 实现，即使不使用线（仅从点列表中找到凹包）也会有所帮助

Answer 1

这里是 github repo 使用 python.

寻找一组点的凹包

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

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

Answer 2

这是您子问题的答案：

A good python implementation for the problem, even if not using the lines (just finding a concave hull from a list of points) will also be helpful

您可以使用 alphashape. The tricky part is to choose an alpha that fits your needs. Alphashape comes with a function to find the optimum alpha value. Basically 它以 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'))

One possible solution is to take each line and interpolate it to a range of let's say 20 points and find the concave hull of all the created points.

这不会给你想要的输出，因为凹包会跟随这些额外的（假的）点，并且它变得比原始点更凹。
我认为整个问题的最佳解决方案是从 optimizealpha 获得的最佳 alpha 点的凹包开始，然后减少它，直到你的包不与你的任何线相交，正如@sgillen 所建议的.这可以通过使用带有测试 any([polygon.crosses(line) for line in lines]).

的二分循环找到最佳 alpha 来类似地完成。

Answer 3

虽然这个问题可能已经有了答案，但这里也是我的方法：

就像其他人也说的那样，您首先必须将线的端点转换为点列表。

之后，您可能需要 SciPy 库中的这个简洁函数：scipy.spatial.ConvexHull()。基本上你只是将一个带有顶点的numpy数组传递给函数（使用numpy.array()创建）并且它returns一个hull-Object

Here 是文档

使用.points-属性，您可以获得所有点，或者使用.vertices-属性，您可以获得构成船体的输入列表的索引。如果您对此感兴趣，您还可以获得面积或体积（对于 3D 形状）之类的东西。

~奥卡加纳

Python 一组线的凹壳多边形

Python Concave Hull Polygon of a set of lines

python

concave-hull