Математическое
Когда-то, будучи в М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
Редко сейчас возвращаюсь к этим штучкам, но весьма занятно бывает...
Одна из таких штучек - достаточно серьёзный пакет по вычислительной геометрии и пространственному анализу 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
Редко сейчас возвращаюсь к этим штучкам, но весьма занятно бывает...