我正在寻找一个计算二维的alpha形状的实现。 我正在运行的Ubuntu。 我更喜欢这个任务的命令行工具，但也可以用python库。
在Google中，我发现了许多计算alpha形状的实现。 但是他们没有一个输出我想要的。 作为input，我有一个二维点列表（例如，文本文件中每行一对浮点数）。 作为输出，我想要有相同比例的二维点的另一个列表。
我已经尝试安装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)函数fill_alpha2D_complex(points, f)我的列表时，输出结果并不是我所期望的。 这不是一个二维点的列表，而是似乎是一个“持久性图”，我不知道这是什么意思。
任何人都知道这个问题的简单解决scheme？
更新：我想打印出与Alpha形状相关的点，它们处于不再连接的边缘。 我认为这意味着“给我与最小的阿尔法值关联的点，使形状连接”。
更新我现在发现如何得到我想从肯克拉克森 的实现，以及（或多或less我想要的）从dionysus实现 。 Clarkson的实现是正确的，它只是输出点的索引而不是点（与狄奥尼索斯相同的故事），我需要得到一些可选的标志。 我写的包装是下面。 这个解决scheme是理想的，因为它产生了一个连接的并且不包含孔的alpha形状。 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)
我在dionysus docs中找到了这个可能会给你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]