kdtree内の境界ボックス間の最小距離

Question

ユークリッド空間内の同じ木の最小距離b/w 2 kdtree境界ボックスを見つける必要があります。各ボックスが5つの要素を維持しているとします。私はjavaを使って最小ユークリッド距離が必要です。

double QHRect[][] = QNode.m_NodesRectBounds; 
double RHRect[][] = RNode.m_NodesRectBounds; 

    QHRect[][]: 5.74842E-4,7.76626E-5,6.72655E-4, 
        0.5002329025,0.2499048942,0.25046735625 
    RHRect[][]: 
        0.75006193275,0.7495593574,0.75005675875, 
        0.999890963,0.999386589,0.99985146 

Answer 1

この実装では、他の言語と比較してJavaの実装について厄介なことはありません。このような問題を処理するための一般的なアルゴリズムを知る必要があります。

1. 2つの境界ボックス（立方体）のすべての12の頂点を列挙します。
2. 2つの境界ボックスの12面をすべて列挙します。
3. 一方の頂点と他方の頂点の間のユークリッド距離を求めます。これは、点と面の最短距離に似ています。
4. これらの2 * 6 * 6 = 72の組み合わせのうち、最小のものを選んでください。

問題の一般的なバージョンでは、2つの境界ボックスも交差するかどうかをチェックする必要があります。