Предпосылка: предположим, у меня есть прямоугольное подмножество 2D-пространства и набор точек, все с различными x -значениями, в этом подмножестве.В интересах оптимизации алгоритма, который еще не написан, я хочу разделить свой блок на ячейки в соответствии со следующим процессом: я делю прямоугольник пополам на 2 равные части вдоль оси x.Затем я несколько раз делю пополам каждый под прямоугольник, пока в каждой ячейке не будет ни одной точки, или ни одной вообще. 
На этой иллюстрации вертикальные линии представляют «процесс деления пополам» и линииупорядочены по темноте (темнее - новее).
Сначала я определю два основных класса:
class Point{
private:
double x;
double y;
public:
// [...]
// the relevant constructor and getter
// overloaded operators +, -, * for vector calculations
};
class Box{
private:
Point bottom_left_point;
double width;
double height;
public:
Box(Point my_point, double my_x, double my_y) : // constructor
bottom_left_point(my_point), width(my_x), height(my_y){}
bool contains(const Point& p); // returns true iff the box contains p in the geometric sense
Box halve(bool b) const; // takes a boolean as input and returns the left half-rectangle for false, and the right half-rectangle for true
};
Теперь для реализации «алгоритма деления пополам» мне понадобится двоичное дерево -как структураКаждый узел будет представлять вложенную ячейку прямоугольника (с корневым узлом, представляющим общий прямоугольник).Узел может иметь двух дочерних элементов, и в этом случае дочерние элементы представляют его левую и правую половины.Узел также может иметь указатель на частицу, которая существует в ячейке.Конечная идея состоит в том, чтобы начать с пустого дерева и вставлять точки, одну за другой, используя метод insert(Point* to_be_inserted).
Так что я определю следующий рекурсивный класс, чьи атрибуты private довольноне требует пояснений:
class Node;
class Node{
private:
enum node_type{ INT, EXT, EMPTY };
node_type type;
// type == INT means that it is an interior node, i.e. has children
// type == EXT means that it is an exterior node, i.e. has no children but contains a point
// type == EMPTY means that it has no children and no point
std::array<Node*,2> children;
Box domain; // the geometric region which is being represented
Point* tenant; // address of the particle that exists in this cell (if one such exists)
public:
Node(Box my_domain) :
type(EMPTY), children({nullptr}), domain(my_domain){}
//
// to be continued...
Первым делом стоит определить метод subdivide(), который наделяет мой узел двумя дочерними элементами:
void Node::subdivide(void){
type = INT;
children[0] = new Node(domain.halve(false));
children[1] = new Node(domain.halve(true));
}
Теперь все готово для записисуть всего этого дела, метод insert.Поскольку он будет записан рекурсивно, самое простое решение - иметь логический тип возврата, который сообщает нам, была ли вставка успешной или неудачной.Имея это в виду, вот код:
bool Node::insert(Point* to_be_inserted){
if(not domain.contains(*to_be_inserted)) return false;
switch(type){
case INT:{
for(Node* child : children) if(child->insert(to_be_inserted)) return true;
return false;
}
case EXT:{
subdivide();
for(Node* child : children) if(child->insert(to_be_inserted)) break;
tenant = nullptr;
for(Node* child : children) if(child->insert(to_be_inserted)) return true;
break;
}
case EMPTY:{
type = EXT;
tenant = to_be_inserted;
return true;
}
}
throw 1; // this line should not, in, theory ever be reached
}
(Обратите внимание, что для абстракции и общности я использовал циклы for в массиве children, когда я мог просто выписатьдва случая.)
Объяснение:
Сначала мы проверяем, находится ли to_be_inserted в геометрической области, представленной this.Если нет, верните false.
Если this является внутренним узлом, мы передаем точку каждому дочернему элементу, пока он не будет успешно вставлен.
Если this является внешним узлом, это означает, что мы должны разделить узел на две части, чтобы иметь возможность правильно изолировать to_be_inserted от точки, которая в настоящее время проживает в узле.
- Сначала мы звоним
multiply(). - Затем мы пытаемся
insert текущего арендатора в одного из детей (извините, как это непристойно звучит, уверяю вас, что это непреднамеренно). - Как только это будет сделано, мы сделаем то же самое с
to_be_inserted и вернем результат.(Обратите внимание, что a priori вставка будет успешной на этом этапе из-за предварительного вызова box::contains.
Наконец, если this это EMPTY узел, нам просто нужно присвоить tenant для *to_be_inserted и изменить type на EXT, и все готово.
Хорошо, так чтодавайте попробуем это с помощью простого main:
int main(void){
Box my_box(ORIGIN, 1.0, 1.0); // rectangle of vertices (0,0),(0,1),(1,0),(1,1)
Node tree(box); // initializes an empty tree representing the region of my_box
Point p(0.1, 0.1);
Point q(0.6, 0.7);
tree.insert(&p);
tree.insert(&q);
return 0;
}
Компилируется, но при запуске исключения в нижней части insert выдается после нескольких вызовов. Как это возможно, учитывая, что внет точки Node создается без значения type?
Редактировать: Я заметил, как и эту, несколько возможных ошибок, которые могут также возникнуть при небольших изменениях вкод:
необъяснимый звонок на nullptr->insert(something)
звонок на insert по адресу 0x0000000000000018, который неуказать на инициализированный Node.
Полный код, включая makefile с соответствующими флагами отладки, можно найти в https://github.com/raphael-vock/phantom-call.