1

我有一组点云（一组已确定在自己的区域内的点）。

目标是结合这些单独的集群

一世。相交

ii. 在彼此之间的某个最小距离内

Check ii 使这变得更加困难。为了快速处理这些点云，我正在创建 AABB（沿 X 轴对齐的轴对齐边界框）。

我目前的方法是使用分离轴定理的一些属性：

  1. 为每个点云创建 AABB
  2. 对于每个 AABB，检查它们是否重叠，方法是将它们投影到随机轴上，然后按照它们落在这条线上的位置 o(nlog(n)) 对这些线性投影进行排序。然后，我浏览此列表以使用 SAT 检查交叉点 O(N)。大多数 AABB 的线性投影不会重叠，因此不会相交，而那些我可以手动检查的投影（因为 1D 中没有重叠保证没有相交，但反之则不然）。

最后一部分是我卡住的地方。完成上述一维投影是为了避免 O(n^2) 成对检查交叉点。但是为了组合在某个阈值内但不相交的凸多边形，我看不到 O(N^2) 成对检查的方法。

有没有办法构建一些树或图形来组合彼此在一定距离内的所有凸多边形而不检查每个成对组合？

如果使用我的步骤 1 和 2，您可以假设剩余的点云/AABB 不相交。

编辑

一个潜在的解决方案是将其添加threshold/2到AABB宽度和高度，并检查交叉点。如果它们相交，那么我可以检查两个实际的交叉点（这对 AABB 来说很快），以及两者之间的最小距离。

4

2 回答 2

0

我最终使用了我的随机轴的法线，并检查了两个方向上的一维重叠，这大大加快了我的算法（如果沿着一个轴聚集，则消除了减速）。

对于距离阈值，AABB保证交叉点所需的所有边上的最小距离填充为 A/2。AABB这捕获了仅在 x 或 y 方向上分隔的所有情况（对角线情况需要 A*sqrt(2)/4）

于 2016-03-28T05:06:28.260 回答
0

我认为为给定的一组相交框找到相交框的问题称为“空间连接”。有专门的算法，例如TOUCH。但是，我发现如果使用空间索引，简单地遍历框并检查重叠是非常有效的。这意味着对于每个 for 框，您都可以查询相交框的空间索引。经典地，您可以为此使用 R-Tree 或 X-Tree。

就我个人而言，我使用PH-Tree （我自己的 Java 实现）得到了非常好的结果，例如使用大约 1,200,000 个 3D 框（6000 个相交框）的数据集，在台式机上加载索引和执行查询总共需要大约 6 秒.

编辑

我不确定复杂性，但它似乎低于 O(n * log n)。

于 2016-03-29T09:23:23.983 回答