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

Формула изобретения

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

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

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

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

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

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

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

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

9. Способ по п.7, отличающийся тем, что n=3.

10. Способ по п.7, отличающийся тем, что n=4.

11. Способ по п.7, отличающийся тем, что n=6.

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

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

выбирают значение N>2;

упорядочивают все ячейки, на которые разбито изображение, в последовательность таким образом, чтобы для координат (х₁, y₁ ) и (x₂, y₂) любых двух подряд идущих ячеек в этой последовательности выполнялись неравенства |x₁ -x₂| Nd и |y₁-y₂| Nd;

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

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

15. Способ по п.13, отличающийся тем, что n=4, и указанное упорядочение ячеек производят путем формирование N² групп ячеек, где в одну группу относят ячейки, которые имеют одинаковые остатки от деления на N номеров столбцов, в которых расположена каждая из этих двух ячеек, и одинаковые остатки от деления на N номеров строк, в которых расположена каждая из этих двух ячеек, после чего формируют последовательность всех ячеек из первой группы, второй группы и так далее до N²-й группы.

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

17. Способ по п.13, отличающийся тем, что функция F( ) имеет вид F( )=F₁( )+F₂( )+F₃( ), где F₁( ) - штраф за близость маркировочного знака, нанесенного на отрезок , к уже имеющимся маркировочным знакам того же линейного объекта, лежащим в соседних ячейках, F₂( ) - штраф за неоптимальное направление маркировочного знака относительно рамки изображения, F₃( ) - штраф за наличие одинаковых маркировочных знаков разных линейных объектов в соседних ячейках.

Описание изобретения к патенту

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

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

