Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,899

ГЕОМЕТРИЧЕСКИЕ ПРИЕМЫ В РЕАЛИЗАЦИИ АЛГОРИТМА ГЕНЕРАЦИИ СЛУЧАЙНЫХ ТОЧЕК ВНУТРИ ПРОИЗВОЛЬНЫХ МНОГОУГОЛЬНИКОВ И МНОГОГРАННИКОВ

Мартынова Е.В. 1 Нигматулин Р.М. 1
1 ФГБОУ ВО «Южно-Уральский государственный гуманитарно-педагогический университет»
Настоящая статья посвящена описанию построения и реализации алгоритма генерации случайных точек внутри произвольных многоугольников и многогранников. Использование геометрических приемов позволяет избавиться от «холостого хода» алгоритма, возникающего при использовании цикла с постусловием «пока не будет получено необходимое количество точек». Преимущества их использования особенно проявляются для невыпуклых многоугольников, площадь которых значительно меньше площади их выпуклой оболочки, и для невыпуклых многогранников, объем которых также значительно меньше объема их выпуклой оболочки. Предложенные в работе геометрические приемы позволяют упростить построение и реализацию алгоритма генерации случайных точек, равномерно распределённых внутри произвольных многоугольников и многогранников. Число шагов для получения необходимого числа точек в каждом треугольнике (тетраэдре) в произвольной триангуляции заданного многоугольника (многогранника) в предложенном алгоритме определяется явно. Был проведен вычислительный эксперимент, наглядно демонстрирующий преимущества такого подхода.
случайные точки внутри многоугольника
случайные точки внутри многогранника
равномерное распределение точек
генерация случайных точек
1. Амбарцумян Р.В. Введение в стохастическую геометрию / Р.В. Амбарцумян, Й. Мекке, Д. Штойян. – М.: Наука, 1989. – 400 с.
2. Препарата Ф. Вычислительная геометрия: Введение / Ф. Препарата, М. Шеймос. – М.: Мир, 1989. – 478 с.
3. Rocchini C., Cignoni P. Generating random points in a tetrahedron // Journal of graphics Tools. – 2000. – Vol. 5. – № 4. – P. 9–12.
4. Weisstein E.W. Triangle Point Picking – From MathWorld [Электронный ресурс] // A Wolfram Web Resource. URL: http://mathworld.wolfram.com/topics/RandomPointPicking.html (дата обращения: 20.11.17).
5. Копытов Н.П. Универсальный алгоритм равномерного распределения точек на произвольных аналитических поверхностях в трехмерном пространстве / Н.П. Копытов, Е.А. Митюшов // Фундаментальные исследования. – 2013. – № 4–3. – С. 618–622.
6. Рубан А.И. Новый генератор случайных равномерно распределенных точек [Текст] / А.И. Рубан, А.В. Кузнецов // Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева. – 2013. – № 2 (48). – С. 75–81.
7. ArcGIS Pro | Профессиональное картографическое программное обеспечение 2D & 3D ГИС [Электронный ресурс]. – Режим доступа: https://www.esri.com/ru/arcgis/products/arcgis-pro/overview (дата обращения: 20.11.17).
8. Geospatial Modelling Environment. GME | SpatialEcology.Com [Электронный ресурс]. – Режим доступа: http://www.spatialecology.com/gme/ (дата обращения: 20.11.17).
9. Bеlisle C. On the polygon generated by n random points on a circle // Statistics & Probability Letters. – 2011. – Vol. 81. № 2. – P. 236–242.
10. Мартынова Е.В. Информационные технологии в организации геометрического эксперимента // Математика. Компьютер. Образование: Тезисы Девятнадцатой международной школы-конференции (Дубна, 30 января – 03 февраля 2012 г.). – Ижевск: НИЦ «Регулярная и хаотическая динамика», 2012. – С. 350.
11. Мартынова Е.В. Геометрический подход к построению алгоритма генерации случайных точек внутри произвольного многоугольника / Е.В. Мартынова, Р.М. Нигматулин // Информационно-коммуникационные технологии в науке, производстве и образовании ICIT-2017: материалы Международной научной конференции (Саратов, 21–22 сентября 2017 г.). – Саратов: ООО Издательство «Научная книга», 2017. – С. 168–172.

