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

Your points are uniformly distributed over the sphere. Therefore, it would make a lot of sense to convert them to spherical coordinates and discretize. Searching the 2D grid first would narrow down the choice of nearest neighbour to a small part of the sphere in constant time.

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

Вот статья по поиску соседей: 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)} - центры Вороного. Наименьшее расстояние даст вам ближайший центр.

Я разработал кривую (я уверен, что я не 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 так, чтобы расстояние между обмотками покрывало самую большую плитку на сфере. Для каждой точки в основном наборе вычислите тета ближайшей точки на кривой и индексируйте список точек по этим числам. Для данной контрольной точки рассчитайте ее s ( тета ближайшей точки на кривой), и найдите это в индексе. Найдите оттуда (в обоих направлениях) значения тета , которые находятся так же далеко, как ваш текущий ближайший сосед. После достижения этого предела, если расстояние до этого соседа меньше расстояния от контрольной точки до следующей соседней обмотки, вы нашли ближайшего соседа. Если нет, перейдите к значению theta по 2pi и выполните поиск этой обмотки таким же образом.

Критика? Мы нашли ближайшего соседа. Если нет, перейдите к значению theta по 2pi и выполните поиск этой обмотки таким же образом.

Критика? Мы нашли ближайшего соседа. Если нет, перейдите к значению theta по 2pi и выполните поиск этой обмотки таким же образом.

Критика?

OK. NEARPT3 http://www.ecse.rpi.edu/Homepages/wrf/Research/nearpt3/nearpt3.pdf algorithm could be helpful in your case. And it all depends on how many space you can afford to use for your N points. If it is O(N*logN) then there are algorithms like kD-tree based (http://www.inf.ed.ac.uk/teaching/courses/inf2b/learnnotes/inf2b-learn06-lec.pdf) which would work for O(logN) to find nearest point. In case of 64K point Nlog_2 N = about 10^6 which is easily can fit into memory of modern computer.

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