Способ нанесения надписей горизонталей на оригинале рельефа и способ назначения положений маркировочных знаков протяженных линейных объектов заданного типа на графическом изображении

Способ нанесения надписей горизонталей на оригинале рельефа и способ назначения положений маркировочных знаков протяженных линейных объектов заданного типа на графическом изображении

Иллюстрации

Показать все

Реферат

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

Современная технология создания оригинала рельефа предполагает выполнение трех основных этапов: создание машинного рельефа, редактирование горизонталей и оформление оригинала рельефа. Редактирование горизонталей позволяет повысить «читаемость» рельефа за счет искусственной укладки горизонталей по определенным правилам. В частности, подчеркивают точки максимальной кривизны, добиваются соответствия точек максимальной кривизны соседних горизонталей, обеспечивают соответствие горизонталей и элементов гидрографии и т.д. Оформление оригинала рельефа включает в себя, в частности, нанесение надписей горизонталей.

Специфика нанесения надписей горизонталей состоит в том, что надписи горизонталей должны наноситься в разрыве изображения горизонтали вдоль направления горизонтали. Надписи горизонталей следует ориентировать основанием цифр вниз по скату, причем по возможности к южной или восточной рамкам плана. При размещении надписей горизонталей следует исходить из того, что в сочетании с отметками высот они должны обеспечивать быстрое определение высотного положения любой точки плана [Условные знаки для топографических планов масштабов 1:5000, 1:2000, 1:1000, 1:500. - М.: ФГУП «Картгеоцентр», 2004, с.215-216, правило 456].

В [Алчинов А.И, Беклемишев Н.Д, Кекелидзе В.Б. Методы цифровой фотограмметрии. Технология «Талка». Моск. гос. ун.-т печати - М, 2007, с.177-178] (прототип способа нанесения надписей горизонталей на оригинале рельефа) излагается способ нанесения надписей горизонталей на оригинале рельефа, в котором в интерактивном режиме выбирают горизонтали, на которых должны быть нанесены подписи, на этих горизонталях определяют точки, в которых должны быть нанесены надписи, и создают надписи горизонталей, ориентированные в заданном направлении вдоль горизонталей. При этом для обеспечения правильного направления надписей относительно горизонталей, при котором верх цифр должен быть ориентирован вверх по склону, производят согласование направлений горизонталей относительно градиента цифровой модели рельефа (ЦМР) и выбирают направление верха надписей относительно направления горизонталей (вправо или влево).

Недостатком этого способа является использование ЦМР для согласования направления надписей горизонталей, что может приводить к грубым ошибкам при определении направления ската на оригинале рельефа. Тем самым указанный способ является ненадежным. Поясним это утверждение на примере ЦМР и оригинала рельефа, которые изображены на фиг.1. Для определенности будем предполагать, что масштаб равен 1:1000, т.е. при редактировании горизонталей при построении оригинала рельефа каждую из них можно смещать на расстояние, составляющее 1/4 заложения рельефа на составляемом плане [«Инструкция по топографической съемке в масштабах 1:5000, 1:2000, 1:1000 и 1:500». ГКИНП-02-033-79. Москва, «Недра», 1982, с.101, п.20.4]. На фиг.1 приведено трехмерное изображение поверхности рельефа в системе координат Oxyz, где х, у - плановые координаты, z - высота. На переднем плане штриховкой показано сечение рельефа вертикальной плоскостью Oxz. Предполагается, что возвышение точки М локального максимума высоты рельефа над сечением АС рельефа меньше 1/4 заложения рельефа. Здесь АВ - исходная горизонталь, построенная по ЦМР, A₁B₁ - преобразованная горизонталь АВ, полученная в результате правки горизонталей при построении оригинала рельефа. Кроме того, изображены горизонталь CD той же высоты, что и горизонталь АВ, и две горизонтали EF и GH, имеющие меньшую высоту, чем горизонталь АВ. В этом примере предполагается, что вблизи оси Ох горизонтали проходят параллельно оси Оу. Пунктирными линиями на заштрихованном сечении изображены уровни высоты, соответствующие заданной высоте сечения рельефа. Для горизонтали A₁B₁ согласно ЦМР направление ската совпадает с положительным направлением оси х. В то же время на оригинале рельефа горизонтали A₁B₁ и CD лежат между горизонталями EF и GH, имеющими меньшую высоту. Отсюда следует, что на оригинале рельефа при движении от горизонтали EF к горизонтали A₁B₁ происходит повышение рельефа, т.е. согласно оригиналу рельефа направление ската совпадает с отрицательным направлением оси х. Таким образом, направление ската, полученное по оригиналу рельефа, не совпадает с направлением ската, полученным по ЦМР.

