@black_list_man

Как эффективно находить общие сегменты полигонов?

Разрабатываю картографический движок для морских навигационных карт. В стандарте указано, что если участки линий друг на друга накладываются (имеют общие сегменты), то участок линии с наименьшим приоритетом (каждая геометрия имеет приоритет) должен быть скрыт. Я не могу понять как это выразить алгоритмически. Первым делом пробовал перебирать все линии, и удалять общие точки, что в корне неверно, т.к оставшиеся точки соединялись и менялась сама геометрия линий. Плюс производительность жуткая: для каждой линии, перебираем все линии и точки... Одна такая линия может содержать 4 тысячи точек. А линий на экране может быть более тысячи.

Проще говоря, необходимо найти и скрыть общие сегменты у полигональной геометрии и сделать это довольно эффективно.

В аналогичном проприетарном софте такой функционал реализован и работает довольно быстро. Наверняка есть какие-то общепринятые решения данной задачи.

Снизу вырезка из стандарта.
5ea9e1efe6fa4141389607.png

Снизу представлен скриншот, на котором видно как линия, обозначающая опасную область (в виде фиолетового паттерна с восклицательным знаком) имеет общие грани с береговой линией и линией причала. Поскольку эти линии имеют больший приоритет, то линия, обозначающая границы области должна быть скрыта в этих сегментах.5eaa9fe03209e875065758.png
  • Вопрос задан
  • 34 просмотра
Пригласить эксперта
Ответы на вопрос 2
trapwalker
@trapwalker
Программист, энтузиаст
В postgis (ГИС-расширени для постгреса) это сделано очень эффективно. Загляните в исходники, они открыты. Ещё я не вижу смысла изобретать дендрофекальный велосипед, когда есть GDAL.
Задача-то не тривиальная. Линии вашей геометрии могут отличаться незначительно, могут не лежать на одних и тех же наборах точек, могут быть разнонаправлены, что порой важно.
Ответ написан
freeExec
@freeExec
Участник OpenStreetMap
На этот случай есть пространственный индекс. Где вы по bbox быстро получаете список входящих в него точек и дальше уже перебираете только их, а не все 4к.
https://blog.mapbox.com/a-dive-into-spatial-search...
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы