結合最接近的凸多邊形

Question

我有一個點雲數組（已確定位於其自己的區域中的一組點）。

我們的目標是將這些單獨的羣集組合起來，這些羣集可以是

i。相交

ii。在彼此間的最小距離內

檢查ii使這變得更加困難。爲了快速處理這些點雲，我創建了AABB（沿X軸對齊的軸對齊邊界框）。

我的當前方法是使用分離軸定理的一些性質：

1. 每個點雲
2. 對於每個AABB創建AABB，檢查是否它們是由這些投影到隨機軸，然後重疊（nlog（n））將這些線性投影按照它們落在該行上的位置排序。然後我通過這個列表查看使用SAT檢查交叉點O（N）。大多數AABB的線性投影不會重疊，因此不會相交，而且我可以手動檢查（因爲1D中沒有重疊保證沒有交集，但反過來不是這樣）。

最後一部分是我卡住的地方。上述一維投影是爲了避免O（n^2）兩兩交叉檢查。但爲了結合在一定閾值內但不相交的凸多邊形，我無法看到圍繞O（N^2）兩兩檢查的方式。

有沒有辦法構造一些​​樹或圖來組合所有在一定距離範圍內的凸多邊形而不用檢查每個成對組合？

如果使用我使用我的步驟從1 & 2，您可以假設剩餘的pointclouds/AABB不相交。

EDIT

的潛在解決方案是添加的threshold/2到AABB寬度和高度，並檢查是否有交叉點。如果它們相交，那麼我可以檢查兩個實際的交點（對AABB來說這是很快的），以及兩者之間的最小距離。

Answer 1

我最終使用了我的隨機軸的法線，並在兩個方向上檢查了兩個方向上的兩個重疊，這大大加快了我的算法（如果沿着一個軸聚集，則消除減速）。

對於距離閾值，保證交叉所需的所有邊上的距離填充的最小值爲A/2。這就捕獲了所有僅在x或y方向上分離的情況（對角線情況需要A * sqrt（2）/ 4）

Answer 2

我認爲給定一組相交框找到相交框的問題是稱爲「空間連接」。有專門的算法，如TOUCH。 但是，如果使用空間索引，我發現只需遍歷這些框並檢查重疊是非常有效的。這意味着對於每個框，您可以查詢相交框的空間索引。 古典上你可以使用R-Tree或X-Tree。

就個人而言，我用PH-Tree（我自己的Java實現）獲得了很好的結果，例如數據集大約有1200,000個3D盒子（6000個相交盒子），加載索引和執行查詢需要大約6秒鐘臺式機。

編輯

我不知道的複雜性，但它似乎是低於O（N * log n）的。