kdtree中边界框之间的最小距离

I need to find the minimum distance b/w two kdtree bounding box's of same tree in euclidean space. Suppose each box maintain a 5 elements. I need the minimum Euclidean distance using java.

我需要找到欧几里得空间中同一棵树的最小距离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

1 个解决方案

#1

There is nothing tricky about a Java implementation compared with any other language in this matter. You need to know the general algorithm to handle a problem like this. I believe it is this:

与其他语言相比，Java实现没有什么棘手之处。你需要知道一般的算法来处理这样的问题。我相信是这样的:

Enumerate all 12 vertices of the two bounding boxes (cubes).
枚举两个边界框(立方体)的所有12个顶点。
Enumerate all 12 faces of the two bounding boxes.
列举两个边框的所有12个面。
Find the Euclidean distance between each vertex of one and face of the other. This is similar to the shortest distance between a point and a plane.
求一个顶点与另一个顶点之间的欧几里得距离。这类似于点到平面的最短距离。
Of these 2*6*6=72 combinations, pick the smallest and you have your answer.
在这2*6*6=72个组合中，选择最小的，就得到了答案。

In the general version of the problem, you would also have to check for if the two bounding boxes intersect as well.

在问题的一般版本中，您还必须检查两个边界框是否相交。

#1