СПОСОБ ОПРЕДЕЛЕНИЯ НЕДОПУСТИМОЙ ПЛОТНОСТИ ТОЧЕЧНЫХ ОБЪЕКТОВ, БЕСПОРЯДОЧНО РАСПОЛОЖЕННЫХ НА ПЛОСКОСТИ Российский патент 2007 года по МПК G06M11/00 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На фиг.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]. В случае конфигураций из не очень большого числа точечных объектов это вполне приемлемый способ.

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

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

С целью уменьшения перебора точечных объектов при определении тестовых квадратов со стороной 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 тестового квадрата состоит в следующем.

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

Затем формируют горизонтальные полосы шириной d, включая в полосу с номером k те точечные объекты Р_i, для которых выполняется условие kd≤y_i<(k+1)d. Одновременно составляют список всех непустых полос. Для этого последовательно просматривают все точечные объекты с номерами i[0],..., i[N-1] и для каждого точечного объекта с номером i[k] определяют номер полосы m[k]=y_i[k]/d, в которую он попадает (для этого в результате деления отбрасывают дробную часть, что дает целое число). Поскольку значения y_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, е_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.

В первом случае последовательно просматривают точечные объекты, попавшие в текущую полосу р[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]]]}≥x_{i[bj+k[j, r]]}-d, следующим образом. При r=0 полагают s[0]=0. Для текущего r последовательно просматривают все точечные объекты в порядке номеров k[j, 0],..., k[j, е_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]]]}≥x_{i[bj+k[j, r]]}-d, и минимальный номер 0≤s1[r]≤e_j+1-b_j+1, для которого x_{i[bj+k[j+1, s1[r]]]}≥x_{i[bj+k[j, r]]}-d, следующим образом. При r=0 полагают s[0]=s1[0]=0. Для текущего r последовательно просматривают все точечные объекты в порядке номеров k[j, 0],..., k[j, е_j-b_j], начиная с k[j, s[r-1]]-го, пока значение координаты х очередного объекта не станет превосходить х_{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]]-го, пока значение координаты х для них остается меньше x_{i[bj+k[j, r]]}+d. Из всех таких точечных объектов отбирают те, для которых значение координаты у не больше увеличенного на d значения координаты у текущего точечного объекта, и включают их в число дочерних вершин для вершины, соответствующей текущему объекту.

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

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

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

{(x, y)|x_min≤x≤x_min+d, y_min≤y≤y_min+d},

{(x, y)|x_max-d≤x≤x_max, y_max-d≤y≤y_max}

или

{(x, у)|x_min≤x≤x_min+d, y_max-d≤y≤y_max},

{(x, у)|x_max-d≤x≤x_max, y_min≤y≤y_min+d}

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

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

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

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

1. Способ определения недопустимой плотности точечных объектов, беспорядочно расположенных на плоской поверхности, при котором выбирают величину тестового квадрата, перемещают указанный тестовый квадрат в различные положения, покрывающие всю проверяемую поверхность, подсчитывают количество точечных объектов в каждом из квадратов, сравнивают полученные значения с заданными минимальным и максимальным допустимым значениями числа точечных объектов и определяют те квадраты, в которых плотность точечных объектов принимает недопустимые значения, отличающийся тем, что указанные различные положения тестового квадрата выбирают как положения тестового квадрата, при которых он проходит двумя своими смежными сторонами через соответствующие два точечных объекта, а также все положения тестового квадрата, одна из вершин которого совпадает с каким-либо из точечных объектов.2. Способ по п.1, отличающийся тем, что для определения всех положений тестового квадрата, при которых он проходит двумя своими смежными сторонами через соответствующие два точечных объекта, перебирают все пары точечных объектов.3. Способ по п.1, отличающийся тем, что для определения всех положений тестового квадрата, при которых он проходит двумя своими смежными сторонами через соответствующие два точечных объекта, строят любой из четырех ориентированных графов смежности (верхний, нижний, левый или правый) для конфигурации точечных объектов и заданной стороны тестового квадрата, и перебирают все пары точечных объектов, для которых соответствующие им вершины в графе смежности являются связанными направленным ребром, причем для каждой такой пары точечных объектов строят два тестовых квадрата, смежные стороны которых проходят через указанную пару точечных объектов.4. Способ по п.1, отличающийся тем, что для подсчета количества точечных объектов, попавших в тестовый квадрат, находящийся в положениях, при которых он проходит двумя своими смежными сторонами через соответствующие два точечных объекта, а также в положениях, при которых одна из его вершин совпадает с каким-либо из точечных объектов, строят четыре ориентированных графа смежности (верхний, нижний, левый и правый) для конфигурации точечных объектов и заданной стороны тестового квадрата, в каждом из указанных графов для каждой вершины упорядочивают списки дочерних к ней вершин по возрастанию их номеров, после чего для подсчета числа точечных объектов, попавших внутрь тестового квадрата, пара смежных сторон которого проходит через пару точечных объектов А и В или вершина которого совпадает с точечным объектом А=В, при А≠В выбирают пару ориентированных графов смежности G_A и G_B, причем для точечного объекта А или В выбирают соответствующий верхний граф смежности, если точечный объект лежит строго внутри нижней стороны тестового квадрата, нижний граф смежности, если точечный объект лежит строго внутри верхней стороны тестового квадрата, левый граф смежности, если точечный объект лежит строго внутри правой стороны тестового квадрата, правый граф смежности, если точечный объект лежит строго внутри левой стороны тестового квадрата, а при А=В выбирают пару, состоящую из верхнего и правого графов смежности, если точечный объект А=В совпадает с нижним левым углом тестового квадрата, из верхнего и левого графов смежности, если точечный объект А=В совпадает с нижним правым углом тестового квадрата, из нижнего и правого графов смежности, если точечный объект А=В совпадает с верхним левым углом тестового квадрата, из нижнего и левого графов смежности, если точечный объект А=В совпадает с верхним правым углом тестового квадрата, и определяют число точечных объектов внутри тестового квадрата как число точечных объектов, входящих одновременно в два упорядоченных по возрастанию списка: в список дочерних вершин для вершины А в графе G_A и в список дочерних вершин для вершины В в графе G_B.