Блог

Общая постановка задачи:

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

Учитывая:

Произвольные выпуклые фигуры на 2D плоскости. ( скажем, повторяется std::vector < IShape * >, IShape имеет элемент getBBox())

Вопрос:

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

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

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

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

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

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

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

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

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

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