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

Question

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

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

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

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

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

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

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

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

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

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

Answer 1

я предлагаю нарушение этого в несколько этапов:

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