Распределение случайных точек внутри произвольной фигуры на плоскости или в пространстве является актуальной проблемой не только в вычислительной и стохастической геометрии, но и в математическом моделировании, численных методах, компьютерной графике [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 случайных точек. Уточним постановку задачи. Требуется построить последовательность Dn(n∈N), такую, что:

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

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

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

mart04.wmf

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

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

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

mart05.wmf

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

mart06.wmf

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

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

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

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

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

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

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

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

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

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

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

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

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

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

mart1.tif

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

mart2.tif

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

mart3.tif

Рис. 3. Пример равномерного распределения 750 случайных точек (αi, βi, γi) внутри тетраэдра, образованного векторами mart15.wmf (слева), и соответствующее ему распределение точек M(xi, yi, zi) внутри тетраэдра OABC (где A (5, 2, 1), B (1, 6, 2) и C (2, 1, 7))

Рассмотрим в пространстве произвольные точки A, B, C (общего положения). Тогда точки M(xi, yi, zi) с координатами

mart11.wmf

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

Мы предлагаем следующее решение задачи о равномерном распределении n точек внутри тетраэдра OABC.

Зададим точки с координатами

mart12.wmf.

Эти точки равномерно распределены внутри тетраэдра, образованного векторами mart13.wmf (см. пример на рис. 3 слева). Тогда (по существу выполнив аффинное преобразование) случайные точки M(xi, yi, zi) с координатами

mart14.wmf

будут равномерно распределены внутри произвольного тетраэдра OABC (см. пример на рис. 3 справа). Несложно записать формулы для координат случайных точек внутри произвольного тетраэдра ABCD.

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

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

1. Пронумеруем все тетраэдры в триангуляции (обозначим их количество k) и найдем объем каждого из них: V1, V2,…, Vk (объем многогранника обозначим V).

2. Построим разбиение отрезка mart16.wmf точками V1, V1 + V2, …, V1 + V2 + … + Vk-1.

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

Результаты вычислительного эксперимента в примере 1

Номер эксперимента

№ 1

№ 2

№ 3

№ 4

№ 5

№ 6

№ 7

Число точек n

750

1000

3000

5000

10000

50000

10000

n1/n

0,123

0,130

0,125

0,124

0,123

0,124

0,126

n2/n

0,112

0,123

0,122

0,127

0,122

0,125

0,125

n3/n

0,128

0,131

0,129

0,122

0,125

0,125

0,124

n4/n

0,241

0,216

0,222

0,226

0,223

0,223

0,222

 

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

Пример 1. Будем распределять n случайных точек внутри тетраэдра, образованного векторами mart19.wmf, объем которого V = 1/6. Обозначим V1 – объем тетраэдра, отсекаемого от исходного плоскостью x = 1/2, V2 – объем тетраэдра, отсекаемого от исходного плоскостью y = 1/2, V3 – объем тетраэдра, отсекаемого от исходного плоскостью z = 1/2, V4 – объем куба с ребром 1/3, три смежных ребра которого выходят из начала координат. Число точек, попавших в отсекаемые тетраэдры, обозначим соответственно n1, n2, n3, а в куб – n4. Очевидно, что V1 = V2 = V3 = 1/48, V4 = 1/27.

В таблице показаны отношения n1/n, n2/n, n3/n, n4/n (с точностью до 0,001) для числа случайных точек n = 750, 1000, 3000, 5000, 10000, 50000, 100000. Предельные отношения соответственно равны mart20.wmf и mart21.wmf. Вычислительный эксперимент выполнен в MATLAB.

Заключение

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

Работа выполнена при финансовой поддержке ФГБОУ ВО «КГПУ им. В.П. Астафьева» по договору о выполнении НИР от 21.06.2017 г. № 16-746.


Библиографическая ссылка

Мартынова Е.В., Нигматулин Р.М. ГЕОМЕТРИЧЕСКИЕ ПРИЕМЫ В РЕАЛИЗАЦИИ АЛГОРИТМА ГЕНЕРАЦИИ СЛУЧАЙНЫХ ТОЧЕК ВНУТРИ ПРОИЗВОЛЬНЫХ МНОГОУГОЛЬНИКОВ И МНОГОГРАННИКОВ // Современные наукоемкие технологии. – 2018. – № 1. – С. 27-31;
URL: https://top-technologies.ru/ru/article/view?id=36887 (дата обращения: 03.12.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074