Polyline drawMapRect оптимизированный рисунок

Question

У меня есть много длинных полилиний на карте. Я хотел бы оптимизировать их рисование, потому что в нескольких тысячах точек полилинии нарисованы невероятно медленно.

мой drawMapRect выглядит так:

- for each polyline segment 
- verify if it's bounding box intersects the currently drawn MKMapRect
- if id does, draw it

Что здорово, если очков не так много. Но когда есть 8-16 видимых карт и 2-3000 точек, они невероятно медленно проходят через for,

Если бы они были только местоположениями, решение состояло бы в том, чтобы реализовать некую структуру дерева квадрантов / r-деревьев и фильтровать только те местоположения в текущей отрисовке. MKMapRect, но я не уверен в том, будет ли это подходящим для самих полилиний.

Если я отфильтрую только по конечным точкам сегмента внутри текущего maprect, то некоторые отрезки линии могут не отображаться. Например, два красных maprects между точками 1-2 не имеют конечных точек сегмента в них, но все еще должны рисовать...

Есть ли какой-то алгоритм, похожий на квадри, или какой-то подход к этой проблеме?

Answer 1

К сожалению, я не знаю такой структуры данных, которая позволила бы проверить пересечение линии с прямоугольником.
Однако один из подходов к решению проблемы может быть следующим:
Нарисуйте все полилинии на карте с очень низким разрешением (массив 2 dim) и отметьте для каждого пикселя, какая полилиния его нарисовала. Затем отсканируйте в этой карте низкого разрешения соответствующие прямоугольники для нарисованных пикселей и сохраните все соответствующие полилинии. Затем их можно нарисовать на карте полного разрешения.
Возможно, этот приблизительный алгоритм работает быстрее, чем тот алгоритм, который вы используете прямо сейчас.

РЕДАКТИРОВАТЬ:

Я предполагаю, что вы используете для проверки пересечения ломаной линии MKMapRect эффективный алгоритм, такой как показан в разделе Как найти точку пересечения между линией и прямоугольником?,