Специфика нанесения надписей горизонталей состоит в том, что надписи горизонталей должны наноситься в разрыве изображения горизонтали вдоль направления горизонтали. Надписи горизонталей следует ориентировать основанием цифр вниз по скату, причем по возможности к южной или восточной рамкам плана. При размещении надписей горизонталей следует исходить из того, что в сочетании с отметками высот они должны обеспечивать быстрое определение высотного положения любой точки плана [Условные знаки для топографических планов масштабов 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( ) штрафа за нанесение маркировочного знака именно в точке, принадлежащей отрезку линейного объекта, и производят выбор очередного места нанесения маркировочного знака в том отрезке линейного объекта, для которого значение функции F( ) принимает минимальное значение, где вид функции F( ) выбирают с учетом конкретной специфики задачи, учитывая при этом, что наличие уже выбранных мест нанесения маркировочных знаков того же объекта в соседней ячейке должно резко ухудшать качество решения. Это обеспечивает достижение технического результата, состоящего в нанесении маркировочных знаков с учетом конкретной специфики задачи.

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

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

Функция F( ) может иметь вид F( )=F₁( )+F₂( )+F₃( ), где F₁( ) - штраф за близость маркировочного знака, нанесенного на отрезок , к уже имеющимся маркировочным знакам того же линейного объекта и за отсутствие маркировочных знаков на других отрезках того же линейного объекта и на отрезках других линейных объектов, попадающих в указанную очередную ячейку, F₂( ) - штраф за неоптимальное направление маркировочного знака относительно рамки изображения, F₃( ) - штраф за наличие одинаковых маркировочных знаков разных линейных объектов в соседних ячейках. Это обеспечивает достижение технического результата, состоящего в получении такой расстановки маркировочных знаков, которая учитывает основные требования к расстановке маркировочных знаков.

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

Изобретение поясняется графическими материалами, где:

Фиг.1. Пример несоответствия направления ската по ЦМР и по оригиналу рельефа.

Фиг.2. Определение направления ската в одной точке

Фиг.3. Изображение горизонталей на оригинале рельефа

Фиг.4. Подмножество размещений маркировочных знаков при n=3.

Фиг.5. Подмножество размещений маркировочных знаков при n=4.

Фиг.6. Подмножество размещений маркировочных знаков при n=6.

Фиг.7. Двудольный граф соответствия при n=3.

Фиг.8. Двудольный граф соответствия при n=4.

Фиг.9. Двудольный граф соответствия при n=6.

Осуществление изобретения

1. Способ нанесения надписей горизонталей на оригинале рельефа

1.1. Общее описание

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

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

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

Для определения направления ската рельефа в окрестностях указанных точек используют информацию о соседних горизонталях. Способ определения направления ската рельефа в окрестностях указанных точек горизонталей с использованием информации о соседних горизонталях является известным и описан в патенте РФ 2308086 (п.6.3 описания). При этом в зависимости от варианта реализации описываемого способа (автоматическое нанесение надписей всех горизонталей или нанесение отдельных надписей) используют либо триангулированную модель всего оригинала рельефа, либо триангулированную модель фрагмента оригинала рельефа вблизи точки постановки нанесения отдельной надписи. Эти варианты описываются ниже в п.1.2 и 1.3 соответственно.

1.2. Автоматическое нанесение надписей горизонталей

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

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

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

Наконец, производят нанесение надписей в местах, являющихся назначенными положениями маркировочных знаков.

1.3. Ручное нанесение надписей горизонталей

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

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

В качестве параметра программы, осуществляющей управление процессом нанесение надписей горизонталей, используют размер d окрестности курсора мыши. Обычно его задают равным 2-10 пикселей экрана дисплея. При щелчке мышью в точку, в окрестности которой надо добавить надпись горизонтали, автоматически находят одну или несколько горизонталей, пересекающих окрестность размера d с центром в точке курсора. Если таких горизонталей несколько, то увеличивают масштаб выдачи изображения, пока не будет достигнута однозначность указания, на какую горизонталь надо добавить надпись. В дальнейшем производят работу именно с этим более крупным масштабом показа. При желании оператор имеет возможность уменьшить масштаб показа изображения. Автоматически вычисляют пересечение горизонтали с указанной окрестностью курсора, и на этом пересечении находят точку минимальной кривизны горизонтали.

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

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

1.4. Ручная корректировка надписей горизонталей

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

1.5. Использование переменного масштаба показа оригинала рельефа

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

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

1.6. Определение направления ската в одной точке

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

Для эффективной реализации нахождения частей горизонталей, попавших внутрь указанного квадрата, используют R-деревья [Шаши Шекхар, Санжей Чаула. Основы пространственных баз данных. - М. Кудиц-образ, 2004, с.130], причем определение всех горизонталей, пересекающих квадрат, сводится к выполнению запроса областей [там же, с.150]. Для точного нахождения частей горизонталей, попавших внутрь указанного квадрата, используют двухэтапную обработку запроса [там же, с.152], причем на этапе фильтрации используют R-деревья, а на этапе очистки перебирают все отрезки ломаной, представляющих данную горизонталь, и для каждого из них вычисляют пересечение с указанным квадратом. После этого объединяют полученные отрезки в ломаные, которые берут в качестве горизонталей обрезанного оригинала рельефа.

Наконец, определяют направление ската в указанной точке максимальной кривизны по указанному обрезанному оригиналу рельефа. Способ определения направления ската рельефа в окрестностях указанных точек горизонталей с использованием информации о соседних горизонталях является известным и описан в патенте РФ 2308086 (п.6.3 описания и п.17 формулы изобретения).

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

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

2.1. Общее описание

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

Назначения положений маркировочных знаков протяженных линейных объектов заданного типа на графическом изображении, включающем в себя множество однотипных линейных объектов, начинают с того, что определяют множество всех возможных размещений маркировочных знаков. В качестве размещений маркировочных знаков используют ячейки, имеющие форму правильных n-угольников со стороной d и расположенные в плоскости изображения. Величину стороны d выбирают таким образом, чтобы площадь многоугольника примерно соответствовала величине площади изображения, приходящейся на один маркировочный знак с учетом заданного диапазона плотности размещения маркировочных знаков на изображении. Другими словами, при идеальном размещении маркировочных знаков на изображении в каждую ячейку должен был бы попасть примерно один маркировочный знак с учетом выбранного диапазона плотности маркировочных знаков. Например, если на 1 дм должно размещаться от 1 до 3 маркировочных знаков, то в качестве площади ячейки можно выбрать любое значение от 1/3 до 1 дм. В качестве числа n сторон правильного многоугольника используют значения 3, 4 или 6, обеспечивающие возможность составить паркетное разбиение плоскости изображения на правильные n-угольники.

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

После того, как выбрано подмножество возможных размещений маркировочных знаков, строят двудольный граф соответствия, который является отделенным и отличным от графических объектов на изображении. В качестве вершин первого уровня этого двудольного графа используют линейные объекты исходного изображения, на которые надо нанести маркировочные знаки, а в качестве вершин второго уровня используют возможные размещения маркировочных знаков, входящие в выбранное подмножество, т.е. вышеуказанные ячейки, являющиеся правильными n-угольниками со стороной d и составляющие паркетное разбиение плоскости изображения. Вершину первого уровня, являющуюся линейным объектом исходного изображения, соединяют в графе ребром с вершиной второго уровня, являющейся ячейкой паркетного разбиения плоскости изображения, в том и только в том случае, если указанный линейный объект пересекается с указанной ячейкой, т.е. полностью или частично попадает в ячейку. В случае растровых изображений для определения пересечений перебирают все пиксели, составляющие данный объект, и определяют, в какую из ячеек он попадает полностью или частично. В случае векторных изображений перебирают все прямолинейные отрезки, составляющие каждый из линейных объектов, и определяют, с какими ячейками они пересекаются. Для этого можно использовать любой из известных способов, например, изложенный в [М. de Berg, M. van Kreveld, M.Overmars, O.Schwarzkoft. Computational Geometry. Algorithms and Applications. Springer-Veriag Berlin Heidelberg, 1997. pp.33-39]. На фиг.7-9 показаны примеры двудольных графов соответствия для рассматриваемого изображения в случае выбора n равным 3, 4 и 6.

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

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

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

2.2. Поиск максимального паросочетания в двудольном графе

В качестве соответствия по возможности большей мощности в указанном двудольном графе соответствия, при котором каждому возможному размещению маркировочного знака соответствует не более одного линейного объекта, может использоваться максимальное паросочетание в указанном двудольном графе. Нахождение максимального паросочетания в двудольном графе может быть выполнено любым известным способом, например с помощью известного алгоритма Форда-Фулкерсона [Кормен Т, Лейзерсон Ч, Ривест Р. Алгоритмы: построение и анализ. М., МЦНМО, 2000, с.242-256].

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

2.3. Поиск паросочетания в двудольном графе с учетом функции штрафа

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

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

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

При n=4 указанное упорядочение ячеек может производиться путем формирование N² групп ячеек, где в одну группу относят ячейки, которые имеют одинаковые остатки от деления на N номеров столбцов, в которых расположена каждая из этих двух ячеек, и одинаковые остатки от деления на N номеров строк, в которых расположена каждая из этих двух ячеек, после чего формируют последовательность всех ячеек из первой группы, второй группы и так далее до N²-й группы.

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

Функция F( ) может иметь вид F( )=F₁( )+F₂( )+F₃( ), где F₁( ) - штраф за близость маркировочного знака, нанесенного на отрезок , к уже имеющимся маркировочным знакам того же линейного объекта и за отсутствие маркировочных знаков на других отрезках того же линейного объекта и на отрезках других линейных объектов, попадающих в указанную очередную ячейку, F( ) - штраф за неоптимальное направление маркировочного знака относительно рамки изображения, F₃( ) - штраф за наличие одинаковых маркировочных знаков разных линейных объектов в соседних ячейках.