Ближайший сосед на единичной сфере с примерно равномерно распределенными точками

Я пишу программу, которая реализует SCVT (Spherical Centroidal Voronoi Tesselation). Я начинаю с набора точек, распределенных по единичной сфере (у меня есть выбор для случайных точек или спирали равной площади). Будет от нескольких сотен до 64 тысяч баллов.

Затем мне нужно создать несколько миллионов случайных точек выборки, для каждой выборки найти ближайшую точку в наборе и использовать ее для вычисления «веса» этой точки. (Этот вес, возможно, придется искать из другого сферического набора, но этот набор будет оставаться статичным для любого заданного запуска алгоритма.)

Затем я перемещаю исходные точки в вычисленные и повторяю процесс, вероятно, 10 или 20 раз. Это даст мне центры плиток Вороного для последующего использования.

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

О, я использую координаты x, y, z, но это не высечено на камне. Похоже, это все упростит. Я также использую C, поскольку я наиболее знаком с ним, но также не привязан к этому выбору. :)

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

edit: [Извините, я думал, что понял заголовок и теги. Я легко могу генерировать случайные точки. Проблема заключается в поиске ближайшего соседа. Какой эффективный алгоритм, когда все точки находятся на единичной сфере?]


geometry nearest-neighbor
person Jerry B    schedule 13.04.2009    source источник
comment
Что именно вы спрашиваете - хотите ли вы знать, как генерировать точки, случайно распределенные на сфере, или как вычислять ближайшего соседа на сферической поверхности, или что-то еще? Это не совсем понятно.   -  person David Z    schedule 13.04.2009

Ответы (7)


arrow_upward
3
arrow_downward

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

person Don Reba    schedule 14.04.2009
comment
Меня осенила идея уменьшить его почти в другом измерении. Если я расположу точки по спирали на постоянном расстоянии от предыдущего витка, поиск может быть почти линейным. Наверное, нужно всего лишь проверить 2 коротких дистанции на линии ... - person Jerry B; 15.04.2009

arrow_upward
1
arrow_downward

Вы можете обнаружить, что организация ваших точек в структуру данных, называемую Octree, полезна для эффективного поиска ближайших точек. См. http://en.wikipedia.org/wiki/Octree.

person David Plumpton    schedule 14.04.2009

arrow_upward
1
arrow_downward

Я придумал кривую (уверен, что я не первый), которая закручивается по сфере от полюса к полюсу. Остается постоянное расстояние от соседних обмоток (если я все сделал правильно). Для z (-1 на южном полюсе до +1 на северном полюсе):

n = a constant defining a given spiral
k = sqrt(n * pi)

r = sqrt(z^2)
theta = k * asin(z)
x = r * cos(theta)
y = r * sin(theta)

Он совершает k/2 оборотов вокруг сферы с каждой sqrt(4pi/n) обмоткой из соседних обмоток, в то время как наклон dz/d(x,y) равен 1/k.

В любом случае установите k таким образом, чтобы расстояние между намотками перекрывало самую большую плитку на сфере. Для каждой точки в основном наборе вычислите theta ближайшей точки на кривой и проиндексируйте список точек по этим числам. Для данной контрольной точки вычислите ее (theta ближайшей точки на кривой) и найдите ее в индексе. Найдите оттуда наружу (в обоих направлениях) до theta значений, которые находятся на таком же расстоянии, как ваш текущий ближайший сосед. После достижения этого предела, если расстояние до этого соседа меньше расстояния от тестовой точки до следующей соседней обмотки, вы нашли ближайшего соседа. Если нет, перескочите значение theta на 2pi и ищите эту обмотку таким же образом.

Критика?

person Jerry B    schedule 18.04.2009

arrow_upward
0
arrow_downward

Вот статья о поиске соседей: http://en.wikipedia.org/wiki/Nearest_neighbor_search Насколько я понимаю, вы можете использовать тривиальный алгоритм, пройдя через все центры Вороного и рассчитав расстояние между вашей точкой и центральной точкой в ​​3D.

distance_2 = (x - x_0)^2 + (y - y_0)^2 + (z - z_0)^2