В предлагаемом ниже способе нанесения надписей горизонталей на оригинале рельефа используется способ определения мест нанесения надписей характеристик протяженных линейных объектов на изображении, каковыми, в частности, являются горизонтали. Как было указано выше, специфика нанесения надписей горизонталей состоит в том, что надписи горизонталей должны наноситься в разрыве изображения горизонтали вдоль направления горизонтали. Этим же свойством (возможно, без разрыва условного знака линейного объекта) обладают надписи характеристик линейных объектов многих других типов, включая названия улиц [Условные знаки для топографических планов масштабов 1:5000, 1:2000, 1:1000, 1:500. - М.: ФГУП «Картгеоцентр», 2004, с.252, правило 606], ширину морских эстакад [там же, с.23, знак 100], число прокладок и индексы напряжения электрокабелей [там же, с.28, знак 119], индексы назначения наземных, подземных, надводных и подводных трубопроводов [там же, с.29-30, знаки 121-122, с.32, знаки 130-131], пояснительные надписи канализации ливневой открытой [там же, с.31, знак 129], пояснительные надписи и ширина колеи узкоколейных железных дорог [там же, с.36, знак 158], характеристики линейных автомобильных дорог [там же, с.42, знаки 191, 192], ширина линейных скотопрогонов [там же, с.42, знак 196], надписи изобат [там же, с.52, знак 234], и т.д.

Задача определения мест нанесения надписей характеристик протяженных линейных объектов может рассматриваться как частный случай задачи размещения маркировочных знаков линий. Приведем основные понятия и терминологию в этой области, следуя описанию патента США 6,091,424.

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

В данном описании термин «маркирующий знак» ("label") означает текст или другой указатель, который должен быть нанесен на рисунок (drawing). Термин «размещение маркировочного знака» ("label placement") означает одну или несколько выбранных областей, внутри которых может быть размещен маркировочный знак.

Термин «назначение положения» ("label assignment") означает выбранное размещение маркировочного знака. Наконец, термин «вариант маркировки» ("labeling solution") означает набор назначений положения для многих маркировочных знаков, такой, что назначения положений удовлетворяют определенному критерию.

В общей задаче размещения маркировочных знаков для деталей рисунков (GFLP - Graph Feature Label Problem) применительно к картографии выделяются две более частные задачи: задача размещения маркировочных знаков линий (ELP - Edge Label Placement) и задача размещения маркировочных знаков точек (PLP - Point Label Placement). Задача ELP является менее ограничительной по сравнению с задачей PLP ввиду того, что линии обычно являются длинными, что обеспечивает много возможных мест для размещения маркирующих знаков. При этом плотность линий может сильно варьироваться. Поэтому способы размещения маркировочных знаков линий, чтобы быть практичными, должны хорошо работать и в условиях очень высокой плотности линий. Известно, что задача ELP является NP-трудной, и тем самым любое решение задачи размещения маркировочных знаков линий должно основываться на использовании определенных эвристик, обеспечивающих не оптимальное, но приемлемое по качеству решение.

Известно несколько способов назначения положений маркировочных знаков протяженным линейным объектам на графическом изображении.

В патенте США 6,091,424, 18.07.2000 приор. 1.11.1996 (прототип способа назначения положений маркировочных знаков протяженным линейным объектам на графическом изображении), предложен способ назначения положений маркировочных знаков (labels) протяженным линейным объектам на графическом изображении, включающем в себя множество однотипных линейных объектов, при котором строят множество всех возможных размещений маркировочных знаков, выбирают подмножество возможных размещений маркировочных знаков в множестве всех возможных размещений маркировочных знаков, представляют графические объекты и возможные размещения маркировочных знаков вершинами двудольного графа соответствия, отделенного и отличного от графических объектов, и находят соответствие по возможности большей мощности в указанном двудольном графе соответствия, при котором каждому возможному размещению маркировочных знаков соответствует не более одного линейного объекта. При этом в качестве положений в качестве возможных размещений маркировочных знаков используют области, которые реально могут занимать маркировочные знаки на изображении, а в качестве подмножества возможных размещений маркировочных знаков выбирают некоторую совокупность возможных размещений, в которой никакие два различных возможных размещения не пересекаются. Недостатком этого способа является то, что он не обеспечивает равномерности положений маркировочных знаков на изображении в целом, что является следствием использования в качестве возможных размещений маркировочных знаков областей, которые реально занимают маркировочные знаки на изображении. В случае маркировочных знаков небольшого размера вполне может оказаться допустимой ситуация, когда множество маркировочных знаков будет сконцентрировано в каком-то одном месте.

