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

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

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

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

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

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

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

В заявке [ЕР 0526027 В1, опубл. 27.05.98. Appl. № 92306372.1 filed 10.07.92. Приор. 25.07.91 JP 186107/91] предлагается способ топографической обработки, включающий в себя запоминание множества карт, имеющих соответственно разные данные и относящихся к одной области, и выбор части первой из указанного множества карт, при котором указанная часть указанной первой карты делится на множество подобластей, производится исследование данных каждой из указанных подобластей, чтобы определить, соответствует ли плотность указанных данных карты заранее заданному порогу, для каждой подобласти, для которой плотность указанных данных карты не соответствует указанному порогу, исследуются данные соответствующей части второй карты и порождается выдаваемая на дисплей информация, объединяющая данные из указанной части второй карты и указанного множества подобластей первой карты, отличных от тех областей, для которых плотность данных не соответствует указанному порогу.

В работе [Алчинов А.И., Кекелидзе В.Б. «Технология составления рельефа местности на цифровой фотограмметрической станции «Талка»» // Геопрофи, 2005, № 3, с.22-24] (прототип) описан простейший способ нерегулярного размещения точечных объектов на карту местности с заданной плотностью, состоящий в том, что наносят требуемые точечные объекты в характерных местах, после чего разбивают карту на квадраты заданного размера и подсчитывают число точечных объектов в каждом квадрате, чтобы определить те квадраты, в которых плотность точечных объектов слишком мала или слишком велика. Соответственно проводят автоматическое или ручное добавление точечных объектов или удаление лишних.

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

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

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

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

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

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

на фиг.3 - сдвиг тестового квадрата по вертикали.

на фиг.4 - определение верхнего графа смежности.

на фиг.5 - полосы для получения верхнего графа смежности.

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

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

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

Способ нерегулярного размещения точечных объектов на карту местности с заданной плотностью состоит в том, что выбирают размер стороны тестового квадрата, используемого для контроля допустимости плотности точечных объектов, и производят последовательно нанесение точечных объектов на карту местности и удаление явно лишних с использованием на каждом шаге контроля плотности точечных объектов, применяя для определения мест недопустимой плотности точечных объектов цифровую фотограмметрическую станцию "Талка" [Алчинов А.И., Кекелидзе В.Б. "Технология составления рельефа местности на цифровой фотограмметрической станции "Талка" // Геопрофи, 2005, № 3, с.22-24]. Она позволяет, в частности, производить подключение внешних программ пользователя, оформленных в виде DLL ["Использование SDK-средств для подключения внешних программ к Талке 3.3." http://talka-tdv.ru/statyi.htm]. В качестве DLL следует использовать программу, реализующую описанный ниже в п.2 способ определения недопустимой плотности точечных объектов, беспорядочно расположенных на плоской поверхности. Совокупность тестовых квадратов, в которых плотность точечных объектов меньше заданной, следует при выполнении этой DLL объединить в одну или несколько областей, используя, например, способ объединения прямоугольных областей, изложенный в [Ф.Препарата, М.Шеймос. Вычислительная геометрия: введение. М., "Мир", 1989, с.414-424]. То же самое следует сделать и для тестовых квадратов, в которых плотность точечных объектов больше заданной. Это обеспечит удобный просмотр операторами, производящими размещение точечных объектов, текущего состояния всего множества точечных объектов. Предпочтительным является именно ручное нанесение новых точечных объектов или удаление излишних, поскольку это позволяет учитывать трудноформализуемые требования, такие как читаемость рельефа.

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

На фиг.1 показан пример конфигурации точечных объектов, расположенных на листе плана местности формата 20×20 см. В предположении, что минимальное и максимальное количество точечных объектов на 1 кв. дм составляют 2 и 5, на этом примере четыре тестовых квадрата со стороной 1 дм содержат соответственно 3, 4, 4 и 3 точечных объекта, то есть количества точек внутри тестовых квадратов, соответствующих паркетному разбиению листа плана, удовлетворяют требованиям на минимальное и максимальное число точечных объектов. Под паркетным разбиением карты или плана здесь и ниже понимается разбиение карты или плана на примыкающие друг к другу сторонами непересекающиеся квадраты, заполняющие в совокупности всю карту или план. Однако заштрихованный тестовый квадрат содержит 6 точек, что недопустимо. Таким образом, использование наряду с тестовыми квадратами, соответствующих паркетному разбиению листа плана, дополнительных тестовых квадратов позволяет выявлять места чрезмерно большой плотности точечных объектов, которые не выявляются при использовании только "паркетных" тестовых квадратов. На фиг.2 показан пример конфигурации точечных объектов, для которой дополнительный тестовый квадрат выявляет место чрезмерно малой плотности точечных объектов.

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

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

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

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

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

3. Ориентированные графы смежности точечных объектов

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

Верхним графом смежности для конфигурации точечных объектов и стороны d тестового квадрата будем называть ориентированный граф, множество вершин которого совпадает с множеством индексов точечных объектов 0 i<N, а направленные ребра определяются следующим образом. Направленное ребро из вершины i в вершину j(i j) проводится в том и только в том случае, если 0 у_j-у_i d и -d x_j-x_i d. Иными словами, направленное ребро из вершины i в вершину j проводится в том и только в том случае, если точечный объект P_j лежит выше точечного объекта Р _i, а расстояния между этими точечными объектами как по горизонтали, так и по вертикали не превосходят стороны тестового квадрата (см. фиг.4).

В соответствии с общей теорией графов каждый ориентированный граф с множеством вершин {j} (0 j<N) задается совокупностью списков S _j всех вершин, в которые идут направленные ребра с началом в вершине j. Вершины из списка S_j называются дочерними к вершине j. Таким образом, определение ориентированного графа с заданным множеством вершин {j} (0 j<N) эквивалентно заданию совокупности списков S _j(0 j<N) дочерних вершин для всех j, 0 j<N.

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

Прежде всего упорядочивают точечные объекты по возрастанию значений координаты у. Это производят с помощью любого известного способа сортировки, например [А.В.Ахо, Дж.Э.Хопкрофт, Дж.Д.Ульман. Структуры данных и алгоритмы. Издат. дом "Вильямс", 2000, с.243], что дает последовательность номеров точечных объектов i[0], ..., i[N-1], являющуюся перестановкой последовательности 0, ..., N-1, такую, что у_i[0] ... у_i[N-1].

Затем формируют горизонтальные полосы шириной d, включая в полосу с номером k те точечные объекты P_i, для которых выполняется условие kd у_i<(k+1)d. Одновременно составляют список всех непустых полос. Для этого последовательно просматривают все точечные объекты с номерами i[0], ..., i[N-1] и для каждого точечного объекта с номером i[k] определяют номер полосы m[k]=у _i[k]/d, в которую он попадает (для этого в результате деления отбрасывают дробную часть, что дает целое число). Поскольку значения у_i[k] являются неубывающими, то и номера полос m[k] также будут неубывающими. Следовательно, при последовательном просмотре точечных объектов они будут последовательно заполнять полосы, причем окончание очередной полосы и начало новой характеризуется условием m[k]<m[k+1]. В результате получается совокупность из М непустых полос с номерами р[0]<...<р[М-1], причем полоса с номером p[j] содержит точечные объекты с номерами i[b _j], i[b_j+1], ..., i[e _j]. Например, для множества из шести точечных объектов, изображенного на фиг.5, получаются четыре непустые полосы с номерами 1, 2, 5 и 6, причем полоса 1 содержит точечные объекты с номерами i[0], i[1], i[2], а полосы 2, 5 и 6 содержит по одному точечному объекту с номерами i[3], i[4] и i[5] соответственно.

В каждой j-й полосе производят упорядочение попавших в нее точечных объектов с номерами i[b_j], ..., i[e _j] по возрастанию значений координаты х с помощью, например, того же вышеуказанного способа сортировки. Это дает последовательность номеров k[j, 0], ..., k[j, e_j-b _j], являющуюся перестановкой последовательности 0, ..., e_j-b_j, такую, что значения координаты х для точечных объектов с номерами i[b _j+k[j, 0]], ..., i[b_j+k[j, e _j-b_j]] возрастают. Например, для приведенной на фиг.5 конфигурации для полосы с номером р[0]=1 имеем b₁=0, e₁=2, k[0, 0]=1, k[0, 1]=2, k[0, 2]=0.

Наконец, путем последовательного просмотра сформированных полос с номерами р[0]<...<р[М-1] определяют списки всех дочерних вершин для всех вершин текущей полосы. Здесь различают два случая для текущей полосы p[j]: 1) полосы p[j] и p[j+1] не являются соседними, т.е. p[j+1]>p[j]+1 (сюда же относят и случай, когда j-я полоса является последней, т.е. j=М-1); 2) полосы p[j] и p[j+1] являются соседними, т.е. p[j+1]=p[j]+1.

