Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,074

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

Копытов Н.П. 1 Митюшов Е.А. 1
1 Уральский федеральный университет имени первого Президента России Б.Н. Ельцина
Рассматривается проблема равномерного распределения точек на произвольных аналитических поверхностях в трехмерном пространстве. Представлены краткие сведения об истории развития проблемы и различные подходы к ее решению. Отмечаются особо важные работы, посвященные данной теме. Предлагается универсальный алгоритм равномерного распределения точек на аналитических поверхностях, заданных параметрическим способом. Описывается методология получения функции плотности совместного распределения параметров, соответствующей равномерному распределению точек на поверхности. Описывается обобщенный метод Неймана для генерации двумерной случайной величины по известной функции плотности совместного распределения. Демонстрируются визуальные результаты работы алгоритма, реализованного в системе компьютерной математики Wolfram Mathematica 7.0. Приводятся примеры распределения точек на поверхностях сферы, тора, геликоида, поверхности «Падающая капля» и бутылки Клейна. По полученным результатам даются выводы об эффективности и универсальности предложенного алгоритма, возможностям его развития и усовершенствования.
равномерное распределение точек на поверхностях
генерация двумерной случайной величины
метод Неймана
статистическое моделирование
1. Александров А.Д., Нецветаев Н.Ю. Геометрия: учебник. – 2-е изд., испр. – СПб.: БХВ-Петербург, 2010. – 624 с.
2. Копытов Н.П., Митюшов Е.А. Математическая модель армирования оболочек из волокнистых композиционных материалов и проблема равномерного распределения точек на поверхностях // Вестник ПГТУ. Механика. – 2010. – № 4. – C. 55–66.
3. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. – М., 1978. – 832 с.
4. Кривошапко С.Н., Иванов В.Н. Энциклопедия аналитических поверхностей. – М.: Книжный дом «ЛИБРОКОМ», 2010. – 560 с.
5. Монаков А.А. Основы математического моделирования радиотехнических систем: учеб. пособие. – ГУАП. – СПб., 2005. – 100 с.
6. Andrew J.P. Maclean. Parametric Equations for Surfaces. – URL: https://wiki.sch.bme.hu/pub/Infoalap/SzgGraf/ParametricSurfaces.pdf (дата обращения: 20.08.2011).
7. Bendito E., Carmona A., Encinas A.M., Gesto J.M. Computational cost of the Fekete problem I: The Forces Method on the 2-Sphere, preprint. – URL: http://www-ma3.upc.es/users/bencar/articulos/YJCPH2424.pdf (дата обращения: 27.09.2011).
8. Bendito E., Carmona A., Encinas A.M., Gesto J.M. Computational cost of the Fekete problem II: on Smale’s 7th problem, preprint. – URL: http://www-ma3.upc.es/users/bencar/articulos/YJCPH2424.pdf (дата обращения: 27.09.2011).
9. Marsaglia G. Choosing a Point from the Surface of a Sphere. – Ann. Math. Stat. 43, 645–646, 1972.
10. Melfi G., Schoier G. Simulation of random distributions on surfaces. – http://www.sis-statistica.it/files/pdf/atti/RSBa2004p173-176.pdf (дата обращения: 20.09.2011).
11. Rubinstein R.Y., Kroese D.P. Simulation and the Monte Carlo methods. – Second Edition. – Wiley-Intersciens, 2007. – 345 p.
12. Tashiro Y. On methods for generating uniform random points on the surface of a sphere. – Ann. Inst. Stat. Math. 29, 295–300, 1977.
13. Weisstein E.W. Sphere Point Picking. From MathWorld--A Wolfram Web Resource. – URL: http://mathworld.wolfram.com/SpherePointPicking.html (дата обращения: 27.09.2011).

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

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

