Linux 如何找到二维点云的 alpha 形状（凹壳）？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/6833243/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How can I find the alpha shape (concave hull) of a 2d point cloud?
提问by conradlee
I am looking for an implementation that calculates alpha shapes in two dimensions. I am running ubuntu. I would prefer a command line utility for this task, but will also be fine with a python library.
我正在寻找一种计算二维 alpha 形状的实现。我正在运行 ubuntu。我更喜欢这个任务的命令行实用程序，但也可以使用 python 库。
In Google I have found many implementations that calculate alpha shapes. But none of them output what I want. As input I have a list of two dimensional points (e.g., one pair of floats per line in a text file). As output I want another list of two dimensional points with the same scale.
在 Google 中，我发现了许多计算 alpha 形状的实现。但他们都没有输出我想要的。作为输入，我有一个二维点列表（例如，文本文件中每行一对浮点数）。作为输出，我想要另一个具有相同比例的二维点列表。
I have tried installing the latest python bindings of cgal, but these have not been supported in a while and no longer compile on Ubuntu 11.04 (I also tried on Ubuntu 10.04 and had no luck). Clustr, a project developed at flickr by Aaron Straup Cope will also not compile on Ubuntu 11.04 (probably because it is also tied to older CGAL libraries).
我曾尝试安装cgal的最新 python 绑定，但这些绑定已经有一段时间不受支持，并且不再在 Ubuntu 11.04 上编译（我也在 Ubuntu 10.04 上尝试过，但没有成功）。 Clustr，一个由 Aaron Straup Cope 在 flickr 开发的项目也不能在 Ubuntu 11.04 上编译（可能是因为它也与旧的 CGAL 库相关联）。
I also tried this implementationfrom a Ken Clarkson at bell labs. It outputs nearly what I want, the output seems to be in another scale and it turns floats into ints.
我还从贝尔实验室的肯克拉克森那里尝试了这个实现。它输出几乎我想要的东西，输出似乎是另一种规模，它把浮点数变成整数。
I also tried the python bindings of dionysus. These compiled, but when I fed the function fill_alpha2D_complex(points, f)with my list of points, the output was not what I expected. It was not a list of two dimensional points, but rather seems to be a "persistence diagram" I don't know what that means.
我还尝试了dionysus的 python 绑定。这些编译，但是当我fill_alpha2D_complex(points, f)用我的点列表输入函数时，输出不是我所期望的。它不是二维点的列表，而是似乎是一个“持久性图”，我不知道那是什么意思。
Anyone know of a simple solution to this problem?
有人知道这个问题的简单解决方案吗？
UPDATE:I want to print out the points associated with the alpha shape where it is on the verge of not being connected anymore. I think this means "give me the points associated with the smallest alpha value such that the shape is connected."
更新：我想打印出与 alpha 形状相关的点，它处于不再连接的边缘。我认为这意味着“给我与最小 alpha 值相关的点，以便形状连接。”
UPDATEI now found out how to get what I want from Ken Clarkson's implementationand (more or less what I want) from the dionysus implementation. Clarkson's implementation was doing the right thing, it just output the indices of the points rather than the points themselves (same story with dionysus), and I needed to get some optional flags right. The wrapper I wrote is below. This solution is ideal because it produces an alpha shape that is both connected and does not contain holes. Alpha is set automatically. Dionysus, on the other hand, does not automatically discover this values of alpha. Plus Clarkson's implementation can be set to output a ps image of the shape (with the -afps flag). To get Clarkson's code to compile with non-ancient version of GCC, you need to follow the step outlined here. The following code can be used as a library or as a stand alone wrapper:
更新我现在找到了如何从Ken Clarkson 的实现和（或多或少我想要的）狄俄尼索斯实现中获得我想要的. 克拉克森的实现是正确的，它只输出点的索引而不是点本身（与狄俄尼索斯的故事相同），我需要正确设置一些可选标志。我写的包装器如下。此解决方案是理想的，因为它生成了既连接又不包含孔的 alpha 形状。Alpha 是自动设置的。另一方面，狄俄尼索斯不会自动发现这个 alpha 值。此外，克拉克森的实现可以设置为输出形状的 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)
采纳答案by combatdave
I found thisin the dionysus docs which might give you the alpha shape:
我在 dionysus docs 中找到了这个，它可能会给你 alpha 形状：
complex = Filtration()
fill_alpha2D_complex(points, complex)
alphashape = [s for s in complex if s.data[0] <= .5]
Then I believe you need to do something like:
然后我相信您需要执行以下操作：
for simplex in alphashape:
print [v for v in simplex.vertices]
