如何找到2d点云的α形（凹形）？

Question

我正在寻找一个计算二维形状的实现。我正在运行Ubuntu。我更喜欢这个任务的命令行实用程序，但对于Python库也可以。

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

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

我也试过从肯拉克森在钟声实验室this implementation。它几乎输出我想要的结果，输出似乎是另一种规模，它将浮点数转换为整数。

我也试过dionysus的python绑定。这些编译，但是当我用功能fill_alpha2D_complex(points, f)与我的列表的点，输出是不是我所期望的。这不是一个二维点的列表，而是似乎是一个“持久性图”，我不知道这意味着什么。

任何人都知道这个问题的简单解决方案？

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

UPDATE我现在发现了如何得到我从Ken Clarkson's implementation想和（或多或少我想）从dionysus implementation。克拉克森的实现是正确的，它只是输出点的索引而不是点（与狄奥尼索斯相同的故事），我需要得到一些可选的标志。下面是我写的包装器。这种解决方案非常理想，因为它可以生成一个既可以连接又不含孔的alpha形状。 Alpha会自动设置。另一方面，狄奥尼索斯不会自动发现这个alpha值。另外，可以将Clarkson的实现设置为输出形状的ps图像（使用-afps标志）。要使Clarkson的代码与非古代版本的GCC一起编译，您需要遵循here的步骤。下面的代码可以作为一个库或作为一个独立的包装：

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

那么我相信你需要：

#!/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

我在酒神文档这可能会给你的阿尔法形状发现this做类似的事情：

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