СПОСОБ РАССТАНОВКИ БЕРГШТРИХОВ НА ОРИГИНАЛЕ РЕЛЬЕФА, КОМПЬЮТЕРНЫЙ СПОСОБ РАСПОЗНАВАНИЯ НА ОРИГИНАЛЕ РЕЛЬЕФА ЧАСТЕЙ ГОРИЗОНТАЛЕЙ, ПРОХОДЯЩИХ ЧЕРЕЗ ОБЛАСТИ С МАЛЫМИ УКЛОНАМИ, И КОМПЬЮТЕРНЫЙ СПОСОБ РАСПОЗНАВАНИЯ МИНИМАЛЬНЫХ КОНТУРОВ, СОСТАВЛЕННЫХ ГОРИЗОНТАЛЯМИ И РАМКОЙ ОРИГИНАЛА РЕЛЬЕФА Российский патент 2009 года по МПК G06T17/50 G01C11/00 

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

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

В [Алчинов А.И, Беклемишев Н.Д, Кекелидзе В.Б. Методы цифровой фотограмметрии. Технология «Талка». Моск. гос. ун-т печати. - М., 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, где x, y - плановые координаты, z - высота. На переднем плане штриховкой показано сечение рельефа вертикальной плоскостью Oxz. Предполагается, что возвышение точки М локального максимума высоты рельефа над сечением АС рельефа меньше 1/4 заложения рельефа. Здесь АВ - исходная горизонталь, построенная по ЦМР, A₁B₁ - преобразованная горизонталь АВ, полученная в результате правки горизонталей при построении оригинала рельефа. Кроме того, изображены горизонталь CD той же высоты, что и горизонталь АВ, и две горизонтали EF и GH, имеющие меньшую высоту, чем горизонталь АВ. В этом примере предполагается, что вблизи оси Ох горизонтали проходят параллельно оси Оy. Пунктирными линиями на заштрихованном сечении изображены уровни высоты, соответствующие заданной высоте сечения рельефа. Для горизонтали A₁B₁ согласно ЦМР направление ската совпадает с положительным направлением оси x. В то же время на оригинале рельефа горизонтали A₁B₁ и CD лежат между горизонталями EF и GH, имеющими меньшую высоту. Отсюда следует, что на оригинале рельефа при движении от горизонтали EF к горизонтали A₁B₁ происходит повышение рельефа, т.е. согласно оригиналу рельефа направление ската совпадает с отрицательным направлением оси х. Таким образом, направление ската, полученное по оригиналу рельефа, не совпадает с направлением ската, полученным по ЦМР.

Предлагаемый ниже способ автоматической расстановки бергштрихов на оригинале рельефа использует, в частности, определение частей горизонталей, проходящих через области с малым уклоном рельефа. В [Геоинформационная система "КАРТА 2005". Обработка матриц и TIN-моделей. Руководство пользователя. Редакция 2.1. Панорама 1991-2006. - Ногинск. - www.gisinfo.ru (прототип способа распознавания на оригинале рельефа частей горизонталей, проходящих через области с малыми уклонами)] излагается способ распознавания на оригинале рельефа частей горизонталей, проходящих через области с малым уклонами, при котором выбирают пороговое значение уклона и определяют части горизонталей, проходящие через области, в которых величина уклона рельефа меньше указанного порогового значения. При этом для определения величины уклона рельефа используют градиент ЦМР, заданной в виде матрицы высот, которую строят по контурам карты с 3D-метрикой или по оригиналу рельефа. Для этого используют программные функции «Создать матрицу» (см. стр.6) и «Определение уклона поверхности по матрице высот» (стр.11).

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

В случае применения ЦМР, построенной по оригиналу рельефа, также могут возникать ошибки при определении уклона рельефа. В качестве примера рассмотрим картину горизонталей, приведенную на фиг.3. В этом случае треугольники 1-3 являются горизонтальными, и использование интерполяции высот контуров, являющихся горизонталями рельефа, дает одно и то же значение высоты 100 для всех точек матрицы высот, попадающих внутрь этих трех треугольников. С другой стороны, внутри треугольника 6 получаются значения точек матрицы высот с большим значением градиента высот. Однако в реальности рельеф при перемещении от треугольника 10 к треугольнику 1 имеет довольно плавный спуск, который оказывается сильно искаженным при использовании метода интерполяции. Именно по этой причине в большинстве ГИС считается, что для решения задач, связанных с рельефом, одного оригинала рельефа не достаточно, и надо еще иметь матрицу высот (см., например, [патент США 5839090, колонка 8, последнее предложение 4-го абзаца снизу]).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фиг.2 - пример несоответствия величины уклона, определяемой по ЦМР и по оригиналу рельефа.

Фиг.3 - распознавание частей горизонталей, проходящих через области с малыми уклонами.

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

Фиг.5 - неориентированный граф для распознавания частей горизонталей, проходящих через области с малыми уклонами.

Фиг.6 - определение минимальных контуров, составленных горизонталями и рамкой оригинала рельефа.

Фиг.7 - два варианта неориентированного графа для определения минимальных контуров, составленных горизонталями и рамкой оригинала рельефа.

Фиг.8 - доказательство связности подграфа М.

Фиг.9 - триангуляция по множеству вершин ломаных.

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

Фиг.11 - триангуляции выпуклых многоугольников, на которые разбивается треугольник исходной триангуляции горизонталями и рамкой оригинала рельефа.

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

1. Способ расстановки бергштрихов

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

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

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

Далее для каждой из полученных точек на горизонталях определяют направление перпендикуляра к горизонтали и направление ската рельефа, после чего проводят бергштрих, являющийся отрезком прямой линии заданной длины, первый конец которого расположен в указанной полученной точке, а другой конец лежит на указанном перпендикуляре и смещен от указанного первого конца в направлении ската. Согласно нормативным документам длина бергштриха в масштабе плана или карты должна быть равна 1 мм (см. [Условные знаки для топографических планов масштабов 1:5000, 1:2000, 1:1000, 1:500. М.: ФГУП «Картгеоцентр», 2004, с.79, знак 329 (6)], [Условные знаки для топографической карты масштаба 1:10000. М.: Недра, 1977, с.37, знак 285]) или 0,6 мм [Условные знаки для топографических карт масштабов 1:200000 и 1:500000. Военно-топографическое управление генерального штаба. М., 1983, с.38, правило 34].

При определении направления перпендикуляра к горизонтали в данной точке учитывают масштаб плана или карты. Дело в том, что реальные горизонтали являются кривыми линиями, которые на цифровой карте представлены как ломаные. При отображении на дисплее или печати в соответствующем карте масштабе такая ломаная воспринимается как гладкая кривая линия, поскольку мелкие детали не распознаются и эта ломаная строится так, чтобы давать соответствующее приближение горизонтали. Эту же идею - игнорировать мелкие детали - используют при определении нормали к горизонтали в данной точке. А именно, направлением нормали в данной точке горизонтали считают направление, перпендикулярное отрезку, соединяющему точки, отстоящие от данной на k в миллиметрах карты при следовании вдоль ломаной в направлении ломаной и против ее направления. Здесь k не зависит от горизонтали и масштаба, на практике хороший результат дает значение k=0,5.

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

1.2. Автоматическая расстановка бергштрихов

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

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

Выбор горизонталей, на которых должны быть поставлены бергштрихи, определяется нормативными требованиями, согласно которым бергштрихи должны наноситься на горизонтали, воспроизводящие вершины, котловины и седловины, участки с малыми уклонами и затруднительные для чтения рельефа, а также у рамок плана или карты (см. [Условные знаки для топографических планов масштабов 1:5000, 1:2000, 1:1000, 1:500. М.: ФГУП «Картгеоцентр», 2004, с.215, правило 455], [Условные знаки для топографической карты масштаба 1:10000. М.: Недра, 1977, с.103, правило 167]). Чтобы удовлетворить этим требованиям, среди всех горизонталей определяют: минимальные замкнутые горизонтали, не охватывающие никаких других горизонталей; участки горизонталей в окрестности седловин; участки горизонталей, проходящие через области с малыми уклонами, а также минимальные контура, составленные горизонталями и рамкой плана (карты). Способ определения минимальных замкнутых горизонталей является известным и описан в патенте РФ 2308086 (п.3 описания и п.11 формулы изобретения). Способ определения участков горизонталей, проходящих через области с малыми уклонами, описывается ниже в п.2. Способ определения участков горизонталей в окрестности седловин является известным и описан в патенте РФ 2308086 (п.5 описания и п.19 формулы изобретения). Способ определения минимальных контуров, составленных горизонталями и рамкой плана (карты), описывается ниже в п.3. В результате всех этих действий получают совокупность целых горизонталей, а также совокупность отрезков горизонталей, на которых должны быть поставлены бергштрихи.

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

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

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

1.3. Ручная расстановка бергштрихов

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

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

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

Для определения направлений ската можно использовать триангулированную модель рельефа для всего плана или карты, по которой определяют направления ската для всех выбранных точек максимальной кривизны горизонталей, как описано выше в п.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 формулы изобретения).

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

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

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

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

