Отображение подмножества точек долготы / широты?

Question

У меня есть массив координат (широта и долгота), составленный таким образом:

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

В цикле преобразуйте эти координаты в метры (север UTM / восток UTM), и после этого я преобразую эти координаты в пикселях (X / Y) на экране (устройство вывода - iPhone), чтобы нарисовать линию маршрута на пользовательская карта.

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

Возвращаемый пиксель передается методу, который рисует линию на экране (симуляция расчета маршрута).

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

Поскольку координаты (широта / долгота) слишком велики, мне нужно усечь массив широта / долгота, исключив значения, которые не заполняют границы карты (видимая часть карты на экране).
Границы карты - это две пары координат широта / долгота, верхний левый и нижний правый.

Теперь, как лучше всего зацикливаться на этом массиве (НЕ СОРТИРОВАТЬСЯ) и проверять, находится ли значение в границах или нет, и после удаления значения, которое находится снаружи?
Чтобы вернуть чистый массив, содержащий только координаты, видимые на экране?

Примечание: массив координат является очень большим массивом. 4000/5000 Пара предметов.
Это метод, который следует зацикливать при каждом перетаскивании или увеличении.

Как мне оптимизировать поиск и элементы управления в этом массиве?

Answer 1

Я бы предложил разбить это на несколько шагов:

1. Преобразуйте каждую пару долгота / широта в пару метров в вашей новой системе координат.
2. Создайте kd-деревоструктура данных, содержащая все точки в наборе.Это позволяет эффективно запрашивать, какие точки лежат в данном прямоугольном диапазоне.
3. При каждом изменении области просмотра найдите все точки в дереве kd, которые будут отображаться в этом прямоугольнике.
4. Чтобы отобразить точки, выполните итерацию по набору точек, которые будут отображаться, и отобразите каждую из них.