где (x_0, y_0, z_0) - точка интереса (щелчок) для вас, а {(x, y, z)} - центры Вороного. Наименьшее расстояние даст вам ближайший центр.

person Artem    schedule 13.04.2009
comment
По сути, это алгоритм наихудшего случая, O (n), требующий сканирования всех точек для каждой контрольной точки. Для кода пользовательского интерфейса это, вероятно, было бы приемлемо. Для многих миллионов точек выборки предпочтительнее использовать метод O (logn) (или меньше). - person Jerry B; 13.04.2009
comment
@Jerry B, все могло быть хуже. О (п) неплохо. - person mmcdole; 14.04.2009
comment
Что ж, это O (n) для каждого поиска, что делает весь алгоритм O (n * m). Это приближается к триллиону сравнений. Поскольку сканирование всего списка - это наивный метод, я не понимаю, как можно было бы сделать хуже, не делая этого специально. - person Jerry B; 14.04.2009
comment
Тогда я, наверное, ошибся. Я думал, что у вас 64К точек, после этого выбрано небольшое количество центров Вороного (я предполагал меньше 100), а затем только для одной точки (щелчок мышью) вам нужно найти ближайшую группу, то есть ближайший центр Вороного. - person Artem; 14.04.2009
comment
если ваши точки находятся в реляционной базе данных, просто добавьте предложение where, чтобы ограничить выбранные точки только теми, которые примерно достаточно близки, чтобы их можно было рассматривать при вычислении O (n), как предлагается. Я искал похожие цвета в сфере L a b *, как эта, и это было очень быстро. - person Peter Perháč; 14.04.2009
comment
Артем: Я начинаю с 64К точек и по множеству точек выборки нахожу ближайшую точку в этом наборе. Вычислите взвешенное расстояние между ними и общую сумму для каждой из 64 тысяч точек. Это определяет, куда переместятся точки набора 64K. Позже мне также понадобятся щелчки мышью. - person Jerry B; 15.04.2009
comment
МастерПетер: Пока точки просто в массиве в памяти. Для * миллионов сэмплов против 64К точек это все равно займет много времени. Это делается для создания карты для игры, и я не думаю, что люди захотят ждать минуты, не говоря уже о часах, чтобы начать играть. :) - person Jerry B; 15.04.2009

arrow_upward
0
arrow_downward

Использование KD Trie - хороший способ ускорить поиск. Вы также можете получить значительно лучшую производительность, если будете терпеть некоторые ошибки. Библиотека ANN предоставит вам результат в пределах выбранного вами ε.

person Don Reba    schedule 13.04.2009
comment
Нет, ИНС не сработает. Для вычисления центроида с любой точностью требуется точное NN. Хорошо ли KD Trie обрабатывает точки, находящиеся на единичной сфере? На странице Wiki на KD Tries упоминается ANN, но не NN. Возможно, мне придется сделать ИНС с последующим поиском ближайших точек для точного поиска нейронной сети. - person Jerry B; 14.04.2009
comment
При необходимости ε может быть равным нулю. Хотя тогда существует более широкий выбор реализаций, и библиотека ИНС не обязательно лучшая. У него есть огромный недостаток, заключающийся в том, что он не является потокобезопасным. - person Don Reba; 14.04.2009

arrow_upward
0
arrow_downward

В ПОРЯДКЕ. NEARPT3 http://www.ecse.rpi.edu/Homepages/wrf/Research/nearpt3/nearpt3.pdf. И все зависит от того, сколько места вы можете позволить себе использовать для своих N точек. Если это O (N * logN), то существуют такие алгоритмы, как kD-tree (http://www.inf.ed.ac.uk/teaching/courses/inf2b/learnnotes/inf2b-learn06-lec.pdf), который будет работать для O (logN), чтобы найти ближайшую точку. В случае 64К точки Nlog_2 N = около 10 ^ 6, что легко помещается в памяти современного компьютера.