Прежде всего, определяют множество треугольников триангуляции, для которых величина угла между этим треугольником и горизонтальной плоскостью меньше указанного значения уклона. Это множество треугольников берут в качестве множества вершин неориентированного графа. В рассматриваемом примере это треугольники с номерами 1-5, 10, 21, 24-27, 31, 32.

Две вершины графа соединяют ребром в том и только в том случае, если соответствующие треугольники имеют общую сторону, не являющуюся частью никакой горизонтали. В рассматриваемом примере ребрами соединяют следующие пары вершин: (1, 2), (2, 3), (4, 5), (21, 31), (24, 25), (25, 26), (26, 27), (31, 32). В результате получают граф, изображенный на фиг.5. В полученном неориентированном графе находят все связные компоненты, т.е. максимальные подмножества вершин графа, в каждом из которых любые две вершины соединены путем, проходящим по ребрам графа. Для нахождения связных компонент используют любой из известных способов нахождения связных компонент неориентированного графа, например, поиск в ширину [T.H.Cormen, C.E.Leiserson, R.L.Rivest, С.Stein. Introduction to Algorithms, Second Edition. The MIT Press Cambridge, Massachusetts London, 2001, p.450-452]. В рассматриваемом примере граф, изображенный на фиг.5, имеет пять связных компонент.

