quadtree.h

/*
 * This file is part of Copiste.
 *
 * Copiste is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 *  Copiste is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with Copiste.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef INCLUDED_QUADTREEH
#define INCLUDED_QUADTREEH

#include "algo/corpus.h"

#include <list>

class QuadNode
{
    public:
        QuadNode(int e = -1);
        QuadNode(QuadNode* a, QuadNode* b, QuadNode *c, QuadNode *d);

        ~QuadNode();

        bool isLeaf();

        int elem;
        QuadNode* hl;
        QuadNode* hr;
        QuadNode* ll;
        QuadNode* lr;
};

class QuadTree
{
    public:
        QuadTree();

        ~QuadTree();

        struct rect
        {
            double x;
            double y;
            double w;
            double h;
        };
        typedef struct rect rect;

        void create(Corpus *c, rect view);

        int nearest(double x, double y);


    private:
        std::list<int> separate(std::list<int> l, QuadTree::rect view);

        QuadNode* createNode(std::list<int> points, QuadTree::rect view);

        bool isInRect(double x, double y, rect r);

        int nodeSearch(QuadNode *node, rect view, double x, double y);

        QuadNode* mRoot;

        Corpus* mCorpus;

        rect mViewport;
};

#endif