26 #include <tulip/Rectangle.h> 
   27 #include <tulip/Coord.h> 
   35 template <
class TYPE> 
class QuadTreeNode {
 
   48   QuadTreeNode(
const tlp::Rectangle<float> &box):_box(box) {
 
   49     assert(_box.isValid());
 
   51     for(
int i=0; i<4; ++i)
 
   58     for(
int i=0; i<4; ++i)
 
   59       if (children[i] != NULL) 
delete children[i];
 
   64   void insert(
const tlp::Rectangle<float> &box, 
const TYPE 
id) {
 
   65     assert(box.isValid());
 
   66     assert(_box.isValid());
 
   72     Vec2f subBox((_box[0]+_box[1])/2.f);
 
   74     if( !((subBox == _box[0]) || (subBox == _box[1]))) {
 
   75       for (
int i=0; i<4; ++i) {
 
   76         if (getChildBox(i).isInside(box)) {
 
   77           QuadTreeNode *child=getChild(i);
 
   80             child->insert(box, 
id);
 
   82             entities.push_back(
id);
 
   89     entities.push_back(
id);
 
   97   void getElements(
const tlp::Rectangle<float> &box, std::vector<TYPE> &result)
 const {
 
   98     assert(box.isValid());
 
   99     assert(_box.isValid());
 
  101     if (_box.intersect(box)) {
 
  102       for (
size_t i=0; i<entities.size(); ++i) {
 
  103         result.push_back(entities[i]);
 
  106       for (
unsigned int i=0; i<4; ++i) {
 
  107         if (children[i]!=NULL)
 
  108           children[i]->getElements(box, result);
 
  116   void getElements(std::vector<TYPE> &result)
 const {
 
  117     for (
size_t i=0; i<entities.size(); ++i) {
 
  118       result.push_back(entities[i]);
 
  121     for (
unsigned int i=0; i<4; ++i) {
 
  122       if (children[i]!=NULL)
 
  123         children[i]->getElements(result);
 
  136   void getElementsWithRatio(
const tlp::Rectangle<float> &box, std::vector<TYPE> &result, 
float ratio = 1000.)
 const {
 
  137     assert(_box.isValid());
 
  138     assert(box.isValid());
 
  140     if (_box.intersect(box)) {
 
  141       float xRatio = (box[1][0] - box[0][0]) / (_box[1][0] - _box[0][0]) ;
 
  142       float yRatio = (box[1][1] - box[0][1]) / (_box[1][1] - _box[0][1]);
 
  145       if (xRatio < ratio || yRatio < ratio) {
 
  146         for (
size_t i=0; i<entities.size(); ++i) {
 
  147           result.push_back(entities[i]);
 
  150         for (
unsigned int i=0; i<4; ++i) {
 
  151           if (children[i]!=NULL)
 
  152             children[i]->getElementsWithRatio(box, result, ratio);
 
  159         if (entities.size() > 0) {
 
  160           result.push_back(entities[0]);
 
  165           for (
unsigned int i=0; i<4; ++i) {
 
  166             if (children[i]!=NULL && children[i]->_box.intersect(box)) {
 
  169               children[i]->getElementsWithRatio(box, result, ratio);
 
  180   QuadTreeNode* getChild(
int i) {
 
  181     if (children[i] == 0) {
 
  182       Rectangle<float> box (getChildBox(i));
 
  184       if(box[0] ==_box[0] && box[1]==_box[1])
 
  187       children[i] = 
new QuadTreeNode<TYPE>(box);
 
  193   Rectangle<float> getChildBox(
int i) {
 
  194     assert(_box.isValid());
 
  206     I[0] = (_box[0][0] + _box[1][0]) / 2.;
 
  210     E[1] = (_box[0][1] + _box[1][1]) / 2.;
 
  223       return Rectangle<float>(_box[0], F);
 
  227       return Rectangle<float>(I, G);
 
  231       return Rectangle<float>(F, _box[1]);
 
  235       return Rectangle<float>(E, H);
 
  238       tlp::error() << 
"ERROR" << __PRETTY_FUNCTION__  << std::endl;
 
  243   QuadTreeNode *children[4];
 
  244   std::vector<TYPE> entities;
 
  245   tlp::Rectangle<float> _box;