Существует ли система пространственного поиска или система биннинга, которая работает на поверхности (3D) сферы? У меня есть требования, которые
Контейнеры должны быть одинаковыми (чтобы вы могли смотреть в постоянном времени, если существует точка на расстоянии r от любого места на сфере, учитывая постоянную r.) †
Количество бинов должно быть максимально линейным относительно площади поверхности сферы. (В качестве альтернативы, увеличение разрешения поверхности сетки не должно приводить к тому, что она будет расти быстрее, чем область, которую она отображает.)
Я уже рассмотрел
Сферические координаты: не очень хорошо, потому что созданные ячейки крайне неоднородны, что делает их бесполезными для проверки близости.
Сетки куба : Меньше искажений, чем сферические координаты, но все еще очень трудно определить, какие ячейки искать для данного запроса.
3D-воксельное объединение: тратит впустую весь внутренний объем сферы с пустыми ячейками, которые никогда не будут использоваться (а также пустые ячейки в 6 углах ограничивающего куба). Требования к пространству растут с O(n sqrt(n)) с увеличением площади поверхности сферы.
kd-Trees: плохо работают в 3D и имеют техническую логарифмическую сложность, не постоянны для запроса.
Моя лучшая идея для решения заключается в использовании метода биннинга трехмерных вокселей, но каким-то образом исключая воксели, которые сфера никогда не пересечет. Однако я понятия не имею, как определить, какие вокселы исключить, или как рассчитать индекс для такой структуры, учитывая местоположение запроса на сфере.
† Для того, чтобы стоить очков, интервал должен быть минимальным, поэтому хорошая сетка действительно гарантирует постоянный поиск.