java - 具有矩形的 k-d 树

Question

我已经实现了使用给定点的 k-d 树。例如，我可以向树添加点，然后找到距离给定 x、y 坐标最近的点，这很棒。

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

Answer 1

K-d 树非常适合低维点数据。对于由多个点(线、矩形等)组成的任何内容，我建议使用 R 树。