Makefile

all:
	clang++  -Wextra -Wall -std=c++11  main.cpp  -lsfml-graphics -lsfml-system -lsfml-window -o qt  -g
clean:
	rm *.o

quadtree.cpp

#include <iostream>
#include <SFML/Graphics/RenderWindow.hpp>
#include <SFML/Window/Event.hpp>
#include <SFML/Graphics/Font.hpp>
#include <SFML/Graphics/RectangleShape.hpp>
#include <SFML/Graphics/CircleShape.hpp>
#include <vector>
#include <cstdlib>

const int MAX_WIDTH = 640;
const int MAX_HEIGHT = 480;

class testdinger{
public:
  testdinger(){
    x = rand() % MAX_WIDTH;
    y = rand() % MAX_HEIGHT;
    height = 10;
    width = 10;
  };
  double x;
  double y;
  double height;
  double width;
};

enum QUADRANT {TL,TR,BL,BR,None};


class quadtree{
  //in struct point?
public:

  double x;
  double y;
  int h;
  int w;

  quadtree* tl;
  quadtree* tr;
  quadtree* bl;
  quadtree* br;

  ~quadtree(){
    //what happens if you
    //delete a nullptr;
    delete this->tl;
    delete this->tr;
    delete this->bl;
    delete this->br;
  };
  int depth;
  //private:
  std::vector<testdinger*> stuff;
 


public:
  //instantiate recursively
  quadtree(double x,double y,double w,double h,int depth,int maxdepth):
    x(x), y(y),h(h),w(w),depth(depth){
    if (depth == maxdepth){
      tl = nullptr;
      tr = nullptr;
      bl = nullptr;
      br = nullptr;
      return;
    }
    //gotta divide
    double hh = h/2.0;
    double hw = w/2.0;
    stuff = std::vector<testdinger*>();
    bl = new quadtree(x,     y     ,hw ,hh,depth+1,maxdepth);
    br = new quadtree(x + hw,y     ,hw ,hh,depth+1,maxdepth);
    tl = new quadtree(x,     y + hh,hw ,hh,depth+1,maxdepth);
    tr = new quadtree(x+hw,  y+hh  ,hw ,hh,depth+1,maxdepth);
  }

  void insert(testdinger*);  
  QUADRANT region(testdinger*);
  bool collide(testdinger*);
};



QUADRANT quadtree::region(testdinger* td){
   
  //gotta do the equal to or greater than
  //we gotta bias one way or the other with this
  if(td->x >= this->x && td->x <= (this->x + this->w) && td->y >= this->y && td->y <= (this->y + this->h)) {
    if(td->x > this->x + (this->w /2)){ 
      //right
      if(td->y >= this->y + (this->h / 2)){
	//tr
	//		std::cout << "tr"<<std::endl;
	return QUADRANT::TR;
	}else{
	//br
	//	std::cout << "br"<<std::endl;
	return QUADRANT::BR;
      }
    }else{
      //left
      if(td->y >= this->y + (this->h / 2)){
	//TLt
	//	std::cout << "tl"<<std::endl;
	return QUADRANT::TL;
      }else{
	//	std::cout << "bl"<<std::endl;
	return QUADRANT::BL;
      }
    }
  }else{
     //std::cout << "in none branch"<<std::endl;
		return QUADRANT::None;
  }
}



void quadtree::insert(testdinger* td){
  //indicates that this is the bottom layer
  if( this->tl == nullptr || this->tr == nullptr || this->bl == nullptr || this->br == nullptr){
    this->stuff.push_back(td);
    return;
  }

  
  auto quad = this->region(td);
  switch(quad){
  case QUADRANT::TL:
    //       std::cout << "in tl" << std::endl;
       this->tl->insert(td);
       break;
  case QUADRANT::TR:
    //    std::cout << "in tr" << std::endl;
    this->tr->insert(td);
    break;
  case QUADRANT::BL:
    //    std::cout << "in bl" << std::endl;
    this->bl->insert(td);
    break;
  case QUADRANT::BR:
    //    std::cout << "in br" << std::endl;
    this->br->insert(td);
    break;
  case QUADRANT::None:
       std::cout << "we got none" << std::endl;
    return;
  }
}


