Проблемы с перетаскиванием фигур

Question

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

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

Answer 1

Квадтрит (2D, octree if 3D) часто используется при обнаружении столкновений. Идея состоит в том, чтобы рекурсивно разделить пространство в квадратах/кубах и поместить фигуры в правильные квадраты/кубы. Когда вам нужно выполнить обнаружение столкновения на данной фигуре, вы можете затем проверить только фигуры в том же квадрате/кубе.

Существуют и другие структуры, каждая из которых имеет за/против в зависимости от ограничений, которые у вас есть. Если другие фигуры являются статичными, деревья BSP также могут быть хорошей структурой.