Поиск точек, близких к вектору в трехмерном пространстве

Question

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

Существуют ли какие-либо алгоритмы C ++ для этого подвига? И если да (или нет), то какая математическая концепция влечет за собой или будет ли это иметь место, поскольку я хотел бы попытаться понять это и связать свой мозг с кренделем.

(Этот алгоритм будет работать в пространстве с, возможно, 100 000 точек в нем, он должен будет проверить около 1 000 000 векторов и должен завершить эти векторы в течение 1/30 секунды. Я, конечно, сомневаюсь, что любой алгоритм совершите этот подвиг вообще, но будет интересно посмотреть, правда это или нет.

Answer 1

Возможно, вы захотите сохранить свои точки в некоторой пространственной структуре данных.На ум приходят:

1. окт-деревья
2. деревья BSP
3. кд-деревья

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

Дерево BSP Двоичное пространство, разделяющее дерево .Это дерево плоскостей в трехмерном пространстве, образующее двоичное дерево.Основная проблема использования этого для вашей проблемы состоит в том, что вам, возможно, придется сделать много квадратных корней при прохождении, чтобы найти расстояние до плоскостей.Принцип тот же, хотя, когда у вас есть меньше, чем некоторое количество точек, вы формируете лист с этими точками в нем.Все листья в дереве BSP являются выпуклыми многоугольниками (за исключением листьев, расположенных по периметру, которые будут бесконечно большими многоугольниками).При построении BSP вы хотите разделить точки пополам для каждого шага, чтобы действительно получить O (log n) поисков.

KD-дерево - это особый случай BSP, где все плоскости выровнены по оси,Как правило, это значительно ускоряет тесты на них, но не позволяет оптимизировать плоскости на основе вашего набора точек.

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

Answer 2

Это может помочь вам понять октри, когда вы можете думать о ней как о кривой, которая заполняет пространство, пересекающее каждую координату только один раз и не пересекая себя.Кривая отображает 3d-сложность на 1d-сложность.Есть некоторые из этой кривой монстров, такие как кривая z, кривая Гильберта и кривая Мура.Последний является копией четырех кривых Гильберта и имеет очень хорошее качество заполнения пространства.Но разве поиск ближайших точек не решается алгоритмом Дейкстры?