Эффективный алгоритм поиска общих сегментов полигональной геометрии
Разрабатываю картографический движок для морских навигационных карт. В стандарте указано, что если участки линий друг на друга накладываются (имеют общие сегменты), то участок линии с наименьшим приоритетом (каждая геометрия имеет приоритет) должен быть скрыт. Я не могу понять как это выразить алгоритмически. Первым делом пробовал перебирать все линии, и удалять общие точки, что в корне неверно, т.к оставшиеся точки соединялись и менялась сама геометрия линий. Плюс производительность жуткая: для каждой линии, перебираем все линии и точки... Одна такая линия может содержать 4 тысячи точек. А линий на экране может быть более тысячи.
Проще говоря, необходимо найти и скрыть общие сегменты у полигональной геометрии и сделать это довольно эффективно.
В аналогичном проприетарном софте такой функционал реализован и работает довольно быстро. Наверняка есть какие-то общепринятые решения данной задачи.
Снизу вырезка из стандарта.
Снизу представлен скриншот, на котором видно как линия, обозначающая опасную область (в виде фиолетового паттерна с восклицательным знаком) имеет общие грани с береговой линией и линией причала. Поскольку эти линии имеют больший приоритет, то линия, обозначающая границы области должна быть скрыта в этих сегментах.
Вот так это должно выглядеть
Ответы (1 шт):
Я разобрался. Необходимо было пройтись по всей геометрии и создать хэш-словарь с сегментом (две точки отрезка) в качестве ключа и массивом с указателями на геометрию, которой принадлежит этот сегмент - в качестве значения. Таким образом получилось однозначно определить скольким полигонам принадлежит каждый сегмент. Затем надо снова пройтись по всей геометрии, и ее сегментам. По словарю, который мы создали в предыдущем пункте, получаем массив геометрии, которому этот отрезок тоже принадлежит. Смотрим, есть ли в этом списке геометрия с бОльшим приоритетом чем текущая, ели да, то отмечаем данный отрезок как игнорируемый. Для того чтобы хранить информацию об игнорируемых отрезках, я использую массив булевых значений, где индекс в массиве соответствует номеру сегмента. В виде кода это выглядит так:
struct Edge {
QPointF a,b;
};
// Создаем и заполняем хэш-карту всех имеющихся сегментов
QMultiHash<Edge, S57Feature*> sharedEdges;
for (const auto feature: chart->features) {
for (int i = 0; i < feature->pt.size(); i++) {
Edge edge {feature->pt[i],feature->pt[i+1]};
sharedEdges.insert(edge,feature);
}
}
// Проверяем совпадает ли каждый сегмент с другой геометрией более высокого приоритета
for (const auto feature: chart->features) {
feature->suppressed_edges.resize(feature->npts());
for (int i = 0; i < feature->pt.size(); i++) {
Edge edge {feature->pt[i],feature->pt[i+1]};
auto values = sharedEdges.values( edge );
for (const auto v : values) {
if (v->order > feature->order){
feature->suppressed_edges[i] = true;
break;
}
}
}
}