В патенте США 5,988,853 предложен способ расстановки маркирующих знаков, использующий заметание плоскости, а в заявке US 2006/0058949 предложен способ, использующий алгоритм модельной «закалки» (simulated annealing) и/или алгоритм модельного тушения (simulated quenching). Эти способы также не обеспечивают отсутствие скоплений маркировочных знаков малых размеров в окрестности какой-либо точки.

В патенте США 6,154,219, 28.11.2000 предложен способ рисовки объектов карты и связанных с ними маркировочных знаков, содержащий шаги:

составление списка объектов карты, которые должны быть потенциально показаны на карте, где объекты карты включают в себя точечные объекты и объекты, не являющиеся точечными, причем каждый объект включает в себя связанный с ним маркировочный знак, который может быть расположен во множестве потенциальных мест расположения маркировочных знаков;

приписывание приоритета выбора маркировочных знаков каждому объекту из списка;

упорядочение объектов из списка в порядке приоритетов;

рисовка объектов из списка, не являющихся точечными, на представлении карты;

выбор точечных объектов, маркировочных знаков, связанных с точечными объектами, и маркировочных знаков, связанных с объектами, не являющимися точечными, для рисовки на представлении карты, путем выполнения подшагов:

a) извлечение выбранного объекта из списка в порядке приоритетов;

b) если маркировочный знак, связанный с выбранным объектом, может быть помещен в одно или несколько потенциальных мест расположения маркировочного знака для выбранного объекта, не вызывая конфликтов с каким-либо объектом, имеющим более высокий приоритет, или со связанным с ним маркировочным знаком, рисовка маркировочного знака для выбранного объекта на представлении карты в одном из этих мест расположения, а если объект является точечным объектом, то и рисовка объекта на представлении карты;

c) если маркировочный знак, связанный с выбранным объектом, не может быть помещен ни в одно из потенциальных мест расположения маркировочных знаков для выбранного объекта, не вызывая конфликтов с каким-либо объектом, имеющим более высокий приоритет, или со связанным с ним маркировочным знаком, удаление выбранного объекта из первого списка;

d) если маркировочный знак, связанный с выбранным объектом, оказался нарисован, определение, имеется ли конфликт между маркировочным знаком и одним или несколькими объектами, имеющими более низкий приоритет, и при наличии конфликта удаление объектов, вовлеченных в конфликт и имеющих более низкий приоритет, из списка;

e) повторение шагов а)-d), пока не будут нарисованы маркировочные знаки для всех объектов, оставшихся в списке.

Кроме того, в патенте США 6,154,219, 28.11.2000 предложен способ рисовки объектов карты и связанных с ними маркировочных знаков, содержащий шаги:

составление первого списка объектов карты, которые должны быть потенциально показаны на карте, где объекты карты включают в себя точечные объекты и объекты, не являющиеся точечными, причем каждый объект включает в себя связанный с ним маркировочный знак, который может быть расположен во множестве потенциальных мест расположения маркировочных знаков;

приписывание приоритета выбора маркировочного знака каждому объекту из списка;

упорядочение объектов из первого списка в порядке приоритетов;

составление второго списка, включающего в себя выбранные точечные объекты из первого списка;

создание взвешенного массива конфликтов, соответствующего объектам из второго списка и включающего в себя штраф для каждого объекта из второго списка, и если имеется несколько потенциальных положений маркировочных знаков для выбранного объекта, определение, имеются ли конфликты, и:

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

рисовка маркировочного знака для выбранного объекта в положении, имеющем наименьшее значение назначенного штрафа;

выбор точечных объектов, маркировочных знаков, связанных с точечными объектами, и маркировочных знаков, связанных с объектами, не являющимися точечными, для рисовки на представлении карты, путем выполнения подшагов:

