Пространственные структуры данных в C
Вы можете использовать структуру запроса Spring:
Query query = new Query();
query.addCriteria(Criteria.where("id").is(10).orOperator(Criteria.where("id").is(20));
this.client.findOne(query, clazz);
5 ответов
Это кажется, что Вы хотели бы реализовать kd-дерево, которое позволит Вам более быстро искать N-мерное пространство. Существует еще некоторая информация и ссылки на реализации в Каменном Репозитории Алгоритма Ручья.
Так как Ваше поле статично (которым я предполагаю, что Вы подразумеваете, что hyper сферы не перемещаются), затем быстрым решением, о котором я знаю, является Kdtree.
Можно или сделать собственное, или использовать чужой, как этот: http://libkdtree.alioth.debian.org/
Как лучше всего приблизиться, это для Вашей проблемы зависит от нескольких факторов, которые Вы не описали: - то же расположение гиперсферы будет использоваться для многих вычислений коллизии частицы? - Универсальный размер гиперсфер? - То, каковы перемещение частицы (например, прямая линия / кривая) и то перемещение, затронуто сферами? - Вы полагаете, что частица имеет нулевой объем?
Я предполагаю, что частица не имеет простого перемещения прямой линии, поскольку это было бы относительно быстрым вычислением нахождения самой близкой точки между строкой и точки, которая, вероятно, будет о той же скорости как находящий, какое из полей строка пересекает с (для определения где в n-дереве для исследования).
Если бы Ваши положения гиперсферы фиксируются для большого количества коллизий частицы, затем вычисляя разбиение Вороного/, составление мозаики Dirichlet дало бы Вам быстрый способ более позднего открытия точно, какая сфера является самой близкой к Вашей частице для любой данной точки в пространстве.
Однако для ответа на исходный вопрос о octrees/quadtrees/2^n-trees в n размерах Вы запускаете с (hyper) - куб, который содержит область пространства, которым Вы интересуетесь. Это будет подразделено на 2^n гиперкубы при размышлении содержания, которое будет слишком сложным. Это продолжается рекурсивно, пока у Вас нет только простых элементов (например, один центроид гиперсферы) в вершинах. Теперь, когда n-дерево создается, Вы используете его для обнаружения коллизий путем взятия пути частицы и пересечения его с внешним гиперкубом. Перекрестное положение скажет Вам, какой гиперкуб в следующем уравнивают дерева для посещения затем, и Вы определяете положение пересечения со всеми 2^n гиперкубы на том уровне, после вниз, пока Вы не достигаете вершины. После того как Вы достигаете листа, можно исследовать взаимодействия между путем частицы и гиперсферой, сохраненной в том листе. Если у Вас есть коллизия, Вы закончили, иначе необходимо найти точку выхода пути частицы от текущего листа гиперкуба и определить, в какой гиперкуб это перемещается затем. Продолжите, пока Вы не найдете коллизию или полностью оставите полный гиперкуб ограничения.
Эффективно нахождение соседнего гиперкуба при выходе из гиперкуба является одной из самых сложных частей этого подхода. Для 2^n могут быть адаптированы подходы Samet деревьев {1, 2}. Для kd-деревьев (двоичные деревья) подход предлагается в {3} раздел 4.3.3.
Эффективное внедрение может быть столь же простым как хранение списка 8 указателей от каждого гиперкуба до его дочерних гиперкубов и маркировки гиперкуба специальным способом, если это - лист (например, сделайте весь ПУСТОЙ УКАЗАТЕЛЬ указателей).
Описание делящегося пространства для создания дерева квадрантов (который можно обобщить к n-дереву) может быть найдено в Klinger & Dyer {4}
Поскольку другие упомянули, что kd-деревья могут больше подойти, чем 2^n-trees, поскольку расширение произвольного числа размеров более просто, однако они приведут к более глубокому дереву. Также легче адаптировать положения разделения для соответствия геометрии гиперсфер с kd-деревом. Описание выше обнаружения коллизий в 2^n дерево одинаково применимо к kd-дереву.
{4} Эксперименты в представлении изображения с помощью регулярного разложения, Klinger, A., и Красильщика, C.R. E, Comptr. Обработка графики и Обработка изображений 5 (1976), 68-105.
Дерево квадрантов является 2 размерными деревьями, в которых на каждом уровне узел имеет 4 детей, каждый из которых покрывает 1/4 области родительского узла.
Дерево в октябре является 3 размерными деревьями, в которых на каждом уровне узел имеет 8 детей, каждый из которых содержит 1/8-й из объема родительского узла. Вот изображение, чтобы помочь Вам визуализировать его: http://en.wikipedia.org/wiki/Octree
При выполнении размерных тестов на пересечение N Вы могли бы обобщить это к дереву N.
Перекрестные алгоритмы работают путем запуска наверху дерева и рекурсивно пересечения в любые дочерние узлы, которые пересекают протестированный объект, в какой-то момент Вы добираетесь до вершин, которые содержат фактические объекты.
Дерево октантов будет работать, пока можно указать сферы их центрами - оно иерархически, мусорные ведра указывают в кубические регионы с восемью детьми. Разработка соседей в структуре данных дерева октантов потребует, чтобы Вы сделали вычисления куба пересечения сферы (в некоторой степени легче, чем они смотрят) удаться, какие кубические регионы в дереве октантов в сфере.
Нахождение ближайших соседей означает идти, создают резервную копию дерева, пока Вы не получаете узел больше чем с одним заполненным ребенком и все окружающие включенные узлы (это гарантирует, что запрос получает все стороны).
Из памяти это - (несколько наивный) основной алгоритм для пересечения куба сферы:
i. Центр в кубе (это получает одноименную ситуацию),
ii. Любой из углов куба в радиусе r центра (углы в сфере)
iii. Для каждой поверхности куба (можно устранить некоторые поверхности путем разработки, какая сторона поверхности центр находится на) удаются (это - весь первый год векторная арифметика):
a. Нормальная из поверхности, которая переходит к центру сферы
b. Расстояние от центра сферы к пересечению нормального с плоскостью поверхности (хорда межустанавливает плоскость поверхность куба),
c. Пересечение плоскости находится в стороне куба (одно условие пересечения хорды к кубу)
iv. Вычислите размер хорды (Грех Cos^-1 отношения нормальной длины к радиусу сферы)
v. Если ближайшая точка на строке является меньше, чем расстояние хорды и точки находится между концами строки, хорда пересекает один из краев куба (хорда пересекает поверхность куба где-нибудь вдоль одного из краев).
Немного смутно помнивший, но это - что-то, что я сделал для ситуации, вовлекающей сферические регионы с помощью octee структуры данных (много лет назад). Можно также хотеть проверить KD-деревья, как некоторые из других плакатов предполагают, но начальный вопрос звучит очень похожим на то, что я сделал.