Kirill Pankratov (neznaika_nalune) wrote,
Kirill Pankratov
neznaika_nalune

Categories:

Математическое

Когда-то, будучи в Мassachusetts Institute of Technology, я много занимался разными математическими вычислительными алгоритмами и написал кучу больших и маленьких компьютерных программ на эти темы (в основном на Матлабе - языке лучше всего подходящем для такой математической "мастерской"). Некоторые из них стали популярны и использовались множеством людей по всему миру.

Одна из таких штучек - достаточно серьёзный пакет по вычислительной геометрии и пространственному анализу Spatial and Geometric Analysis toolbox (SaGA) (ещё здесь - кто-то поместил на сервере Woods Hole Oceanographic Institution). Там много всего - всевозможные двух-, трёх- и многомерные интерполяциии и аппроксимации, вычислительные операции с полигонами и полиэдрами, построения выпуклых оболочек (convex hull) в пространстве любой размерности, сегментация Вороного и Деланэ (в многомерных пространствах), генерация сеток, вращение твёрдого тела, всякая графика и т.д.

Я практически не возвращался к этому пакету лет 10, но он продолжал жить своей жизнью. На него сотни ссылок на интернете (даже до сих пор, после стольких лет), его переводили на другие языки, он упоминается в библиографиях в десятках статей и диссертаций и т.д. И до сих пор я примерно раз в две недели получаю письма от пользователей со всего мира с попросами по нему.

Сегодня получил очередное такое - на этот раз касается одной из маленьких вспомогательных утилит, которую я написал с полпинка в качестве разминки - построение наиболее равномерного распределения N точек по сфере:

Hello Dr. Pankratov,

I've recently come across your matlab program for
equally distributing points on a sphere (eqdsph.m).
I was hoping you could explain your methodology as
I am trying to do something similar and have reached
a dead end. Any assistance you could offer would be
greatly appreciated.


Это такая полезная штучка - для всевозможных графических и вычислительных приложений. Решение которое я использовал - чисто физическое. Начинаем со случайно разбросанных точек на сфере. При этом считаем точки как заряженные отталкивающиеся частицы - такие электрончики на металлическом шаре. Считаем силы действующие на каждую частицу, проецируем на сферу и двигаем в направлении силы, пропорционально ей. Итерируем много раз и вскоре получаем вполне равномерное распределение. Вот так начинается - случайно-однородное распределение точек по сфере:
http://puddle.mit.edu/~glenn/kirill/SAGAPIC/chullrs100.gif

И в конце концов получается вот что:
http://puddle.mit.edu/~glenn/kirill/SAGAPIC/chulled100.gif

Вот код основной функции: http://puddle.mit.edu/~glenn/kirill/SAGA/eqdsph.m

Кстати, заодно весьма элегантный метод создания случайно-однородных точек на сфере. Если просто случайно-однородное распределение спроецировать на сферические координаты, будет плохо - концентрация точек на полюсах, подобно сетке параллелей и меридианов на глобусе. А надо так: вместо случайно-однородного делаем нормальное (гауссовое) распределение по всем трём координатам. Это даёт полную сферическую симметрию. Потом проецируем точки на сферу - делим все координаты на длины вектора из центра до точки. Получаем идеальное случайно-однородное распределение на сфере. Вот програмка: http://puddle.mit.edu/~glenn/kirill/SAGA/randsph.m

Редко сейчас возвращаюсь к этим штучкам, но весьма занятно бывает...
Subscribe

  • Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 31 comments