Далее последовательно рассматривают все найденные связные компоненты. Для каждой из них составляют список входящих в ее состав треугольников и список горизонталей, на которых лежат вершины этих треугольников. В рассматриваемом примере первая связная компонента содержит треугольники 1-3, вершины которых лежат на горизонтали I. Вторая связная компонента содержит треугольники 4-5, вершины которых лежат на горизонтали I. Третья связная компонента содержит единственный треугольник 10, вершины которого лежат на горизонтали II. Четвертая связная компонента содержит треугольники 24-27, вершины которого лежат на горизонтали III. Пятая связная компонента содержит треугольники 21, 31, 32, вершины которых лежат на горизонталях II и III.

Если для какой-либо связной компонента в указанном списке горизонталей оказывается единственная горизонталь, то перебирают все треугольники из указанного списка треугольников. Для каждого такого треугольника определяют те его стороны, которые не лежат на указанной единственной горизонтали, для каждой такой стороны проверяют, существует ли второй треугольник указанной триангуляции, который одной из своих сторон примыкает к этой стороне. Если такой треугольник существует и не входит в рассматриваемую связную компоненту, добавляют его в указанный список треугольников, при этом определяют горизонталь, на которой лежит вершина указанного второго треугольника, не инцидентная указанной стороне, и добавляют эту горизонталь в указанный список горизонталей. В рассматриваемом примере такими связными компонентами являются первые четыре связные компоненты. В результате описанного пополнения списков для первой связной компоненты список треугольников 1-3 превращается в 1-3, 6, а список горизонталей I превращается в I, II. Для второй связной компоненты список треугольников 4-5 не изменяется. Для третьей связной компоненты список треугольников 10 превращается в 10, 11, а список горизонталей II превращается в II, III. Для четвертой связной компоненты список треугольников 24-27 не изменяется.

После этого определяют те связные компоненты, для которых после корректировки списка треугольников и горизонталей, на которых лежат их вершины, в полученном списке оказывается более одной горизонтали. Для каждой такой связной компоненты определяют область, являющуюся объединением всех треугольников из указанного списка. Перебирают все пары вершин многоугольной границы этой области, которые лежат на горизонталях разной высоты. Для каждой такой пары вершин определяют минимальную длину связывающей их ломаной линии, лежащей внутри указанной области. Определяют уклон рельефа между этой парой вершин как отношение разности высот этих точек к полученной минимальной длине связывающей их ломаной линии. Если для какой-либо из указанных пар вершин уклон рельефа между этой парой вершин оказывается меньше указанного порогового значения уклона, то делают вывод о том, что указанная область является областью с малым уклоном рельефа. В этом случае перебирают все треугольники, входящие в указанный список, находят все стороны этих треугольников, лежащие на какой-либо горизонтали, и добавляют их в список искомых отрезков горизонталей. Для определения минимальной длины связывающей их ломаной, лежащей внутри указанной области и связывающей две заданные точки границы области, может быть использован любой из известных способов, например, основанный на графе видимости и изложенный в [М. de Berg, М. van Kreveld, М.Overmars, O.Schwarzkoft. Computational Geometry. Algorithms and Applications. Springer-Verlag Berlin Heidelberg, 1997, pp.306-308].

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

