Какова адекватная структура данных для управления геометрическими подразделениями квадрата?

Question

Я ищу структуру данных, которая может управлять данными объекта прямоугольника (O LxH), а также всех подразделений (внутренних разделов) объекта прямоугольника.

Необходимо иметь возможность добавлять больше разделов, а также получать доступ к существующим разделам. Каждый раздел должен рассматриваться как другой объект прямоугольника (O LxH).

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

Пример на рисунке

раздел 'B' должен быть другим объектом с началом, длиной и высотой.

Answer 1

Базовая реализация

struct Node
{
  vector<Node*> vChildNodes;
  double x0,y0,x1,y1;
};

... и обычно вам нужно добавить рекурсивные методы split () и locate ().

То, что вы пытаетесь реализовать, похоже на Quadtree - см. http://en.wikipedia.org/wiki/Quadtree или kd-дерево, http://en.wikipedia.org/wiki/K-d_tree. Вы можете попробовать существующие реализации.

Answer 2

Я бы сказал, вам определенно нужно какое-то дерево.

Вы упоминаете, что беспокоитесь о том, что дерево BSP может быть слишком сложным для этой проблемы - это зависит от того, насколько надежным вам должно быть решение. Вы также можете подумать, можно ли разбить объекты на более чем две части - если нет, то вы можете использовать двоичное дерево.

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

Доступ к разделам может быть выполнен путем присвоения каждому узлу относительного идентификатора относительно его родителя. Первый дочерний элемент получает relativeID = 0, второй дочерний элемент 1 и т. Д. Повторите это для дочерних элементов каждого узла на каждом уровне. Затем вы можете написать метод, который принимает список относительных идентификаторов и использует его для обхода дерева и поиска правильного раздела (каждый уровень удаляет один относительный идентификатор для перехода на следующий уровень).