0

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

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

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

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

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

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

Вот так это должно выглядеть введите сюда описание изображения

8
  • Эээ...Рисовать в порядку увеличения приоритета?
    – MBo
    30 апр 2020 в 4:04
  • Линии -- это прямые? Как они задаются? Что понимается под наложением? 30 апр 2020 в 4:50
  • @MBo нет. По порядку получится только с простыми линиями. Большинство линий имеют сложный паттерн, вроде символов якорей и тд. При наложении будет видно обе линии. 30 апр 2020 в 9:28
  • @hedgehogues Большинство линий задаются полигонами и обозначают границы области. Реже- полилинией (набором точек). 30 апр 2020 в 9:32
  • @PavelSaenko как линии могут задаваться полигонами и точками одновременно? И как они могут задаваться полигонами вообще? 30 апр 2020 в 9:38

1 ответ 1

0

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

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;
                        }

                    }


        }


    }

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.