В первом случае последовательно просматривают точечные объекты, попавшие в текущую полосу p[j] в порядке номеров k[j, 0], ..., k[j, e_j-b _j], причем для каждого текущего номера r, 0 r e_j-b_j, определяют минимальный номер 0 s[r] e_j-b_j, для которого x_{i[bj+k[j, s[r]]] xi[bj+k[j, r]]}-d, следующим образом. При r=0 полагают s[0]=0. Для текущего r последовательно просматривают все точечные объекты в порядке номеров k[j, 0], ..., k[j, e _j-b_j], начиная с k[j, s[r-1]]-го, пока значение координаты х очередного объекта не станет превосходить х_{i[bj+k[j, r]]}-d. Номер первого такого объекта в текущей полосе берут в качестве s[r]. Далее последовательно просматривают все точечные объекты в порядке номеров k[j, 0], ..., k[j, е_j-b_j], начиная с k[j, s[r]]-го, пока значения координаты х для них остается меньше х_{i[bj+k[j, r]]}+d. Из всех таких точечных объектов отбирают те, для которых значение координаты у не меньше значения координаты у текущего точечного объекта, и включают их в число дочерних вершин для вершины, соответствующей текущему объекту.

Во втором случае последовательно просматривают точечные объекты, попавшие в текущую полосу p[j] в порядке номеров k[j, 0], ..., k[j, е_j-b _j], причем для каждого текущего номера r, 0 r e_j-b_j, определяют минимальный номер 0 s[r] e_j-b_j, для которого x_{i[bj+k[j, s[r]]] xj[bj+k[j, r]]}-d, и минимальный номер 0<s1[r] e_j+1-b_j+1, для которого x_{i[bj+k[j+1, s1[r]]] xi[bj+k[j, r]]}-d, следующим образом. При r=0 полагают s[0]=s1[0]=0. Для текущего r последовательно просматривают все точечные объекты в порядке номеров k[j, 0], ..., k[j, e _j-b_j], начиная с k[j, s[r-1]]-го, пока значение координаты х очередного объекта не станет превосходить x_{i[bj+k[j, r]]}-d. Номер первого такого объекта в текущей полосе берут в качестве s[r]. Кроме того, последовательно просматривают все точечные объекты в порядке номеров k[j+1, 0], ..., k[j+1, e_j+1-b_j+1 ], начиная с k[j+1, s[r-1]]-го, пока значение координаты х очередного объекта не станет превосходить х_{i[bj+k[j, r]]} -d. Далее последовательно просматривают все точечные объекты в порядке номеров k[j, 0], ..., k[j, e_j -b_j], начиная с k[j, s[r]]-го, пока значения координаты х для них остается меньше x_{i[bj+k[j, r]]}+d. Из всех таких точечных объектов отбирают те, для которых значение координаты у не меньше значения координаты у текущего точечного объекта, и включают их в число дочерних вершин для вершины, соответствующей текущему объекту. Кроме того, последовательно просматривают все точечные объекты в порядке номеров k[j+1, 0], ..., k[j+1, e_j+1-b_j+1 ], начиная с k[j+1, s1[r]]-го, пока значения координаты х для них остается меньше х_{i[bj+k[j, г]]}+d. Из всех таких точечных объектов отбирают те, для которых значение координаты у не больше увеличенного на d значения координаты у текущего точечного объекта, и включают их в число дочерних вершин для вершины, соответствующей текущему объекту.

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