a) извлечение выбранного объекта из списка в порядке приоритетов;

b) если имеется несколько потенциальных положений маркировочных знаков для выбранного объекта, не вызывающих конфликтов с объектами, имеющими более высокий приоритет, или со связанными с ними маркировочными знаками, определение, имеются ли конфликты между многими потенциальными положениями маркировочных знаков и объектами, имеющими более низкие приоритеты, и при наличии таких конфликтов;

c) если маркировочный знак, связанный с выбранным объектом, не может быть помещен ни в одно из потенциальных мест расположения маркировочных знаков для выбранного объекта, не вызывая конфликтов с каким-либо объектом, имеющим более высокий приоритет, или со связанным с ним маркировочным знаком, удаление выбранного объекта из первого и второго списков;

d) если маркировочный знак, связанный с выбранным объектом, оказался нарисован, определение, имеется ли конфликт между ярлыком и одним или несколькими объектами, имеющими более низкий приоритет, и при наличии конфликта удаление объектов, вовлеченных в конфликт и имеющих более низкий приоритет, из списка;

e) повторение шагов а)-d), пока не будут нарисованы маркировочные знаки для всех объектов, оставшихся в списке.

В заявке US 2004/0252137, 16.12.2004 предложен способ нанесения маркировочных знаков на карту, содержащий шаги:

извлечение связи каждого маркировочного знака с соответствующим объектом (target feature) на карте безотносительно к другим маркировочным знакам или объектам;

извлечение свойств объектов карты;

извлечение свойств маркировочных знаков;

помещение (pulling) маркировочных знаков в пределах рамки карты;

упорядочение маркировочных знаков по убыванию приоритета;

проверка каждого маркировочного знака на пересечение с другими маркировочными знаками;

перемещение маркировочных знаков, пересекающихся с другими маркировочными знаками, в положения, где они не пересекаются с другими маркировочными знаками;

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

вычисление функции оценки;

настройка свойств маркировочных знаков.

Кроме того, в заявке US 2004/0252137, 16.12.2004 предложен способ перемещения в данной двумерной плоскости планарных объектов, представляющих выпуклые многоугольники и пересекающих другие планарные объекты, представляющие выпуклые многоугольники, где определенный выпуклый многоугольник можно перемещать в любом направлении в плоскости карты в положение, где он не имеет пересечений, включающий в себя:

приписывание выпуклому многоугольнику с более высоким приоритетом названия первого многоугольника, а выпуклому многоугольнику с более низким приоритетом - названия второго выпуклого многоугольника,

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

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

(c) помещение самого длинного вектора и его длины, получающихся в результате повторения шагов (а) и (b), в структуру данных карты;

(d) сортировка структуры данных карты по длине векторов;

(e) выбор самого короткого непроверенного вектора из структуры данных карты;

(f) установка первого флага, второго флага и третьего флага в значение PASS;

(g) установка первого флага в FAIL, если перемещение второго выпуклого многоугольника в обоих направлениях на длину самого короткого непроверенного вектора в новое положение перемещает второй выпуклый многоугольник на расстояние, большее выбранного максимального допустимого отклонения второго выпуклого многоугольника от исходного положения;

(h) повторение шагов (е)-(h), если первый флаг установлен в FAIL;

(i) установка второго флага в FAIL, если перемещение второго выпуклого многоугольника перемещает часть второго выпуклого многоугольника за пределы рамки карты;

(j) повторение шагов (е)-(j), если второй флаг установлен в FAIL;

(k) установка третьего флага в FAIL, если перемещение второго выпуклого многоугольника вызывает пересечение второго выпуклого многоугольника с каким-либо выпуклым многоугольником с приоритетом, большим или равным приоритету первого выпуклого многоугольника;

(l) повторение шагов (е)-(l), если третий флаг установлен в FAIL;

перемещение второго маркировочного знака в новое положение, если первый флаг, второй флаг и третий флаг установлены в значение PASS;

установка параметра окончательного положения второго выпуклого многоугольника из списка параметров второго выпуклого многоугольника в новое положение, если первый флаг, второй флаг и третий флаг установлены в значение PASS.