person Artem    schedule 14.04.2009
comment
Хорошего чтения. Одна вещь, которая поразила меня в конспектах лекций, - это комментарий о том, что время имеет тенденцию идти экспоненциально по размеру. Таким образом, трехмерное kD-дерево кажется расточительным для того, что по сути является двумерными данными. В остальном звучит неплохо. - person Jerry B; 15.04.2009
comment
Правильно. Однако вы должны быть осторожны, потому что ближайший сосед в сферических координатах не обязательно является ближайшим соседом в декартовых координатах. - person Don Reba; 15.04.2009

arrow_upward
0
arrow_downward

Другая возможность, более простая, чем создание дерева квадратов, - использование матрицы соседства.

Сначала поместите все свои точки в двумерную квадратную матрицу (путем преобразования точек в полярные координаты). Затем вы можете запустить полную или частичную пространственную сортировку, так что точки будут упорядочены внутри матрицы.

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

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

Вы можете прочитать более подробную информацию об этой идее в следующем документе (его PDF-копии вы найдете в Интернете): Сверхмассивное моделирование толпы на графическом процессоре на основе Emergent Behavior.

Этап сортировки дает вам интересный выбор. Вы можете использовать только сортировку с транспонированием чет-нечет, описанную в документе, которая очень проста в реализации (даже в CUDA). Если вы выполните только один проход, это даст вам частичную сортировку, которая уже может быть полезна, если ваша матрица почти отсортирована. То есть, если ваши точки перемещаются медленно, это сэкономит вам много вычислений.

Если вам нужна полная сортировка, вы можете запустить такой проход четно-нечетной транспозиции несколько раз (как описано на следующей странице Википедии):

http://en.wikipedia.org/wiki/Odd%E2%80%93even_sort

person mgmalheiros    schedule 08.02.2014
comment
Ой. Больно читать. Я предполагаю, что либо статья была написана на португальском языке, а затем переведена на английский (плохо), либо сам английский автора ужасен. - person Jerry B; 09.02.2014
comment
Кроме того, двухмерная сортировка в большинстве случаев не имеет смысла. Если вы будете поступать так же, как он, чередуя проходы по осям X и Y, то каждый проход потенциально (и, вероятно) разрушает любую гарантию сортировки от предыдущего прохода в другом направлении. Это означает, что даже полный N проход в каждом направлении не гарантирует сортировки. Фактически, даже неясно, что будет означать сортировку в двух измерениях (аналогично невозможности упорядочить комплексные числа). И если вы выполняете полную сортировку в одном направлении, а затем полную сортировку в другом, первая сортировка по сути является избыточной. - person Jerry B; 09.02.2014
comment
@jerry, на самом деле вы сортируете пары, но меняете порядок важности для каждого направления. Итак, когда вы сортируете столбцы, вы сначала сравниваете по X, а если они совпадают, сравниваете по Y. Для строк это аналогично, но вы сравниваете сначала по Y, а затем, если необходимо, по X. Код сортировки действительно похож на сортировку по четным и нечетным в Википедии, но с четырьмя двойными циклами (четные столбцы, нечетные столбцы, четные и нечетные строки). Сам реализовал, работает. Но, конечно, сложность составляет O (n²), потому что вам может потребоваться несколько проходов, чтобы все это отсортировать. - person mgmalheiros; 10.02.2014
comment
Я разместил код, который использовал, в pastebin. Кроме того, я взял образцы изображений, где точки имеют цветовую кодировку: красный (X) и зеленый (Y). Итак, у вас есть начальное состояние, полностью случайное в ранее. Я позвонил partial_sort() 10 раз и получил после. - person mgmalheiros; 10.02.2014
comment
Конечно, поскольку матрица похожа на уплотнение, чем более равномерно вы установите точки, тем лучше будет сортировка. Для моего конкретного приложения (симуляция плотных частиц) это работает очень хорошо. Но если у вас есть большие пустые области или очень плотные кластеры в вашем наборе данных, результат будет не очень хорошим (но у вас будут те же проблемы при использовании пространственного хеширования). Фактически, я ранее использовал пространственное хеширование в CUDA, но потратил много времени на повторную сортировку ведер (когда частицы перемещались от одного к другому). Это решение идеально подходит для меня (даже больше при использовании поиска в текстурной памяти). - person mgmalheiros; 10.02.2014