2

在例如 100 个 3D 点的点云中找到由 5 个刚性、共面、非共线点定义的形状的最有效方法是什么？

4

3 回答 3

1

您可以使用距离在相关变换（旋转、移位等）下不变的事实。因此，匹配距离是一个好主意。尝试这个：

首先，为 3d 云创建一个包含所有成对距离的数据结构。那是100x100，所以还不错。

现在，开始匹配距离：对于 2d 集中的每个点，查看 3d 集中是否存在匹配距离。维护一个匹配距离图并慢慢扩展它。

你知道如何把它变成一个算法吗？使用正确的数据结构，这可能是合理的。

于 2013-06-19T21:58:27.933 回答
0

蛮力方法

在伪代码中：

Find all possible three point tuples from your set of points.
Every three-tuple now defines a plane.
For all planes:
   filter the set of points for points that lie in the plane
   if you have five or more points remaining, return the first five and exit  
return NOT_FOUND and exit

请注意，这种方法的复杂性是阶乘，这意味着O(n!)

例如，对于 100 个点的集合，您必须进行约 1700 万个共面性检查，而对于 1000 个点，您需要进行约 1700 亿个共面性检查。

于 2013-06-19T13:49:15.263 回答
-1

您可以选择 5 个点并找到一个形状。100C5 可以解决问题。现在如何有效地计算组合，您可以找到它的算法。此处提供了示例实现

于 2013-06-19T13:42:54.227 回答