当你有一个网格时，有许多众所周知的方法来导航它，例如使用半边数据结构，它允许在面和顶点周围轻松循环。kd-trees 是否有类似的结构/算法，可以让您轻松找到相邻和重叠的（半）面？
我最感兴趣的是在边缘循环以找到所有相邻的（半）面和单元格，这似乎变得相当复杂，尤其是在不平衡的 kd 树上。此外，识别相邻面与相同的相对半面重叠的重叠半面将是有用的。
我想知道是否有一些标准算法。很难搜索它们，因为每本书和每一个互联网搜索结果都充满了使用 kd-tree 在欧几里得空间中搜索最近邻居的标准算法，而没有提及如何在 kd-tree 网格或图形中导航以进行查询尊重树本身。
类似于半边结构的东西会非常好，但我想大多数算法宁愿遍历树。
如果没有特定的算法，我真的很想建议如何处理长方体的集合，即 kd 树边界框的几何表示，用于查询邻接、重叠和类似的几何属性。
半边
作为参考，简要介绍了网格上的半边结构。半边结构如下所示：
（图片取自CGAL 手册）
它使所有重要的查询变得非常容易：
- 围绕面部循环：跟随下一个指针，直到您回到起始边缘。
- 查找相邻面：按照相反的指针指向另一个面的半边。
- 找到顶点周围的边：按照下一个指针，然后是相反的指针，找到下一个入射边。
该结构具有更多有用的属性，例如允许使用边界边缘的下一个点跟随网格的边界并围绕孔循环，就像在面内循环一样。
KD树
这些操作仅在多边形网格上得到很好的定义。kd-tree 看起来像这样：
（图片取自维基百科关于 kd-trees的文章）
树是通过细分初始框来构建的。您从一个维度开始，当您细分一个框时，您总是使用下一个维度（例如，x、y、x、y 用于 2D 或 x、y、z、x、y、z 用于 3D）。有多种选择分割平面的方法，具体取决于您的实际应用。
这样的树不是网格，因为它在设计上具有 T 形路口。如果您尝试在此示例树中构建半边结构，您将拥有多个对边的边，正如您在树的最右边一列中看到的那样。
此外，这样的树具有重叠（半）边，如示例树左侧的蓝色边。当您尝试将其拆分为半边时，您会得到四个半边，每个半边都与两个相对的边相邻。
KD树中的邻接
例如，如果要使用这样的树来创建树中包含的点的网格，则需要框之间的邻接信息。
这是一个示例，其中我使用 kd-tree 创建混合四边形/三角形网格，并使用分离顶点的 kd-tree：
（请注意，并非所有具有重叠边缘的框都已连接，有关如何创建此图的更多信息，请参见下文）
共享一条边的邻居也是相应图中的邻居（并且构造保证它是同一条边）。但是不共享同一个父节点的盒子可能彼此相邻。在左上角，您会看到一个三角形，对应于子树：
|\
A |\
B C
其中相邻叶节点与其父单元的相邻单元相连。这仍然是一个相当简单的查询，并且交叉点也不复杂。没有重叠的边缘，并且边缘具有一个或两个不重叠的相对边缘。
但是您也会看到许多三角形和四边形，它们连接的盒子在树中彼此相距很远，没有明显的方法可以找到所需的邻接信息。
在树中寻找邻居
我使用以下算法创建了这个图：
start at all* splits:
traverse the two subtrees in parallel as follows:
if the dimension is the same as the split:
follow+ the subtrees in the split direction in both trees (e.g. right, left)
else:
follow+ both trees in the first direction (e.g. left, left) AND
follow+ both trees in the second direction (e.g right, right)
if both new nodes are leaf nodes, connect them
* all O(n) inner tree nodes.
+ When you arrive at a leaf node, store it and continue traversing the other subtree as before.
这样，您就可以坚持分割平面并始终以相同的方向遍历两个子树，而无需考虑实际坐标来查找要连接的框。这些边形成了上例中的四边形和三角形。
但是这种方法甚至没有找到所有的邻接。例如，大多数四边形应该被分割成三角形，因为有额外的邻接，这是算法找不到的。
即使是底部左数第二个四边形也可以分成两个三角形，就邻接而言，它的边缘交叉点非常短，因此比其他交叉点更难看到。
（找到这些三角形只是一个应用程序，另一方面，识别哪些连接可以创建一个四边形并仍然产生有用的网格可能非常有用。示例中的网格可能对某些应用程序有利而对其他人不利）
是否有更有效和更一般查询的技术？
组合方法不能保证邻居实际上共享一个非零边缘交叉点，正如您在示例中看到的那样，连接它们的中心（或单元格内的其他点）的边缘可能会穿过树中的其他框，无法检测到通过这个算法。
此外，该算法从分割平面开始，并在时间内遍历完整的子树，这似乎相当低效。
我现在正在寻找更快的查询技术来查找单元格、边和顶点的邻居。例如，我想从树中一个盒子的边缘开始，找到所有相邻的面（以及相邻的盒子）。这不仅涉及与边缘相邻的面，还涉及父单元的邻居以及可能出现在 kd-tree 中的更复杂的邻域。
目前我找到的论文
绳子树，在树内构建额外的链接以实现更有效的光线交叉：
Havran, V.、Bittner, J. 和 Zára, J.（1998 年 4 月）。用绳索树进行光线追踪。在第 14 届计算机图形学春季会议上（第 130-140 页）。( PDF )
使用嵌套的 kd-trees 允许一些查询：
Greß, A. 和 Klein, R. (2004)。使用 kd-trees 高效表示和提取 2 流形等值面。图形模型，66（6），370-397。（网站）