void traverse_tree(quadtree* qt){
  if(qt->tl == nullptr || qt->tr == nullptr || qt->br == nullptr || qt->bl == nullptr){
    return;
  }
  std::cout << "inside quadtree starting at " << qt->x << " " << qt->y << std::endl;
  std::cout << "finished" << std::endl;
  traverse_tree(qt->tl);
  traverse_tree(qt->tr);
  traverse_tree(qt->bl);
  traverse_tree(qt->br);
}


bool quadtree::collide(testdinger* td){
  if( this->tl == nullptr || this->tr == nullptr || this->bl == nullptr || this->br == nullptr){
    for(auto &v:this->stuff){
      if(v->x == td->x && v->y == td->y){
	return true;
      }
    }
    return false;
  }
  auto quad = this->region(td);  
  switch(quad){
  case QUADRANT::TL:
       return this->tl->collide(td);
  case QUADRANT::TR:
    return this->tr->collide(td);
  case QUADRANT::BL:
    return this->bl->collide(td);
  case QUADRANT::BR:
    return this->br->collide(td);
  case QUADRANT::None:
    return false;
  }
}


void draw_tree(quadtree* qt,sf::RenderTarget *rend){

  if(qt == nullptr){
    return;
  }
  
  for(auto &v:qt->stuff){
    auto circle = sf::CircleShape(5);
    circle.setPosition(v->x,v->y);
    circle.setFillColor(sf::Color::Green);
    rend->draw(circle);
  }

  auto shape = sf::RectangleShape(sf::Vector2f(qt->w, qt->h));
  //  shape.setSize(sf::Vector2f(qt->w, qt->h));
  shape.setPosition(qt->x, qt->y);
  //  shape.setFillColor(sf::Color(128, 255, 129, 0));
  shape.setFillColor(sf::Color::Transparent);
    //  shape.setFillColor(sf::Color::Red);
  shape.setOutlineThickness(1.0f);
  shape.setOutlineColor(sf::Color(0, 0, 255));
  rend->draw(shape);
    
  draw_tree(qt->tl,rend);
  draw_tree(qt->tr,rend);
  draw_tree(qt->bl,rend);
  draw_tree(qt->br,rend);

}





int main(){
  sf::RenderWindow app( sf::VideoMode( MAX_WIDTH, MAX_HEIGHT, 32 ), "Quadtree",sf::Style::None );
  app.setFramerateLimit( 20 );
  std::cout << "blood for the blood god" << std::endl;
  auto qt = new quadtree(0,0,MAX_WIDTH,MAX_HEIGHT,0,5);
  std::cout << "we allocated that dumb shit" << std::endl;
  auto cont = std::vector<testdinger*>();
  for(int i = 0;i<200;i++){
    auto td = new testdinger();
    cont.push_back(td);
  }

  for(auto &v:cont){
    qt->insert(v);
  }
  
  for(auto &v:cont){
    if(!qt->collide(v)){
      std::cout << "this should've collideded " << v->x << " " << v->y << std::endl;
    }
  }
  
  

  draw_tree(qt,&app);  
  app.display();
  std::cout << std::endl;

  app.clear(sf::Color::Black);
  while( app.isOpen() ) {
    sf::Event event;
    while( app.pollEvent( event ) ) {
      if ( event.type == sf::Event::KeyPressed ) {
	if ( event.key.code == sf::Keyboard::Escape || event.key.code == sf::Keyboard::Q ) {
	  app.close();
	}
      }
    }
           
    // clear the window with black color
    ///      app.clear(sf::Color::Black);
    
    // draw everything here...
    // window.draw(...);
    
    // end the current frame
      //    app.display();


    // auto circle = sf::CircleShape(5);
    // circle.setPosition(0,0);
    // circle.setFillColor(sf::Color::Blue);
    // app.draw(circle);
    // auto circle2 = sf::CircleShape(5);
    // circle2.setPosition(0,MAX_HEIGHT - 3);
    // circle2.setFillColor(sf::Color::Cyan);
    // app.draw(circle2);
    // auto circle3 = sf::CircleShape(5);
    // circle3.setPosition(MAX_WIDTH - 3,0);
    // circle3.setFillColor(sf::Color::Magenta);
    // app.draw(circle3);
    // auto circle4 = sf::CircleShape(5);
    // circle4.setPosition(MAX_WIDTH - 3,MAX_HEIGHT -3);
    // circle4.setFillColor(sf::Color::Yellow);
    // app.draw(circle4);

  }

  std::cout << "holy sheet" << std::endl;
  return 0;
  
}