алгоритм поиска диапазона для запроса фигур в 2D-плоскости, которые находятся в заданной области

Общая постановка проблемы:

Механизм выбора формы на холсте

Данный:

Произвольные выпуклые формы на 2D-плоскости. (скажем, восстановлено с помощью std::vector ‹ IShape* >, у IShape есть член getBBox())

данный

Вопрос:

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

(в этом конкретном примере должны возвращаться формы A и B )

Я знаю эту типичную проблему поиска диапазона/запроса диапазона, однако «классические» примеры относятся к поиску точек в заданном регионе, чтобы проиллюстрировать, как можно использовать kdtree для решения проблемы.

Я не могу понять, как «расширить» алгоритм для работы с фигурами. Я больше ищу идею, чем точную реализацию.

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


algorithm data-structures kdtree range-query
person libxelar.so    schedule 02.04.2019    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Используя ограничительную рамку, вы можете очень легко проверить, находится ли фигура внутри выделения (то есть все ли четыре угла внутри).

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

person Thomash    schedule 03.04.2019
comment
для 4-5 фигур перебор всех из них в порядке. но как насчет 2 миллионов форм, если выбор включает 0,1% из них (очень узкий выбор)? - person libxelar.so; 03.04.2019
comment
Вы не перебираете их все, а только те, у которых верхний левый угол находится внутри выделения. - person Thomash; 03.04.2019

arrow_upward
1
arrow_downward

KD-дерево не идеально подходит для этого типа поиска. Как предложил @Thomash, полезно создавать AABB (ограничительные рамки, выровненные по оси) для каждой формы. Затем вы можете поместить их во что-то вроде quadtree или R-дерево. Они позволяют хранить AABB, а затем легко запрашивать все AABB, которые пересекаются с прямоугольником запроса.

Для каждого AABB, который вы получаете из запроса, вам нужно проверить, действительно ли фигура пересекается с прямоугольником запроса (пересечение с AABB, очевидно, не гарантирует пересечение с фигурой внутри AABB).

Если вы используете Java, взгляните на мои реализации различных пространственных индексов.

person TilmannZ    schedule 04.04.2019
comment
хорошо, я думаю, что у меня есть первая идея, то есть обрабатывать все фигуры по их выровненным BBox, что выполнимо. Теперь, во-вторых, храним ли мы эти bboxes как данные в дереве? - person libxelar.so; 04.04.2019
comment
да. Дерево может быть похоже на карту‹AABB, YourData›, где AABB — это «ключ», а ваши данные — это фактическая форма. - person TilmannZ; 04.04.2019
comment
Разумеется, у «Карты» есть дополнительные функции для поиска всего, что пересекается с заданным прямоугольником. - person TilmannZ; 04.04.2019