Кроме того, в заявке US 2004/0252137, 16.12.2004 предложен способ перемещения в данной двумерной плоскости планарных объектов, представляющих выпуклые многоугольники и пересекающих другие планарные объекты, представляющие выпуклые многоугольники, где определенный выпуклый многоугольник можно перемещать в направлении вдоль вектора в плоскости карты в положение, где он не имеет пересечений, включающий в себя:

приписывание выпуклому многоугольнику с более высоким приоритетом названия первого выпуклого многоугольника, а выпуклому многоугольнику с более низким приоритетом - названия второго выпуклого многоугольника,

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

(b) нахождение самого длинного из векторов, параллельных выбранному вектору направления перемещения, с началом на линии, содержащей сторону второго выпуклого многоугольника (если сторона не параллельна выбранному вектору направления перемещения) и концом в каждой вершине первого выпуклого многоугольника (если вершина находится на внутренней стороне линии, содержащей сторону), что гарантирует отсутствие пересечения между первым и вторым выпуклыми многоугольниками при сдвиге второго выпуклого многоугольника в обоих направлениях на длину самого длинного вектора;

(c) помещение самого длинного вектора и его длины, получающихся в результате повторения шагов (а) и (b), в структуру данных карты;

(d) сортировка структуры данных карты по длине векторов;

(e) выбор самого короткого непроверенного вектора из структуры данных карты;

(f) установка первого флага, второго флага и третьего флага в значение PASS;

(g) установка первого флага в FAIL, если перемещение второго выпуклого многоугольника в обоих направлениях на длину самого короткого непроверенного вектора в новое положение перемещает второй выпуклый многоугольник на расстояние, большее выбранного максимального допустимого отклонения второго выпуклого многоугольника от исходного положения;

(h) повторение шагов (е)-(h), если первый флаг установлен в FAIL;

(i) установка второго флага в FAIL, если перемещение второго выпуклого многоугольника перемещает часть второго выпуклого многоугольника за пределы рамки карты;

(j) повторение шагов (е)-(j), если второй флаг установлен в FAIL;

(k) установка третьего флага в FAIL, если перемещение второго выпуклого многоугольника вызывает пересечение второго выпуклого многоугольника с каким-либо выпуклым многоугольником с приоритетом, большим или равным приоритету первого выпуклого многоугольника;

(l) повторение шагов (е)-(l), если третий флаг установлен в FAIL;

перемещение второго выпуклого многоугольника в новое положение, если первый флаг, второй флаг и третий флаг установлены в значение PASS;

установка параметра окончательного положения второго выпуклого многоугольника из списка параметров второго выпуклого многоугольника в новое положение, если первый флаг, второй флаг и третий флаг установлены в значение PASS.

Недостатком этих способов является использование приоритетов, что не позволяет эффективно использовать эти способы в ситуациях, когда все объекты имеют примерно однородную природу, и назначение приоритетов является чем-то искусственным. Кроме того, в этих способах контролируется только отсутствие пересечений между маркировочными знаками, но не обеспечивается отсутствие скоплений маркировочных знаков малых размеров в окрестности какой-либо точки.

В заявке WO 2002/029726, 11.04.2002 предложен способ размещения маркировочных знаков среди графических элементов на графическом дисплее компьютера, содержащий шаги:

идентификация по крайней мере одного кластера пересекающихся маркировочных знаков и графических элементов;

вычисление новых координат показа для по крайней мере одного маркировочного знака из указанного кластера;

перемещение указанного маркировочного знака в положение с указанными новыми координатами показа.

Кроме того, в заявке WO 2002/029726, 11.04.2002 предложен способ размещения маркировочных знаков среди графических элементов на графическом дисплее компьютера, содержащий шаги:

последовательный выбор маркировочных знаков из множества маркировочных знаков на дисплее;

проверка каждого из указанных выбранных маркировочных знаков на пересечение с другими маркировочными знаками и графическими элементами на дисплее;

накопление числа очков за пересечения для каждого из указанных маркировочных знаков;

порождение списка других маркировочных знаков и графических элементов, которые пересекают каждый из указанных выбранных маркировочных знаков;

сравнение множества указанных списков и накопление списков кластеров пересекающихся маркировочных знаков и графических элементов;

сортировка множества указанных списков кластеров по числу элементов в них;

вычисление новых координат показа для по крайней мере одного маркировочного знака из указанного кластера;

сравнение на покластерной основе степени пересечения маркировочных знаков и графических элементов с новыми координатами показа и существующей степени пересечения маркировочных знаков и графических элементов;

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