Наиболее четко постановка рассматриваемой задачи, возможные пути ее решения иллюстрируются на одном из частных случаев – проблеме равномерного распределения точек на поверхности сферы [9, 11–13]. С середины XX века в ведущих мировых научных изданиях, таких как журналы «Biometrics», «Annals of Mathematical Statistics» и т.д., стали появляться работы, описывающие различные подходы к решению проблем равномерного распределения точек на поверхности сферы. Как итог многолетнего исследовательского процесса эти алгоритмы стали входить в уже ставшие классическими труды по теории вероятности, математической статистики и методам Монте-Карло [11]. Также следует отметить, что задача равномерного распределения точек на поверхности сферы тесно связана с одной из крупнейших математических проблем XXI века, включенных в список Стивена Смейла (seventh Smales’s problem [7, 8]). Проблеме также посвящена отдельная страница в популярной математической интернет-энциклопедии Wolfram MathWorld [13]. Наряду с феноменологическими подходами к решению задачи равномерного распределения точек на поверхности сферы [7, 8] применяются методы статистического моделирования [9, 12, 13]. Помимо алгоритмов равномерного распределения точек на поверхности сферы в трехмерном «физическом» пространстве также немало работ посвящено решению аналогичной задачи для случая с многомерным пространством. Особо стоит отметить работу «Simulation of random distributions on surfaces» (G. Melfi, G. Schoier, [10]), в которой предлагается метод равномерного распределения точек уже на поверхностях, заданных явным образом в виде функции z = z(x, y).

Алгоритмы равномерного распределения точек на сфере, а также на поверхностях, заданных явным образом в виде функции z = z(x, y), основанные на методе взятия обратной функции для плотности распределения случайной величины и методе Неймана, были изложены авторами в работе [2], в которой также обсуждалась возможность обобщения этих методов для случаев общего задания поверхностей в параметрической форме. Как обобщающий итог исследований, посвященных рассматриваемой проблематике, в данной статье представлен алгоритм равномерного распределения точек на произвольных аналитических поверхностях, которые могут быть заданы в параметрической форме.

В основу алгоритма положен метод статистического моделирования, заключающийся в генерировании координат точек по вычисляемой аналитически функции плотности совместного распределения параметров, соответствующей равномерному распределению точек на поверхности. Для генерирования значения двумерной случайной величины используется обобщенный метод Неймана [8]. Все алгоритмы реализованы в системе компьютерной математики (СКМ) Wolfram Mathematica 7.0, в ней же получены и все визуальные модели.

Общая постановка задачи и методология ее решения

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

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

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

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

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

Пусть поверхность задана параметрическими уравнениями x = x(u, v), y = y(u, v), z = z(u, v) на области D = {u1 ≤ u ≤ u2; v1 ≤ v ≤ v2}. Необходимо найти аналитически f(u, v) – функцию плотности совместного распределения параметров u, v, соответствующую равномерному распределению точек на рассматриваемой поверхности.

В случае, когда точки равномерно распределяются на поверхности, вероятность попадания произвольной точки А на элемент поверхности dS с одной стороны равна:

Eqn183.wmf

где, согласно [1, 3],

Eqn184.wmf

Eqn185.wmf

(E, F, G – коэффициенты первой квадратичной формы поверхности). Следовательно,

Eqn186.wmf

С другой стороны, вероятность попадания точки А на элемент поверхности равна

Eqn187.wmf

Принимая во внимание вышеизложенные соотношения, получаем равенство:

Eqn188.wmf

Откуда окончательно находим искомую функцию плотности совместного распределения параметров, соответствующую равномерному распределению точек на рассматриваемой поверхности:

Eqn189.wmf

Генерируя значения параметров u, v с использованием функции f(u, v), получим равномерное распределение точек на поверхности.

Метод Неймана генерирования многомерной случайной величины по известной функции плотности совместного распределения параметров

Для моделирования одномерной случайной величины по функции плотности распределения применяются различные методы [5, 11]. Например, метод взятия обратной функции удобен в случаях, когда можно получить аналитически обратную функцию. Однако применение данного метода усложняется в случаях многомерных распределений зависимых случайных величин. Универсальным методом генерирования случайных величин по известным плотностям распределения является метод Неймана (метод усечения), суть которого рассмотрим сначала на примере одномерной случайной величины. В этом случае алгоритм реализуется следующим образом [5, 11]:

1. Функция плотности распределения вписывается в прямоугольник.

2. Генерируются два независимых числа эталонным генератором случайной величины с равномерным распределением на интервале (0, 1) и масштабируются по сторонам прямоугольника.

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

4. Повторяются действия 2–3 до тех пор, пока не будет сгенерировано необходимое число точек.

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

