lower_bound_2d (найти ближайшее)

[Igors]

Как посчитать радиус поиска для заданной точки - я там выше писал.

Наверное имеется ввиду это

...но начальный радиус для поиска можно найти так dist=max(min(dx), min(dy), где dx, dy - расстояния между соседними точками в отсортированном массиве.

А что это за радиус? Так, просто взятый с потолка? Пример

***                                          ****
***             х(запрос)               ****
***                                          ****

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

[kramer]

А что это за радиус? Так, просто взятый с потолка? Пример

Нет, я там в том же комменте поправился, хотя там тоже не совсем верно. Должно быть так:
dist = max(min(abs(lower_bound_x - x), abs(upper_bound_x - x)),
                 min(abs(lower_bound_y - y), abs(upper_bound_y - y)),
                 min(abs(lower_bound_z - z), abs(upper_bound_z - z)))
Понятно, случай lower_bound_x - x = 0 и ему подобные надо обрабатывать отдельно.

[Igors]

А что это за радиус? Так, просто взятый с потолка? Пример

Нет, я там в том же комменте поправился, хотя там тоже не совсем верно. Должно быть так:
dist = max(min(abs(lower_bound_x - x), abs(upper_bound_x - x)),
                 min(abs(lower_bound_y - y), abs(upper_bound_y - y)),
                 min(abs(lower_bound_z - z), abs(upper_bound_z - z)))
Понятно, случай lower_bound_x - x = 0 и ему подобные надо обрабатывать отдельно.

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

Ладно, предлагаю обсудить более интересные вещи. Мы выяснили что если точки распределены "достаточно равномерно" - то любая разумная схема работает прилично и с (примерно) O(log N). А вот что если нет? Предлагали выбирать ось на которой наибольшее проецируемое расстояние. А если будет так

**
**
**
**                                    *

А главное - как оценить "равномерность"? Напр расстояние между 2 точками по оси = 10. И что, много это или мало? Стоит ли разбивать данные на неск структур или нет?

[kramer]

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

Ну, безусловно, метод не без оверхеда. Но если хорошенько подумать, наверняка можно что-нибудь хорошенько соптимизировать.

А главное - как оценить "равномерность"? Напр расстояние между 2 точками по оси = 10. И что, много это или мало? Стоит ли разбивать данные на неск структур или нет?

Это очень волнующая тема, на самом деле. Выбор "разбивающей" эвристики для различных целей - тема многих и многих диссертаций по CS.
Например, можно попробовать разбивать не медианой, а просто срединной точкой по каждой оси, fabs(min_x-max_x)/2. Дерево получится в общем случае несбалансированным, зато будет принимать в расчет расположение точек в пространстве, в отличие от медианного дерева, которое учитывает лишь их порядок. Понятно, тут уже не обойтись без некоторой структуры данных, хранящей это разбиение.

[Igors]

Это очень волнующая тема, на самом деле. Выбор "разбивающей" эвристики для различных целей - тема многих и многих диссертаций по CS.

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

Например, можно попробовать разбивать не медианой, а просто срединной точкой по каждой оси, fabs(min_x-max_x)/2. Дерево получится в общем случае несбалансированным, зато будет принимать в расчет расположение точек в пространстве, в отличие от медианного дерева, которое учитывает лишь их порядок. Понятно, тут уже не обойтись без некоторой структуры данных, хранящей это разбиение.

Часто сцена небольшая, напр 1х1х1, но есть "floor" - плоскость на которой все стоит, и эта подложка большая, напр 1000х1000. В этом случае разбиение "по пространству пополам" оказывается невыгодным - вся силенка уходит в пустые ноды, а на "облако" сил уже не остается - кончилась глубина дерева

[kramer]

Для точек все  должно быть попроще (ну это я так думаю).

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

Часто сцена небольшая, напр 1х1х1, но есть "floor" - плоскость на которой все стоит, и эта подложка большая, напр 1000х1000. В этом случае разбиение "по пространству пополам" оказывается невыгодным - вся силенка уходит в пустые ноды, а на "облако" сил уже не остается - кончилась глубина дерева

Хм. Есть еще такая штука, называется sliding midpoint rule. Вот, взгляните: http://www.cs.umd.edu/~mount/Papers/cgc99-smpack.pdf
Суть в том, что если в одном из поддеревьев при разбиении посередине точек не оказывается, точка разбиения съезжает в ближайшую по соответствующей оси в другом поддереве. Таким образом уже на третьем разбиении по данной оси граница поддерева будет проходить по границе сцены (1х1х1).

Еще как вариант - можно строить обычные деревья пообъектно, выбирать перебором ближайший объект по расстоянию до bounding box, искать в нем ближайшую точку с помощью соотв. дерева, потом опять же отсекать остальные объекты по расстоянию до bounding box (если больше найденного - то выкинуть), среди оставшихся опять искать с помощью их деревьев. Для объектов с количеством вершин меньше некоторого N можно и вовсе просто перебором искать, это будет быстрее за счет кэша.