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

Question

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

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

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

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

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

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

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

Answer 1

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

Answer 2

Я изобрел кривую (я уверен, что я не 1-й), которая вращается вдоль сферы от полюса к полюсу. Осталось постоянное расстояние от соседних обмоток (если я все сделал правильно). Для 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 и выполните поиск в этой обмотке таким же образом.

Критика

Answer 3

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

Answer 4

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

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

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

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

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

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

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

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

Answer 5

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

Answer 6

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

Answer 7

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

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

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