4. Более оптимальный способ выявления недопустимой плотности точечных объектов, беспорядочно расположенных на плоскости

Более оптимальный способ выявления недопустимой плотности точечных объектов, беспорядочно расположенных на плоскости, заключается в том, что для определения всех положений тестового квадрата, при которых он проходит двумя своими смежными сторонами через соответствующие два точечных объекта, строят любой ориентированный граф смежности (верхний, нижний, левый или правый) для конфигурации точечных объектов и заданной стороны тестового квадрата и перебирают все пары точечных объектов, для которых соответствующие им вершины являются связанными направленным ребром. Для этого перебирают все точечные объекты А с координатами (х_A, у_A) и для каждого из них перебирают все дочерние в графе к вершине А вершины В с координатами (х_B, у_B ). Вычисляют значения x_min=min{x _A, х_B}, x_max =max{х_A, х_B}, у _min=min{у_A, у_B }, у_max=max{у_А, у _B} и формируют два тестовых квадрата:

{(x, у)|x _min x x_min+d, у_min у у_min+d},

{(x, у)|x _max-d x x_max, у_max-d у у_max}

или

{(x, у)|x _min x x_min+d, у_max -d у у_max},

{(x, у)|x _max-d x x_max, у_min у у_min+d}

в зависимости от знака (х_В-х_А)(у _В-у_А): в случае отрицательного знака используют первый случай, в противном случае - второй.