Корректность описанного способа нагляднее всего можно показать на рассматриваемом примере картины горизонталей. Прежде всего, заметим, что использование триангуляции позволяет за время, линейное по числу вершин всех горизонталей, определить соседние горизонтали. В том случае, когда соседние горизонтали идут близко друг к другу, как горизонтали II и III, т.е. величина уклона рельефа велика, большинство треугольников триангуляции имеют большую величину угла наклона относительно горизонтальной плоскости и не входят в число вершин графа. Исключение составляют те треугольники, все три вершины которых лежат на одной горизонтали, примером чего является треугольник 10. Несколько треугольников такого типа могут быть смежными по сторонам, не лежащим ни на какой горизонтали, образуя одну связную компоненту вышеописанного графа, примером чего является совокупность треугольников 1-3. Таким образом, на триангуляции оригинала рельефа могут иметь место горизонтальные участки двух типов. Горизонтальные участки первого типа (треугольник 10) лежат в области с большим уклоном рельефа. Горизонтальные участки второго типа (треугольники 1-3) лежат в области с малым уклоном рельефа. Для их различения используют соседние негоризонтальные треугольники, которые, будучи добавлены к горизонтальному участку, дают уже негоризонтальный участок, опирающийся на горизонтали разной высоты. Внутри этого негоризонтального участка производят оценку крутизны с использованием кратчайших путей, связывающих пары точек на разных горизонталях.

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

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

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

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

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

Прежде всего, определяют множество треугольников триангуляции, для которых либо все три вершины лежат на какой-либо одной ломаной, изображающей горизонталь рельефа, либо часть вершин лежит на какой-либо одной ломаной, изображающей горизонталь рельефа, а остальные вершины лежат на указанной рамке. Это множество треугольников берут в качестве множества вершин неориентированного графа. Возможны две интерпретации того, что надо понимать под треугольниками указанной триангуляции, часть вершин лежит на какой-либо одной ломаной, изображающей горизонталь рельефа, а остальные вершины лежат на указанной рамке. Первый вариант состоит в том, что в число вершин указанного графа включают все треугольники, вершины которых лежат на одной горизонтали и на указанной рамке, в том числе и в случае, когда вершина, лежащая на рамке, лежит и на другой горизонтали. Второй вариант состоит в том, что в число вершин указанного графа включают только треугольники, вершины которых лежат на одной горизонтали и на указанной рамке, для которых все вершины, лежащие на рамке, не лежат на другой горизонтали. В рассматриваемом примере при первом варианте интерпретации вершины графа - это треугольники с номерами 1-15, 22, 33-42, 46-49, выделенные на фиг.6 наклонной или вертикальной штриховкой. При втором варианте интерпретации вершины графа - это только треугольники с номерами 1-6, 9-12, 15, 22, 33-35, 40-42, 46-49, выделенные на фиг.6 наклонной или вертикальной штриховкой.

Две вершины графа соединяют ребром в том и только в том случае, если соответствующие им треугольники имеют общую сторону, не являющуюся частью никакого отрезка никакой ломаной, изображающей горизонталь рельефа или указанную рамку. В рассматриваемом примере при первом варианте интерпретации вершины графа ребрами соединяют следующие пары вершин: (1, 2), (2, 3), (3, 4), (4, 5), (6, 7), (7, 8), (9, 10), (10, 11), (10, 15), (11, 12), (13, 14), (33, 34), (34, 35), (36, 37), (37, 38), (38, 39), (40, 41), (41, 42), (46, 47), (47, 48), (48, 49). При втором варианте интерпретации вершины графа ребрами соединяют следующие пары вершин: (1, 2), (2, 3), (3, 4), (4, 5), (9, 10), (10, 11), (10, 15), (11, 12), (33, 34), (34, 35), (40, 41), (41, 42), (46, 47), (47, 48), (48, 49). В результате получают один из двух графов, изображенных на фиг.7.

