algorithm - 显示经度/纬度点的子集？

Question

我有一个以这种方式制作的坐标(纬度和经度)数组:

[0] = "45.01234,9.12345"
[1] = "46.11111,9.12345"
[2] = "47.22222,9.98765"
[...] etc

在循环中，将这些坐标转换为米(UTM 北距/UTM 东距)，然后我将这些坐标转换为屏幕上的像素 (X/Y)(输出设备是 iPhone)以在自定义 map 。

[0] = "512335.00000,502333.666666"
[...] etc

返回的像素被传递给在屏幕上画线的方法(模拟路线计算)。

[0] = "20,30"
[1] = "21,31"
[2] = "25,40"
[...] etc

由于坐标(纬度/经度)太多，我需要截断纬度/经度数组以消除未填充 map 边界(屏幕上 map 的可见部分)的值。
map 边界是 2 对坐标纬度/经度、左上角和右下角。

现在，循环此数组(未排序)并检查值是否在边界内并在删除外部值后的最佳方法是什么？
要返回一个只包含屏幕上可见坐标的干净数组？

注意:坐标数组是一个非常大的数组。 4000/5000 两件。
这是一个应该在每次拖动或缩放时循环的方法。

如何优化此数组中的搜索和控件？

Answer 1

我建议将其分成几个步骤:

1. 将每个经度/纬度对转换为新坐标系中的一对米。
2. 创建一个包含集合中所有点的 kd-tree 数据结构。这使您可以非常有效地查询哪些点位于给定的矩形范围内。
3. 每当视口(viewport)发生变化时，找到将在该矩形中显示的 kd 树中的所有点。
4. 要显示点，遍历将要显示的点集并显示每个点。