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

Question

[black_list_man]

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

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

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

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


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

Answer 1

[Сергей П]

В postgis (ГИС-расширени для постгреса) это сделано очень эффективно. Загляните в исходники, они открыты. Ещё я не вижу смысла изобретать дендрофекальный велосипед, когда есть GDAL.
Задача-то не тривиальная. Линии вашей геометрии могут отличаться незначительно, могут не лежать на одних и тех же наборах точек, могут быть разнонаправлены, что порой важно.

Answer 2

[freeExec]

На этот случай есть пространственный индекс. Где вы по bbox быстро получаете список входящих в него точек и дальше уже перебираете только их, а не все 4к.
https://blog.mapbox.com/a-dive-into-spatial-search...