合并最近的凸多边形
Combine Nearest Convex Polygons
我有一组点云（一组已确定在其自己区域内的点）。
我们的目标是将这些单独的集群组合起来
我。相交
二。在彼此之间的最小距离内
检查 ii 使这更困难。为了快速处理这些点云，我正在创建 AABB（沿 X 轴对齐的轴对齐边界框）。
我目前的方法是利用分离轴定理的一些性质：
- 为每个点云创建 AABB
- 对于每个 AABB，检查它们是否重叠，方法是将它们投影到随机轴上，然后根据它们落在这条线 o(nlog(n)) 上的位置对这些线性投影进行排序。然后我遍历此列表以使用 SAT 检查 O(N) 的交叉点。大多数 AABB 的线性投影不会重叠，因此不会相交，我可以手动检查那些重叠的线性投影（因为 1D 中没有重叠保证没有相交，但反之则不然）。
最后一部分是我卡住的地方。上面的 1D 投影是为了避免 O(n^2) 对交叉点的成对检查。但是为了组合在某个阈值内但不相交的凸多边形，我看不到 O(N^2) 成对检查的方法。
有没有一种方法可以构造一些树或图来组合彼此一定距离内的所有凸多边形而不检查每个成对组合？
如果您使用我从 1 和 2 开始的步骤，您可以假设剩余的 pointclouds/AABB 不相交。
编辑
一个可能的解决方案是将 threshold/2 添加到 AABB 宽度和高度，并检查交叉点。如果它们相交，那么我可以检查两个实际交叉点（这对于 AABB 来说很快），以及两者之间的最小距离。
我最终使用了我的随机轴的法线，并在两个方向上检查了 1D 中的两个重叠，这大大加快了我的算法（如果沿一个轴存在集群，则消除了减速）。
对于距离阈值，保证相交所需的所有边上的最小 AABB 距离填充为 A/2。这捕获了 AABB 仅在 x 或 y 方向上分开的所有情况（对角线情况需要 A*sqrt(2)/4)
我认为为给定的一组相交框寻找相交框的问题称为'spatial join'。还有TOUCH等专用算法。
但是，我发现如果使用空间索引，简单地遍历框并检查重叠是非常有效的。这意味着对于每个框，您都可以查询相交框的空间索引。
传统上，您可以为此使用 R-Tree 或 X-Tree。
就我个人而言，我使用 PH-Tree（我自己的 Java 实现）获得了很好的结果，例如使用大约 1,200,000 个 3D 框（6000 个相交框）的数据集，加载索引并执行在台式机上查询总共需要大约 6 秒。
编辑
我不确定复杂度，但它似乎低于 O(n * log n)。
我有一组点云（一组已确定在其自己区域内的点）。
我们的目标是将这些单独的集群组合起来
我。相交
二。在彼此之间的最小距离内
检查 ii 使这更困难。为了快速处理这些点云，我正在创建 AABB（沿 X 轴对齐的轴对齐边界框）。
我目前的方法是利用分离轴定理的一些性质：
- 为每个点云创建 AABB
- 对于每个 AABB，检查它们是否重叠，方法是将它们投影到随机轴上，然后根据它们落在这条线 o(nlog(n)) 上的位置对这些线性投影进行排序。然后我遍历此列表以使用 SAT 检查 O(N) 的交叉点。大多数 AABB 的线性投影不会重叠，因此不会相交，我可以手动检查那些重叠的线性投影（因为 1D 中没有重叠保证没有相交，但反之则不然）。
最后一部分是我卡住的地方。上面的 1D 投影是为了避免 O(n^2) 对交叉点的成对检查。但是为了组合在某个阈值内但不相交的凸多边形，我看不到 O(N^2) 成对检查的方法。
有没有一种方法可以构造一些树或图来组合彼此一定距离内的所有凸多边形而不检查每个成对组合？
如果您使用我从 1 和 2 开始的步骤，您可以假设剩余的 pointclouds/AABB 不相交。
编辑
一个可能的解决方案是将 threshold/2 添加到 AABB 宽度和高度，并检查交叉点。如果它们相交，那么我可以检查两个实际交叉点（这对于 AABB 来说很快），以及两者之间的最小距离。
我最终使用了我的随机轴的法线，并在两个方向上检查了 1D 中的两个重叠，这大大加快了我的算法（如果沿一个轴存在集群，则消除了减速）。
对于距离阈值，保证相交所需的所有边上的最小 AABB 距离填充为 A/2。这捕获了 AABB 仅在 x 或 y 方向上分开的所有情况（对角线情况需要 A*sqrt(2)/4)
我认为为给定的一组相交框寻找相交框的问题称为'spatial join'。还有TOUCH等专用算法。 但是，我发现如果使用空间索引，简单地遍历框并检查重叠是非常有效的。这意味着对于每个框，您都可以查询相交框的空间索引。 传统上，您可以为此使用 R-Tree 或 X-Tree。
就我个人而言，我使用 PH-Tree（我自己的 Java 实现）获得了很好的结果，例如使用大约 1,200,000 个 3D 框（6000 个相交框）的数据集，加载索引并执行在台式机上查询总共需要大约 6 秒。
编辑
我不确定复杂度，但它似乎低于 O(n * log n)。