1. Определяется Eqn190.wmf – максимальное значение функции f(u, v) на области D = {u1 ≤ u ≤ u2; v1 ≤ v ≤ v2}.

2. Генерируются числа

Eqn191.wmf, Eqn192.wmf,

где R – эталонный генератор случайного числа с равномерным распределением на интервале (0, 1);

3. Выполняется проверка: если

Eqn193.wmf,

где R – эталонный генератор случайного числа с равномерным распределением на интервале (0, 1), то точка принимается, в противном случае отбрасывается.

4. Повторяются действия 2–3 до тех пор, пока не будет сгенерировано необходимое число точек.

Визуализация результатов

Описанные выше алгоритмы были реализованы в пакете Wolfram Mathematica 7.0, который позволяет также строить визуальные модели, что является удобным для контроля работы программы и демонстрации результатов. Ниже представлены некоторые визуальные результаты работы алгоритма.

На рис. 1 представлена поверхность сферы и равномерное распределение 15000 точек на ней. Поверхность сферы задана уравнениями:

Eqn194.wmf

Eqn195.wmf

Eqn196.wmf

где 0 ≤ u ≤ π, 0 ≤ v ≤ 2π.

pic_67.tif

Рис. 1. Равномерное распределение 15000 точек на поверхности сферы, ViewPoint: {1,2,2}

На рис. 2 представлена поверхность тора и равномерное распределение 20000 точек на ней. Поверхность тора задана уравнениями:

Eqn197.wmf

Eqn198.wmf

Eqn199.wmf

где 0 ≤ u ≤ 2π, 0 ≤ v ≤ 2π.

pic_68.tif

Рис. 2. Равномерное распределение 20000 точек на поверхности тора, ViewPoint: {1,2,2}

На рис. 3 представлена поверхность геликоида и равномерное распределение 15000 точек на ней. Поверхность геликоида задана уравнениями:

Eqn200.wmf

Eqn201.wmf

Eqn202.wmf

где 0 ≤ u ≤ 2π, 0 ≤ v ≤ 2π.

pic_69.tif

Рис. 3. Равномерное распределение 15000 точек на поверхности геликоида, ViewPoint: {1,2,2}

На рис. 4 представлена поверхность «Падающая капля» и равномерное распределение 20000 точек на ней. Поверхность «Падающая капля» задана уравнениями [4]:

Eqn203.wmf

Eqn204.wmf

Eqn205.wmf

где 0 ≤ u ≤ 2π, 0 ≤ v ≤ 1.

pic_70.tif

Рис. 4. Равномерное распределение 20000 точек на поверхности «Падающая капля», ViewPoint: {1,2,2}

На рис. 5 представлена поверхность бутылки Клейна и равномерное распределение 20000 точек на ней. Поверхность бутылки Клейна задана уравнениями [6]:

Eqn206.wmf

Eqn207.wmf

Eqn208.wmf

где –π/2 ≤ π/2 , 0 ≤ v ≤ 2π.

pic_71.tif

Рис. 5. Равномерное распределение 15000 точек на поверхности бутылки Клейна, ViewPoint: {1,2,2}

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

Выводы

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

Рецензенты:

Берестова С.А., д.ф.-м.н., доцент, заведующая кафедрой теоретической механики Института фундаментального образования Уральского федерального университета имени первого Президента России Б.Н. Ельцина, г. Екатеринбург;

Сесекин А.Н. д.ф.-м.н., профессор, заведующий кафедрой прикладной математики Уральского энергетического института Уральского федерального университета имени первого Президента России Б.Н. Ельцина, г. Екатеринбург.

Работа поступила в редакцию 19.02.2013.


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

Копытов Н.П., Митюшов Е.А. УНИВЕРСАЛЬНЫЙ АЛГОРИТМ РАВНОМЕРНОГО РАСПРЕДЕЛЕНИЯ ТОЧЕК НА ПРОИЗВОЛЬНЫХ АНАЛИТИЧЕСКИХ ПОВЕРХНОСТЯХ В ТРЕХМЕРНОМ ПРОСТРАНСТВЕ // Фундаментальные исследования. – 2013. – № 4-3. – С. 618-622;
URL: http://www.fundamental-research.ru/ru/article/view?id=31243 (дата обращения: 23.10.2019).

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

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