1

我有一个很长的、半排序的纬度、经度和时区三元组列表。我希望能够快速搜索此列表以找到与任何给定纬度和经度最近的时区，因此我想将此列表制作成 KD 树。

我在想我应该首先将整个文件读入某种数据结构（什么数据结构？可能ArrayList<Triplet<Double, Double, String>>？）。然后取该结构中的中间元素并将其作为根，给我留下一个左右列表。然后继续获取每个列表的中间元素并将其添加为左子或右子。

第一次尝试似乎很慢而且效率低下......但我觉得我做错了。你能为我提供一个算法或伪代码吗？

4

1 回答 1

2

如果有帮助，我在 Java 中有一个 KD-Tree，它在一个名为 XYZPoint 的内部类中将 XYZ 作为双精度。您可以使用时区数据增加 XYZ 点，并使用 X 表示经度，使用 Y 表示纬度，使用零表示 Z。它至少可以作为一个起点。

然后，您可以使用已经实现的最近邻（欧几里德距离）方法，用于距离某个点最近的时区。

另外.. 为了填充 KD-Tree，维基百科建议使用HeapSort （我的 Java 实现链接）并反复删除中位数。

于 2012-10-01T01:08:58.087 回答