java - 带矩形的 kd 树

Question

我已经实现了一个使用给定点的 kd 树。例如，我可以向树中添加点，然后找到与给定 x、y 坐标最近的点，这很棒。

我想扩展它以使用矩形，例如用户给出一个 x 和 ay 坐标、一个宽度和一个高度，然后我希望能够在这个结构上进行范围查询和最近邻搜索。我将如何扩展我必须处理矩形数据的当前树？

Answer 1

Kd 树非常适合低维点数据。对于由多个点（线、矩形等）组成的任何东西，我建议使用 R-tree。

Answer 2

我知道 kd 树的一个很好的扩展来处理矩形。它被称为Box Sort算法，可以在这里找到Box sort。这个想法与 kd 树几乎相同。这篇论文也有一个 Pascal 实现，但翻译成 Java 应该是直截了当的。