下面是四叉樹的腳本...我對指標的概念比較陌生，所以我的猜測是我對雙指標或類似的東西做錯了！
#include "BoidQuadTree.h"
#include <iostream>
Quad::Quad(float boundary_TL_x, float boundary_TL_y, float boundary_BR_x, float boundary_BR_y, unsigned short max_Nodes, unsigned short max_Depth)
{
this->max_Depth = new unsigned short(max_Depth);
this->max_Nodes = new unsigned short(max_Nodes);
this->nodes_Remaining = new unsigned short(max_Nodes);
this->boundary_TL = new Vector(boundary_TL_x, boundary_TL_y);
this->boundary_BR = new Vector(boundary_BR_x, boundary_BR_y);
this->TL = nullptr; // no need to allocate memory yet
this->TR = nullptr;
this->BL = nullptr;
this->BR = nullptr;
this->boids = new Boid*[max_Nodes]; // Intitialise all pointers to nullptr
}
Quad::~Quad()
{
if (this->TL == nullptr) { // only deleted if not branched
delete this->max_Depth;
delete this->max_Nodes;
delete[] this->boids;
}
delete this->boundary_TL; // always deleted
delete this->boundary_BR;
delete this->TL;
delete this->TR;
delete this->BL;
delete this->BR;
delete this->nodes_Remaining;
}
bool Quad::Insert(Boid* boid)
{
if (boid != nullptr) {
if (this->InBoundary(boid->position)) {
if (this->TL == nullptr) {
if ((*this->nodes_Remaining) > 0) { // if there is a free position
this->boids[(*(this->max_Nodes)) - (*(this->nodes_Remaining))] = boid;
(*(this->nodes_Remaining)) -= 1;
std::cout << "inserted" << std::endl;
return true; // successfully inserted boid pointer
}
else { // no free positions in current quad...
if (*this->max_Depth > 1) { // Further depth still avaliable, therefore branch all boid pointers into new quads! (can delete boid data from this after branching to free space)
this->TL = new Quad(this->boundary_TL->x, this->boundary_TL->y, this->boundary_TL->x (this->boundary_BR->x / 2), this->boundary_TL->y (this->boundary_BR->y / 2), *(this->max_Nodes), *(this->max_Depth) - 1);
this->TR = new Quad(this->boundary_TL->x (this->boundary_BR->x / 2), this->boundary_TL->y, this->boundary_BR->x, this->boundary_TL->y (this->boundary_BR->y / 2), *(this->max_Nodes), *(this->max_Depth) - 1);
this->BL = new Quad(this->boundary_TL->x, this->boundary_TL->y (this->boundary_BR->y / 2), this->boundary_TL->x (this->boundary_BR->x / 2), this->boundary_BR->y, *(this->max_Nodes), *(this->max_Depth) - 1);
this->BR = new Quad(this->boundary_TL->x (this->boundary_BR->x / 2), this->boundary_TL->y (this->boundary_BR->y / 2), this->boundary_BR->x, this->boundary_BR->y, *(this->max_Nodes), *(this->max_Depth) - 1);
std::cout << "Branched!" << std::endl;
for (unsigned short i = 0; i < *(this->max_Nodes); i ) {
this->PushToBranch(this->boids[i]);
}
this->PushToBranch(boid);
delete[] this->boids; // Delete now unneeded data
delete this->max_Nodes;
delete this->max_Depth;
return true;
}
else {
std::cout << "FUNC LOCATION : Quad::Insert() ERROR! Not enough depth to insert boid pointer! Returning false." << std::endl;
std::cout << boid->position->x << " " << boid->position->y << std::endl;
return false;
}
}
}
else { // this quad has branched
this->PushToBranch(boid);
std::cout << "inserted into branch" << std::endl;
}
}
else {
std::cout << "FUNC LOCATION : Quad::Insert() ERROR! Boid not inside the valid range of the quadtree! Returning false." << std::endl;
return false;
}
}
else {
std::cout << "FUNC LOCATION : Quad::Insert() ERROR! Attempted to insert a nullptr! Returning false." << std::endl;
return false;
}
}
void Quad::Insert(Boid** boids_Array, unsigned int number_Of_Boids)
{
for (unsigned int i = 0; i < number_Of_Boids; i ) {
this->Insert(boids_Array[i]);
}
}
bool Quad::InBoundary(Vector* position)
{
if (position->x >= this->boundary_TL->x && position->x <= this->boundary_BR->x && position->y >= this->boundary_TL->y && position->y <= this->boundary_BR->y) {
return true;
}
else {
return false;
}
}
void Quad::PushToBranch(Boid* boid) // determines where to insert() boid (to be used on boids that are already checked to be in radius!), and
{
if (boid->position->x <= this->boundary_TL->x (this->boundary_BR->x / 2)) {
if (boid->position->y <= this->boundary_TL->y (this->boundary_BR->y / 2)) { // TL
this->TL->Insert(boid);
}
else { // BL
this->BL->Insert(boid);
}
}
else {
if (boid->position->y <= this->boundary_TL->y (this->boundary_BR->y / 2)) { // TR
this->TR->Insert(boid);
}
else { // BR
this->BR->Insert(boid);
}
}
}
主要問題是它適用于非常少量的 boid，但如果我 Insert() 甚至 10（具有完全在樹范圍內的不同隨機位置）到 max_Depth 為 100 和 max_Nodes 的四叉樹值為 1 或 2，我最終會得到數百個分支和大約 20 個深度錯誤，這沒有任何意義？任何幫助將非常感激！我正在失去理智;-;
uj5u.com熱心網友回復：
我錯誤地計算了分支的邊界！感謝所有的幫助和反饋:)
更新計算
this->TL = new Quad(this->boundary_TL->x, this->boundary_TL->y, (this->boundary_TL->x this->boundary_BR->x) / 2, (this->boundary_TL->y this->boundary_BR->y) / 2, *(this->max_Nodes), *(this->max_Depth) - 1);
this->TR = new Quad((this->boundary_TL->x this->boundary_BR->x) / 2, this->boundary_TL->y, this->boundary_BR->x, (this->boundary_TL->y this->boundary_BR->y) / 2, *(this->max_Nodes), *(this->max_Depth) - 1);
this->BL = new Quad(this->boundary_TL->x, (this->boundary_TL->y this->boundary_BR->y) / 2, (this->boundary_TL->x this->boundary_BR->x) / 2, this->boundary_BR->y, *(this->max_Nodes), *(this->max_Depth) - 1);
this->BR = new Quad((this->boundary_TL->x this->boundary_BR->x) / 2, (this->boundary_TL->y this->boundary_BR->y) / 2, this->boundary_BR->x, this->boundary_BR->y, *(this->max_Nodes), *(this->max_Depth) - 1);
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/522665.html
標籤：C 排序指针模拟四叉树