Scientific journal

Modern high technologies

ISSN 1812-7320

"Перечень" ВАК

ИФ РИНЦ = 0,940

Распределение случайных точек внутри произвольной фигуры на плоскости или в пространстве является актуальной проблемой не только в вычислительной и стохастической геометрии, но и в математическом моделировании, численных методах, компьютерной графике [1–4]. Больший интерес представляет равномерное распределение точек, которое связано не только с вычислительными задачами, решаемыми, например, методом Монте-Карло, но и с многочисленными техническими, биологическими и экономическими приложениями [5, 6]. В последние годы активно разрабатываются программные продукты для работы с моделями карт, для проектирования ландшафтов и экологического моделирования, содержащие инструменты для случайного расположения объектов (например, для территориального распределения лесных массивов на картах и др.) [7, 8]. Однако в использовании таких систем, в частности при работе с инструментами случайного распределения точек (объектов на картах), существуют определенные неудобства. Например, на сайте Geospatial Modelling Environment [8] указано, что программа может достаточно долго выполнять распределение случайных объектов, если область на карте имеет малую площадь и большой периметр. Такая же ситуация возможна и при работе с инструментами в профессиональном картографическом программном обеспечении ArcGIS Pro [7]. В обеих системах алгоритмы используют циклы с постусловием: случайные точки внутри некоторой выпуклой оболочки, содержащей выбранную область (на карте), генерируются до тех пор, пока внутрь этой области не попадет заданное количество точек. Очевидно, что если площадь выбранной области мала по сравнению с площадью ее выпуклой оболочки, то количество шагов такого алгоритма может быть велико.

Существуют различные алгоритмические подходы к решению этой проблемы [3, 5, 6, 9]. Вариативность подходов и эффективное решение этой проблемы стало возможным благодаря активному использованию информационно-коммуникационных технологий, специализированным программным продуктам (например, пакетам компьютерной математики). Сочетание ИКТ и наглядности геометрических подходов в решении таких задач дает определенные преимущества [5, 6, 10, 11].

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

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

Мы рассматриваем следующие задачи.

Задача 1. Произвольный многоугольник P площади S задан координатами своих вершин на плоскости. Требуется равномерно распределить внутри него n случайных точек. Уточним постановку задачи. Требуется построить последовательность D_n(n∈N), такую, что:

1) Dn является n-элементным множеством точек плоскости и ;

2) для любого треугольника площадью S(Q) обозначим посредством k(Q, n) количество точек из Dn, попавших внутрь Q. Требуется, чтобы .

В общем случае решение поставленной задачи подразумевает построение какой-либо триангуляции данного многоугольника и «равномерное заполнение» точками каждого из треугольников. При этом генерируются две последовательности независимых случайных чисел si и ti) (i = 1,…, n), равномерно распределенных на интервале (0, 1). В этом случае точки с координатами (si, ti) равномерно распределены внутри единичного квадрата. Если задать на плоскости произвольные точки A, B, то точки с координатами

будут равномерно распределены внутри параллелограмма со сторонами OA, OB.

Однако для равномерного распределения точек внутри треугольника OAB требуется проверять условие s_i + t_i ≤ 1. Выгоднее изначально равномерно распределить точки внутри прямоугольного треугольника с единичными катетами, гипотенуза которого совпадает с диагональю квадрата (так как это позволяет избавиться от проверки условия s_i + t_i ≤ 1). Мы предлагаем следующее решение задачи 1.

Пусть сгенерированы две последовательности независимых случайных чисел si и ti (i = 1,…, n), равномерно распределенных на интервале (0, 1). Построим последовательность точек с координатами

(эти точки равномерно распределены внутри прямоугольного треугольника с единичными катетами (см. пример на рис. 1 слева)). Тогда (фактически выполнив аффинное преобразование) получим, что случайные точки M(xi, yi) с координатами

равномерно распределены внутри произвольного треугольника OAB (см. пример на рис. 1 справа). Несложно записать формулы для координат случайных точек внутри произвольного треугольника ABC.

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

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

1. Пронумеруем все треугольники в триангуляции (обозначим их количество k) и найдем площадь каждого из них: S1, S2,…, Sk (площадь многоугольника обозначим S).

2. Построим разбиение отрезка [0, S] точками S1, S1 + S2, …, S1 + S2 + … + S_k-1.

3. Сгенерируем последовательность n случайных чисел ξ_i, равномерно распределенных на интервале (0, 1), и составим последовательность ξ_i•S.

4. Количество точек mk внутри k-го треугольника будет равно числу точек вида ξ_i•S, попавших в k-й промежуток разбиения в п. 2). Очевидно, что .

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

Рассмотрим задачу о равномерном распределении точек внутри произвольного многогранника.

Задача 2. Произвольный многогранник P объема V в пространстве задан координатами своих вершин. Требуется равномерно распределить внутри него n случайных точек.

Аналогично задаче 1 уточним постановку задачи. Требуется построить последовательность Dn(n∈N), такую что:

1) Dn является n-элементным множеством точек плоскости и ;

2) для любого тетраэдра объемом V(Q) обозначим посредством k(Q, n) количество точек из Dn, попавших внутрь Q. Требуется, чтобы

В общем случае решение поставленной задачи подразумевает построение какой-либо трехмерной триангуляции данного многогранника (разбиение на тетраэдры) и равномерное «заполнение» точками каждого тетраэдра в разбиении. При этом генерируются три последовательности независимых случайных чисел si, ti и ri (i = 1,…, n), равномерно распределенных на интервале (0, 1). Известно, что в этом случае точки с координатами (si, ti, ri) равномерно распределены внутри единичного куба.

Рис. 1. Пример равномерного распределения 750 случайных точек (α_i, β_i) внутри прямоугольного треугольника (слева) и соответствующее ему распределение точек M(xi, yi) внутри треугольника OAB (где A (1, 4) и B (3, 0))

Рис. 2. Полученное с помощью предложенного алгоритма случайное распределение 250 (слева) и 750 (справа) точек внутри многоугольника