当前位置: 首页>>技术教程>>正文


python – 如何找到二维点云的Alpha形状(凹壳)?

, , , ,

问题描述

我正在寻找一种可在两个维度上计算alpha形状的实现。我正在运行ubuntu。我更喜欢使用命令行实用程序来执行此任务,但是使用python库也可以。

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

我尝试安装最新的cgal python绑定,但是一段时间以来不支持这些绑定,并且不再在Ubuntu 11.04上编译(我也在Ubuntu 10.04上尝试过并且没有运气)。由Aaron Straup Cope在flickr上开发的项目Clustr也不会在Ubuntu 11.04上编译(可能是因为它也与较早的CGAL库绑定)。

我还从贝尔实验室的Ken Clarkson尝试了this implementation。它几乎输出了我想要的输出,输出似乎在另一个比例上,并且将浮点数转换为整数。

我还尝试了dionysus的python绑定。这些已编译,但是当我将函数fill_alpha2D_complex(points, f)输入点列表时,输出不是我期望的。它不是二维点的列表,而是一个”persistence diagram”,我不知道那是什么意思。

有人知道这个问题的简单解决方案吗?

更新:我想打印出与Alpha形状相关联的点,该点即将不再连接。我认为这意味着“给我与最小alpha值相关的点,以使形状相连。”

更新现在我发现了如何从Ken Clarkson’s implementation中获得我想要的东西,以及从dionysus implementation中(或多或少获得我想要的东西)。克拉克森(Clarkson)的实现做对了,它只是输出点的索引,而不是点本身(与狄俄尼索斯同理),我需要正确地选择一些标记。我写的包装纸如下。该解决方案是理想的,因为它会产生既连接又不包含孔的Alpha形状。 Alpha是自动设置的。另一方面,狄俄尼索斯(Dionysus)不会自动发现此alpha值。另外,可以将Clarkson的实现设置为输出形状的ps图像(带有-afps标志)。要获取Clarkson的代码以使用non-ancient版本的GCC进行编译,您需要遵循here概述的步骤。以下代码可用作库或独立包装器:

#!/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文档中发现了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]

参考资料

本文由Ubuntu问答整理, 博文地址: https://ubuntuqa.com/article/7714.html,未经允许,请勿转载。

相关内容