Я создаю квадри с помощью C ++ / SFML. и у меня проблемы с поиском неисправностей в моей программе. Я пытался в течение нескольких недель, однако я действительно не могу найти ошибку, и у меня действительно нет друзей, которые знают C ++.
После вставки точек в квадродерево, это не делит правильно. Другая дополнительная проблема заключается в том, что моя программа работает только в режиме выпуска, а не в режиме отладки.
Boundary.h:
Boundary.h представляет AABB для каждого квадрант в пределах квадродерева. Я унаследовал от sf :: RectangleShape только для визуализации. Я также унаследовал от sf :: FloatRect, поэтому я могу использовать функциональность bool sf :: FloatRect :: contains (), которая возвращает bool относительно того, находится ли точка (sf :: Vector2f) внутри прямоугольника.
#ifndef BOUNDARY_H
#define BOUNDARY_H
#include <SFML/Graphics.hpp>
struct Boundary : sf::RectangleShape, private sf::FloatRect
{
Boundary(const sf::Vector2f& centre, const sf::Vector2f& halfsize);
sf::Vector2f centre;
sf::Vector2f halfsize;
using sf::FloatRect::contains;
};
#endif
Граница. cpp:
Конструктор sf :: FloatRect :: FloatRect () принимает верхний левый угол прямоугольника и его полный размер. В моем квадрите, однако, легче думать о границах, основанных на их центрах и половинных размерах, поэтому sf::FloatRect(centre - halfsize, halfsize + halfsize)
#include "Boundary.h"
Boundary::Boundary(const sf::Vector2f& centre, const sf::Vector2f& halfsize)
:sf::FloatRect(centre - halfsize, halfsize + halfsize), centre(centre), halfsize(halfsize)
{
this->setFillColor(sf::Color::Transparent);
this->setOutlineColor(sf::Color::White);
this->setOutlineThickness(1);
this->setPosition(centre);
this->setOrigin(halfsize);
this->setSize(halfsize + halfsize);
}
Quadrant.h
Это представляет квадрант в дереве квадрантов.
#ifndef QUADRANT_H
#define QUADRANT_H
#include "Point.h"
#include "Boundary.h"
#include <iostream>
struct Quadrant : Boundary
{
int firstChildindex; //stores the index of its first child. since the children are contiguous in the base array, you can find them by firstchild + i while 0<=i<4
Point* firstpointnode = nullptr; //stores the beginning of a point list which are all in this current quadrant.
int count = 0; //-1 if the quadrant is a branch / subdivided
Quadrant(const Boundary& AABB);
void subdivide(std::vector<Quadrant>& m_quadrantStorage); //splits the quadrant into four children.
bool insert(Point* pointnode, std::vector<Quadrant>& m_quadrantStorage);
};
#endif
квадрант. cpp:
#include "Quadrant.h"
#include "Globals.h"
#include <iostream>
Quadrant::Quadrant(const Boundary& AABB)
:Boundary(AABB)
{
}
bool Quadrant::insert(Point* pointnode, std::vector<Quadrant>& m_quadrantStorage)
{
if (!this->contains(pointnode->position)) return false; //if the point isnt within this boundary, forget about it.
else if (count < QCAPACITY && count!= -1) //otherwise if it is contained, and it isnt full and isnt a branch, we can insert to the end of the point list.
{
if (firstpointnode == nullptr) {
firstpointnode = pointnode;
firstpointnode->next = nullptr;
}
else {
Point* currentpointnode = firstpointnode;
while (currentpointnode->next != nullptr) //traversing to the end of this quadrant point list
{
currentpointnode = currentpointnode->next;
}
currentpointnode->next = pointnode; // currentpointnode is the last node in the list by this point.
currentpointnode->next->next = nullptr; //disassociating any ties that the point had with any other points, so it is the absolute end of the list.
}
count++;
return true;
}
else if (count != -1) //or if the point is within the quadrant, is full, and it hasnt already subdivided, subdivide.
{
subdivide(m_quadrantStorage);
for (int i = 0; i < 4; i++)
{
if (m_quadrantStorage[firstChildindex + i].insert(pointnode, m_quadrantStorage)) return true;
}
}
return false;
}
void Quadrant::subdivide(std::vector<Quadrant>& m_quadrantStorage)
{
sf::Vector2f newhalfsize = halfsize / float(2);
firstChildindex = m_quadrantStorage.size();//children are contiguous in memory - nth child = firstChildindex + n for 0<=n<4
m_quadrantStorage.emplace_back(Boundary{ sf::Vector2f { centre.x + newhalfsize.x, centre.y - newhalfsize.y }, newhalfsize });
m_quadrantStorage.emplace_back(Boundary{ sf::Vector2f { centre.x + newhalfsize.x, centre.y + newhalfsize.y }, newhalfsize });
m_quadrantStorage.emplace_back(Boundary{ sf::Vector2f { centre.x - newhalfsize.x, centre.y + newhalfsize.y }, newhalfsize });
m_quadrantStorage.emplace_back(Boundary{ sf::Vector2f { centre.x - newhalfsize.x, centre.y - newhalfsize.y }, newhalfsize });
Point* currentpointnode = firstpointnode;
while (currentpointnode->next != nullptr) //transferring all points from parent list to children.
{
Point* nextpointnode = currentpointnode->next;
for (int i = 0; i < 4; i++)
{
m_quadrantStorage[firstChildindex + i].insert(currentpointnode, m_quadrantStorage);
}
currentpointnode->next = nullptr;
currentpointnode = nextpointnode;
nextpointnode = currentpointnode->next;
}
firstpointnode = nullptr; // this parent does not have a point anymore, so it is nullptr.
count = -1; //this parent is no longer a leaf, it is a branch, so the count is now -1.
}
Quadtree.h
Это обрабатывает все активные квадранты и может рассматриваться как двигатель.
#ifndef QUADTREE_H
#define QUADTREE_H
#include "Quadrant.h"
#include "Point.h"
#include <vector>
#include <random>
class Quadtree
{
public:
Quadtree(sf::RenderWindow* winptr);
void display() const;
void debug();
bool insert(Point* point);
Point* constructPoint(const sf::Vector2f& pos);
static sf::Vector2f randomPoint();
private:
sf::RenderWindow* m_winPtr = nullptr;
std::vector<Quadrant> m_quadrantStorage;
std::vector<Point*> m_pointStorage;
sf::VertexArray verticies;
std::vector<int> findleaves(const Boundary& rect);
static std::mt19937 m_randomEngine;
static std::uniform_real_distribution<float> m_uniform;
};
#endif
Quadtree. cpp
#include "Quadtree.h"
#include "Globals.h"
#include <iostream>
#include <algorithm>
#include <chrono>
Quadtree::Quadtree(sf::RenderWindow* winptr)
:m_winPtr(winptr)
{
m_quadrantStorage.emplace_back(Boundary{ sf::Vector2f{0.0f,0.0f}, sf::Vector2f{WIDTH / 2,HEIGHT / 2} });
}
void Quadtree::display() const
{
for (const auto& q : m_quadrantStorage)
{
m_winPtr->draw(q);
}
m_winPtr->draw(verticies);
}
std::vector<int> Quadtree::findleaves(const Boundary& rect) //I AM NOT USING THIS FUNCTION FOR NOW!!
{
std::vector<int> leaves, to_process;
to_process.push_back(0);
while (to_process.size() > 0)
{
int index = to_process.back();
auto node = m_quadrantStorage.begin() + index;
to_process.pop_back();
if (node->count != -1)
{
leaves.push_back(index);
}
else
{
for (int i = 0; i < 4; i++)
{
to_process.push_back(node->firstChildindex + i);
}
}
}
return leaves;
}
bool Quadtree::insert(Point* point)
{
m_quadrantStorage[0].insert(point, m_quadrantStorage);
return true;
}
void Quadtree::debug()
{
//Quadrant& root = m_quadrantStorage[0];
//root.subdivide(m_quadrantStorage);
//m_quadrantStorage[root.firstChildindex].subdivide(m_quadrantStorage);
}
Point* Quadtree::constructPoint(const sf::Vector2f& pos)
{
Point* newPoint = new Point(pos);
m_pointStorage.push_back(newPoint);
verticies.append(*newPoint);
insert(newPoint);
return newPoint;
}
std::mt19937 Quadtree::m_randomEngine(std::chrono::steady_clock::now().time_since_epoch().count());
std::uniform_real_distribution<float> Quadtree::m_uniform{ -WIDTH/2,WIDTH/2 };
sf::Vector2f Quadtree::randomPoint()
{
return { m_uniform(m_randomEngine), m_uniform(m_randomEngine) };
}
Point.h Представляет узел как часть односвязного списка, содержащего указатель на следующий узел и значение его элемента (его положение).
#ifndef POINT_H
#define POINT_H
#include <SFML/Graphics.hpp>
struct Point : sf::Vertex
{
Point(const sf::Vector2f& pos);
Point* next = nullptr;
};
#endif
Точка. cpp
#include "Point.h"
Point::Point(const sf::Vector2f& pos)
:sf::Vertex(pos)
{
}
Источник. cpp
Содержит int main ()
#include "Globals.h"
#include <iostream>
#include "Quadtree.h"
#include <algorithm>
int main()
{
sf::RenderWindow window(sf::VideoMode(WIDTH, HEIGHT), "Quadtree Spatialisation", sf::Style::Default);
sf::Vector2f mousepos;
sf::View screen{ sf::Vector2f{0,0}, sf::Vector2f{WIDTH,HEIGHT} };
window.setView(screen);
sf::VertexArray arr;
Quadtree QT(&window);
while (window.isOpen())
{
sf::Event evnt;
while (window.pollEvent(evnt))
{
switch (evnt.type)
{
case sf::Event::EventType::Closed:
{
window.close();
}
case::sf::Event::EventType::MouseMoved:
{
mousepos = static_cast<sf::Vector2f>(sf::Mouse::getPosition(window));
mousepos = window.mapPixelToCoords(static_cast<sf::Vector2i>(mousepos));
}
case::sf::Event::EventType::KeyPressed:
{
if (sf::Keyboard::isKeyPressed(sf::Keyboard::Key::W))
{
screen.zoom(0.99);
window.setView(screen);
}
else if (sf::Keyboard::isKeyPressed(sf::Keyboard::Key::S))
{
screen.zoom(1.01);
window.setView(screen);
}
else if (sf::Keyboard::isKeyPressed(sf::Keyboard::Key::Space))
{
QT.constructPoint(QT.randomPoint());
}
}
case sf::Event::EventType::MouseButtonPressed:
{
if (sf::Mouse::isButtonPressed(sf::Mouse::Left))
{
QT.constructPoint(mousepos);
}
}
}
}
window.clear();
QT.display();
window.draw(arr);
window.display();
}
}