В полученном неориентированном графе находят все связные компоненты, т.е. максимальные подмножества вершин графа, в каждом из которых любые две вершины соединены путем, проходящим по ребрам графа. Для нахождения связных компонент используют любой из известных способов нахождения связных компонент неориентированного графа, например поиск в ширину [T.H.Cormen, C.E.Leiserson, R.L.Rivest, С.Stein. Introduction to Algorithms, Second Edition. The MIT Press Cambridge, Massachusetts London, 2001, p.450-452]. В рассматриваемом примере графы, изображенные на фиг.7, имеют в зависимости от варианта 9 или 7 связных компонент.

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

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

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

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

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

Покажем, что любые две вершины графа, принадлежащие М, связаны в графе некоторым путем по ребрам графа. Пусть T₁ и T₂ - два треугольника триангуляции, соответствующие любым двум вершинам m₁, m₂ из М. Пусть Р₁ и P₂ - произвольные точки внутри треугольников T₁ и Т₂ (см. фиг.8). Поскольку область, ограниченная контуром А, связна, то внутри этой области существует путь γ, соединяющий точку P₁ с точкой Р₂. Этот путь последовательно проходит через треугольники триангуляции t₁, …, t_n, где t₁=T₁, t_n=T₂. В рассматриваемом примере этими треугольниками являются треугольники с номерами 9, 10, 11, 12. Все три вершины каждого из этих треугольников лежат на контуре А, откуда все эти треугольники принадлежат графу. Для произвольного i, 1≤i<n, пусть Q - точка на пути γ, в которой он выходит из треугольника t_i и заходит в треугольник t_i+1. Тогда Q лежит как на стороне треугольника t_i, так и на стороне треугольника t_i+1. Следовательно, треугольники t_i и t_i+1 имеют общую сторону. Поэтому по определению графа они связаны в графе ребром. Таким образом, в графе существует путь по ребрам, связывающий вершины m₁, m₂. Следовательно, подмножество М графа связно.

Предположим, что М не является связной компонентой графа. Тогда М не является максимальным связным подмножеством графа. В этом случае существует треугольник T₂ триангуляции, не принадлежащий множеству М, для которого соответствующая вершина в графе связана некоторым путем с какой-либо вершиной из множества М. Эта вершина соответствует некоторому треугольнику T₁ триангуляции, лежащему внутри области, ограниченной контуром А. Пусть t₁, …, t_n - все вершины графа на этом пути, причем вершина t₁ соответствует треугольнику T₁, а вершина t_n соответствует треугольнику T₂. Поскольку вершина t_n соответствует треугольнику, не лежащему внутри области, ограниченной контуром А, то существует максимальное i<n, для которого треугольник, соответствующий t_i, все еще лежит внутри указанной области. В этом случае треугольник, соответствующий t_i+1, уже не лежит внутри указанной области. Следовательно, эти два треугольника разделены границей области, являющейся замкнутым контуром А, составленным горизонталью и часть рамки оригинала рельефа. Это противоречит тому, что вершины t_i и t_i+1 связаны ребром в графе. Полученное противоречие доказывает, что М является связной компонентой графа.

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

3.2. Способ построения триангуляции оригинала рельефа

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

Сначала строят триангуляцию по множеству всех точек на плоскости, являющихся вершинами ломаных, изображающих горизонтали рельефа и рамку оригинала рельефа. Можно использовать триангуляцию Делоне или триангуляцию минимального периметра. Триангуляция Делоне может быть определена как такая триангуляция заданного множества точек на плоскости, для которой минимальное значение всех углов всех треугольников максимально [М. de Berg, M. van Kreveld, M.Overmars, O.Schwarzkoft. Computational Geometry. Algorithms and Applications. Springer-Verlag Berlin Heidelberg, 1997, p.189]. Триангуляция минимального периметра определяется как такая триангуляция заданного множества точек на плоскости, для которой сумма периметров всех треугольников минимальна. Способ построения триангуляции по множеству точек хорошо известен и описан, например, в [M. de Berg, M. van Kreveld, M.Overmars, O.Schwarzkoft. Computational Geometry. Algorithms and Applications. Springer-Verlag Berlin Heidelberg, 1997, pp.181-205]. Пример такой триангуляции приведен на фиг.9, где горизонтали рельефа и рамка оригинала рельефа изображены утолщенными линиями, а стороны треугольников, образующих триангуляцию - пунктирными линиями.

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

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

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

4. Способ отбора точек максимальной кривизны горизонталей

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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