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

Question

我需要找到欧几里德空间中同一棵树的两个 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. 枚举两个边界框（立方体）的所有 12 个顶点。
2. 枚举两个边界框的所有 12 个面。
3. 求一个顶点与另一个顶点之间的欧几里得距离。这类似于点和平面之间的最短距离。
4. 在这 2*6*6=72 个组合中，选择最小的一个，你就会得到答案。

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