В этих способах также контролируется только отсутствие пересечений между маркировочными знаками, но не обеспечивается отсутствие скоплений маркировочных знаков малых размеров в окрестности какой-либо точки.

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

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

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

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

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

Уточнение последних двух вариантов способа состоит в том, что для определения направления ската в точке минимальной кривизны строят квадрат со сторонами, параллельными рамке оригинала рельефа, центр которого расположен в указанной точке минимальной кривизны, а сторона равна удвоенному диаметру указанной окрестности. Находят части горизонталей, попавших внутрь указанного квадрата, и строят обрезанный оригинал рельефа из полученных частей горизонталей. Определяют направление ската в указанной точке максимальной кривизны по указанному обрезанному оригиналу рельефа. Если информации на обрезанном оригинале рельефа оказывается недостаточно для определения направления ската, увеличивают размер стороны квадрата вдвое и повторяют указанные действия, пока не будет получено искомое направления ската или не будет исчерпан весь оригинал рельефа. Это обеспечивает достижение технического результата, состоящего в существенном снижении времени получения результата за счет уменьшения объема обрабатываемых данных.

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

Решение поставленной задачи назначения положений маркировочных знаков протяженных линейных объектов заданного типа на графическом изображении, включающем в себя множество однотипных линейных объектов, достигается за счет того, что определяют множество всех возможных размещений маркировочных знаков, выбирают подмножество возможных размещений маркировочных знаков в множестве всех возможных размещений маркировочных знаков, представляют графические объекты и возможные размещения маркировочных знаков вершинами двудольного графа соответствия, отделенного и отличного от графических объектов, и находят соответствие по возможности большей мощности в указанном двудольном графе соответствия, при котором каждому возможному размещению маркировочного знака соответствует не более одного линейного объекта. В отличие от прототипа, выбирают размер d стороны ячейки, имеющей форму правильного n-угольника, таким образом, чтобы в каждую ячейку должен был бы попасть примерно один маркировочный знак с учетом выбранного диапазона плотности маркировочных знаков. Определяют указанное множество всех возможных размещений маркировочных знаков как множество всех правильных n-угольников со стороной d. Для выбора указанного подмножества разбивают площадь изображения на примыкающие друг к другу ячейки, являющиеся правильными n-угольниками со стороной d, оставляя, при необходимости, не покрытые ячейками поля по границе изображения, ширина которых меньше половины выбранного размера стороны ячейки, и в качестве указанного подмножества в множестве всех возможных размещений маркировочных знаков используют множество всех указанных n-угольных ячеек. Это обеспечивает достижение технического результата, состоящего в равномерности положений маркировочных знаков на изображении в целом и предотвращении ситуации, когда множество маркировочных знаков будет сконцентрировано в каком-то одном месте.

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

В качестве значений числа сторон n правильных n-угольников могут использоваться значения 3, 4 и 6.

В качестве соответствия по возможности большей мощности в указанном двудольном графе соответствия, при котором каждому возможному размещению маркировочного знака соответствует не более одного линейного объекта, может использоваться максимальное паросочетание в указанном двудольном графе. Это обеспечивает достижение технического результата, состоящего в нанесении максимального числа маркировочных знаков, при котором никакие два маркировочных знака не попадают в одну и ту же ячейку, т.е. отсутствуют скопления маркировочных знаков на изображении.

Для нахождения в указанном двудольном графе соответствия по возможности большей мощности, при котором каждому возможному размещению маркировочного знака соответствует не более одного линейного объекта выбирают значение N>2, упорядочивают все ячейки, на которые разбито изображение, в последовательность таким образом, чтобы для координат (x₁, y₁) и (x₂, y₂) любых двух подряд идущих ячеек в этой последовательности выполнялись неравенства |х₁-х₂|≥Nd и |y₁-y₂|≥Nd и последовательно перебирают все ячейки в установленном на предыдущем шаге порядке, и для каждой очередной ячейки находят все указанные линейные объекты, пересекающие указанную очередную ячейку, находят пересечения всех таких объектов с площадью ячейки, представляющие собой наборы отрезков линий, для каждого такого отрезка Δ линейного объекта вычисляют значение функции F(Δ) штрафа за нанесение маркировочного знака именно в точке, принадлежащей отрезку Δ линейного объекта, и производят выбор очередног