Эффективное определение того, какие 3D-линии пересекаются с какими 3D-точками

Question

Дано

1. Набор из множества точек в трехмерном пространстве
   (каждая представлена ​​в виде 3 координат с плавающей запятой (x, y, z))
2. Набор из множества бесконечных линий в трехмерном пространстве
   (каждая представлена ​​произвольной точкой на линии и вектором направления 3D)

Есть ли способ узнатькакая из точек лежит на какой из линий (с небольшим допуском для учета ошибок с плавающей запятой) , что более эффективно, чем тривиальный O(n²) подход проверки каждой точки на каждой строке вВложенный цикл?

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

(Ссылки на соответствующую академическую литературу также приветствуются.)

Answer 1

Это дополнение к ответу Пинхеда.

Рассмотрим ограничивающую рамку из P точек, предполагаемую примерно кубической, и подразделяем ее на C³ клетки. Если распределение точек равномерное, каждая ячейка будет содержать в среднем P/C³ точек.

Теперь для каждой линии вы найдете все ячейки, которые она пересекает, в процессе, аналогичном рисованию цифровой линии, и выбудет пересекать в среднем αC клеток, где α - маленькая константа. Следовательно, общая рабочая нагрузка для поиска пропорциональна L P/C³.

В любом случае, вы должны учитывать время инициализации сетки, пропорциональное C³. Следовательно, общее значение, включая инициализацию, имеет вид C³+ ß L P/C² и сводится к минимуму на C~(L P)^(1/5), что дает сложность времени и пространства O((L P)^(3/5)), что значительно экономит более O(L P).

---

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

Точные оценки ускорения сделать намного сложнее, но вы можете ожидать сложность времени, такую ​​как O((L + P) Log(P)).

Answer 2

Разделите трехмерное пространство на кубы со стороны N, чтобы куб мог содержать более одной точки. Бесконечная линия будет пересекать бесконечное количество кубов, но проверка наличия точки у куба занимает O (1). Когда линия пересекает куб с более чем одной точкой, вы проверяете только точки в этом кубе, которые будут меньше, чем общий размер точек, если 1) они распределены равномерно 2) вы используете амортизированные константы ( постоянное амортизированное время ). С точки зрения среднего сценария вы проверяете все точки одновременно в точке O (N ^ 2), если все точки упакованы внутри одного куба. Вы также можете иметь кубики внутри кубов, но это больше бухгалтерия.

Эта идея вдохновлена ​​квадродеревом: https://en.wikipedia.org/wiki/Quadtree

Я получил ноль принятых ответов ... так что возьмите это с крошкой соли или примите мой ответ и помогите братану :)