Корректность этого способа вытекает из следующих рассмотрений. Пусть А и В - два точечных объекта с координатами (х _А, у_А) и (х_В , у_В), для которых существует тестовый квадрат со стороной d, такой, что точечные объекты А и В лежат на двух его смежных сторонах (см. фиг.6). Заметим, что в этом случае через точечные объекты А и В можно провести два тестовых квадрата. Пусть для определенности у_А у_В. В этом случае 0 у_В-у_А d и -d х_В-х_А d. Следовательно, точечный объект В является дочерним к точечному объекту А в верхнем графе смежности, т.е. вершины верхнего графа смежности, соответствующие точечным объектам А и В, являются связанными направленным ребром. Аналогично устанавливается связанность направленным ребром соответствующих вершин в других графах смежности.

Кроме того, ориентированные графы смежности могут быть использованы для быстрого подсчета количества точечных объектов, попавших в тестовый квадрат, находящийся в положениях, при которых он проходит двумя своими смежными сторонами через соответствующие два точечных объекта, а также в положениях, при которых одна из его вершин совпадает с каким-либо из точечных объектов. Для этого строят ориентированные графы смежности (верхний, нижний, левый и правый) для конфигурации точечных объектов и заданной стороны тестового квадрата и в каждом из указанных четырех графов для каждой вершины упорядочивают списки дочерних к ней вершин по возрастанию их номеров. Для подсчета числа точечных объектов, попавших внутрь тестового квадрата, пара смежных сторон которого проходит через пару точечных объектов А и В или вершина которого совпадает с точечным объектом А=В, выбирают пару ориентированных графов смежности следующим образом. При А В выбирают пару ориентированных графов смежности G _A и G_B, причем для точечного объекта А или В выбирают соответствующий верхний граф смежности, если точечный объект лежит строго внутри нижней стороны тестового квадрата, нижний граф смежности, если точечный объект лежит строго внутри верхней стороны тестового квадрата, левый граф смежности, если точечный объект лежит строго внутри правой стороны тестового квадрата, правый граф смежности, если точечный объект лежит строго внутри левой стороны тестового квадрата. Пусть теперь А=В, тогда точечный объект А=В лежит на двух смежных сторонах тестового квадрата, т.е. совпадает с одним из углов тестового квадрата. Если точечный объект А=В совпадает с нижним левым углом тестового квадрата, то выбирают пару, состоящую из верхнего и правого графов смежности. Если точечный объект А=В совпадает с нижним правым углом тестового квадрата, то выбирают пару, состоящую из верхнего и левого графов смежности. Если точечный объект А=В совпадает с верхним левым углом тестового квадрата, то выбирают пару, состоящую из нижнего и правого графов смежности. Наконец, если точечный объект А=В совпадает с верхним правым углом тестового квадрата, то выбирают пару, состоящую из нижнего и левого графов смежности. Тогда определяют число точечных объектов внутри тестового квадрата как число точечных объектов, входящих одновременно в два упорядоченных по возрастанию списка: в список дочерних вершин для вершины А в графе G_A и в список дочерних вершин для вершины В в графе G_B.

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