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

Question

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

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

Дано:

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

Вопрос:

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

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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