我有一个点云数组（已确定位于其自身区域中的一组点）。
我们的目标是将这些
一、交叉
二。在彼此之间的最小距离内
检查二使这更困难。为了快速处理这些点云，我正在创建AABB（沿着X轴对齐的轴对齐包围盒）。
我现在的方法是使用分离轴定理的一些性质：
为每个点云创建aabb
对于每个AABB，检查它们是否重叠，通过将它们投影到随机轴上，然后通过它们落在这条线上O（nlog（n））的位置来排序这些线性投影。然后，我使用SAT浏览此列表以检查交叉点O（N）。大多数AABB的线性投影不会重叠，因此不会相交，并且这样做的投影可以手动检查（因为1D中没有重叠保证不会相交，但相反的情况不成立）。
最后一部分是我被困的地方。上述1D投影是为了避免O（n^2）对交叉点的检查但是为了组合在某个阈值内但不相交的凸多边形，我看不到一个O（N^2）成对检查的方法。
有没有办法构造一些树或图来组合所有在一定距离内的凸多边形而不检查每一对组合？
如果使用1&2中的“我的步骤”，则可以假定其余的点云/AABB不相交。
编辑
一个可能的解决方案是将threshold/2添加到AABB宽度和高度，并检查交叉点。如果它们相交，那么我可以检查两个实际的相交点（对于AABB是快速的），以及两者之间的最小距离。
最佳答案
最后，我使用了随机轴的法线，并且在两个方向上检查了两个方向上的两个重叠，这大大加快了我的算法（如果沿着一个轴进行聚类，则消除了减速）。
对于距离阈值，保证交叉点所需的所有边上的AABB距离填充最小值为a/2。这将捕获所有AABB仅在x或y方向分离的情况（对角线情况需要*sqrt（2）/4）