如何找到 2d 点云的 alpha 形状（凹壳）？

Question

我正在寻找一种计算二维 alpha 形状的实现。我正在运行ubuntu。我更喜欢使用命令行实用程序来完成此任务，但使用 python 库也可以。

在 Google 中，我发现了许多计算 alpha 形状的实现。但他们都没有输出我想要的东西。作为输入，我有一个二维点列表（例如，文本文件中每行一对浮点数）。作为输出，我想要另一个具有相同比例的二维点列表。

我尝试安装cgal的最新Python绑定，但这些已经有一段时间不受支持并且不再在Ubuntu 11.04上编译（我也在Ubuntu 10.04上尝试过但没有运气）。 Clustr，一个由 Aaron Straup Cope 在 flickr 开发的项目也无法在 Ubuntu 11.04 上编译（可能是因为它是也与旧的 CGAL 库相关）。

我还尝试了贝尔实验室的 Ken Clarkson 的此实现。它输出的几乎是我想要的，输出似乎是另一个比例，它将浮点数转换为整数。

我还尝试了 dionysus 的 python 绑定。这些已编译，但当我向函数 fill_alpha2D_complex(points, f) 提供我的点列表时，输出不是我所期望的。它不是二维点的列表，而是似乎是一个“持久性图”，我不知道这意味着什么。

有人知道解决这个问题的简单方法吗？

更新：我想打印出与 alpha 形状相关的点，它处于不再连接的边缘。我认为这意味着“给我与最小 alpha 值相关的点，以便形状是连接的”。

更新 我现在找到了如何从 Ken Clarkson 的实现< /a> 和（或多或少是我想要的）来自 dionysus 实现。克拉克森的实现做了正确的事情，它只是输出点的索引而不是点本身（与狄俄尼索斯相同的故事），并且我需要获得一些正确的可选标志。我写的包装如下。此解决方案非常理想，因为它生成的 alpha 形状既连通又不含孔。阿尔法是自动设置的。另一方面，狄俄尼索斯不会自动发现这个 alpha 值。另外，Clarkson 的实现可以设置为输出形状的 ps 图像（带有 -afps 标志）。要让 Clarkson 的代码使用非古代版本的 GCC 进行编译，您需要按照 此处。以下代码可以用作库或独立的包装器：

#!/usr/bin/python -O

import sys, os
import subprocess
import tempfile

hull_path = "./hull.exe"

def get_alpha_shape(points):
    # Write points to tempfile
    tmpfile = tempfile.NamedTemporaryFile(delete=False)
    for point in points:
        tmpfile.write("%0.7f %0.7f\n" % point)
    tmpfile.close()

    # Run hull
    command = "%s -A -m1000000 -oN < %s" % (hull_path, tmpfile.name)
    print >> sys.stderr, "Running command: %s" % command
    retcode = subprocess.call(command, shell=True)
    if retcode != 0:
        print >> sys.stderr, "Warning: bad retcode returned by hull.  Retcode value:" % retcode
    os.remove(tmpfile.name)

    # Parse results
    results_file = open("hout-alf")
    results_file.next() # skip header
    results_indices = [[int(i) for i in line.rstrip().split()] for line in results_file]
#    print "results length = %d" % len(results_indices)
    results_file.close()
    os.remove(results_file.name)

    return [(points[i], points[j]) for i,j in results_indices]

if __name__ == "__main__":
    points = [tuple([float(i) for i in line.rstrip().split()]) for line in sys.stdin]
    for point_i, point_j in get_alpha_shape(points):
        sys.stdout.write("%0.7f,%0.7f\t%0.7f,%0.7f\n" % (point_i[0], point_i[1], point_j[0], point_j[1]))
    sys.exit(0)

Answer 1

我在 dionysus 文档中找到了this，它可能会给你alpha形状：

complex = Filtration()
fill_alpha2D_complex(points, complex)
alphashape = [s for s in complex if s.data[0] <= .5]

那么我相信你需要做类似的事情：

for simplex in alphashape:
    print [v for v in simplex.vertices]

Answer 2

import alphashape
import numpy as np
from descartes import PolygonPatch
import matplotlib.pyplot as plt

n = 1000
points = np.random.rand(n, 2)

# Define alpha parameter
alpha= 20

# Generate the alpha shape
alpha_shape = alphashape.alphashape(points, alpha)

# Initialize plot
fig, ax = plt.subplots()

# Plot input points
ax.scatter(*zip(*points))

# Plot alpha shape
ax.add_patch(PolygonPatch(alpha_shape, alpha=.5, fc='blue', ec='red'))


pnts = [x for x in alpha_shape.boundary.coords]
plt.scatter(*zip(*pnts),marker='s')



plt.show()