사용자 도구

사이트 도구


kb:rtree

차이

문서의 선택한 두 판 사이의 차이를 보여줍니다.

차이 보기로 링크

kb:rtree [2014/11/09 20:02] (현재)
줄 1: 줄 1:
 +====== R-TREE ======
 +R-TREES: A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING
 +
 +N 차원의 공간에서 N 차원의 사각형(엄밀히 말하자면 2차원에서나 사각형이지만,​ 딱히 따로 부르기 귀찮다.)을 빠르게 찾기 위한 자료 구조다. 이 자료구조를 이용하면 아래와 같은 쿼리를 효과적으로 처리할 수 있다.
 +
 +  * 어떤 점에 가장 가까운 사각형은 어느 것인가?
 +  * 어떤 점을 포함하는 사각형은 어느 어느 것인가?
 +  * 어떤 사각형과 겹치는 사각형은 어느 어느 것인가?
 +  * 어떤 사각형을 포함하는 사각형은 어느 어느 것인가?
 +
 +노드의 삽입/​삭제에는 그리 효과적인 자료구조가 아니므로,​ 동적인 자료 구조를 처리하는 데에는 맞지 않다. 게임에서는 정적인 맵 정보를 구성하는 데 사용할 수 있을 듯 하다.
 +
 +
 +====== C++ Implementation ======
 +http://​www.superliminal.com/​sources/​sources.htm 에서 다운로드받아 약간의 수정을 가한 C++ 소스이다.
 +
 +<file cpp RTree.h>
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \file RTree.h
 +/// \author ​
 +/// 1983 Original algorithm and test code by Antonin Guttman and 
 +///      Michael Stonebraker,​ UC Berkely
 +/// 1994 ANCI C ported from original test code by Melinda Green - 
 +///      melinda@superliminal.com
 +/// 1995 Sphere volume fix for degeneracy problem submitted by Paul Brook
 +/// 2004 Templated C++ port by Greg Douglas
 +/// \date 2004.9.2
 +/// \note http://​www.superliminal.com/​sources/​sources.htm 에서 다운로드받아
 +/// 약간의 수정을 가한 소스이다.
 +//////////////////////////////////////////////////////////////////////////////​
 +
 +#ifndef __RTREE_H__
 +#define __RTREE_H__
 +
 +#include <​math.h>​
 +
 +// 현재 버전은 메모리 풀을 사용하지 않는다. 메모리풀을 사용하기 위해서는
 +// 이 매크로가 선언되어 있는 부분을 찾아서 수정해야 한다.
 +#define RTREE_DONT_USE_MEMPOOLS ​
 +
 +// 노드의 분할을 위해서 '​구'​ 형식의 부피를 사용한다. ​
 +// 노드를 좀 더 잘 분할할 수 있으나, 속도가 약간 느릴 수 있다.
 +#define RTREE_USE_SPHERICAL_VOLUME ​
 +
 +// 파일 IO 헬퍼 클래스
 +class RTFileStream; ​
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \class RTree
 +/// \brief N 차원의 바운딩 박스 트리.
 +///
 +/// DATATYPE ​    ​유저 데이터 형식. int, void*, obj* 같은 형식만 사용 가능.
 +///              즉 int 보다 사이즈가 큰 타입은 사용할 수 없다.
 +/// ELEMTYPE ​    ​좌표계를 나타내는 데 사용할 타입. int, float 등등
 +/// NUMDIMS ​     차원의 수. 2, 3 등등
 +/// ELEMTYPEREAL 내부적으로 부피 등을 계산하는 데 쓰일 타입. 정수형보다는
 +///              실수형의 타입을 사용해야 한다.
 +/// TMAXNODES ​   한 노드에 들어갈 수 있는 자식 노드의 최대 갯수
 +/// TMINNODES ​   한 노드에 들어가야하는 자식 노드의 최소 갯수
 +///
 +/// 3차원의 트리를 구성하기 위해서는 RTree<​Object*,​ float, 3>과 같은 형식으로
 +/// 사용하면 된다.
 +///
 +/// \note 유저 데이터를 집어넣고 삭제하기 위해서는 그 데이터를 감싸는 최소의
 +/// 바운딩 박스(Minimal Bounding Box)를 알아야 한다. ​
 +/// \note 현재 버전은 노드의 할당/​삭제를 위해 그냥 new/​delete를 사용한다.
 +/// 효율을 위해서는 메모리 풀을 이용하는 것이 좋을 것이다.
 +//////////////////////////////////////////////////////////////////////////////​
 +
 +template <​typename DATATYPE, typename ELEMTYPE, int NUMDIMS, ​
 +    typename ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
 +class RTree
 +{
 +protected: ​
 +    struct Node;
 +
 +
 +public:
 +    enum
 +    {
 +        MAXNODES = TMAXNODES, ///< 한 노드에 들어갈 수 있는 자식 노드의 최대 갯수
 +        MINNODES = TMINNODES ​ ///< 한 노드에 들어가야하는 자식 노드의 최소 갯수
 +    };
 +
 +    // 결과값을 반환하기 위한 벡터
 +    typedef std::​vector<​DATATYPE>​ RESULTS;
 +
 +
 +private:
 +    Node*        m_root; ​            ///<​ 루트 노드
 +    ELEMTYPEREAL m_unitSphereVolume;​ ///< 부피를 계산하기 위한 상수
 +
 +
 +public:
 +    RTree();
 +    virtual ~RTree();
 +
 +
 +public:
 +    /// \brief 데이터를 집어넣는다.
 +    /// \param min 바운딩 박스의 최소값
 +    /// \param max 바운딩 박스의 최대값
 +    /// \param dataId 실제 데이터의 ID. 양수여야 한다. 0은 되나 음수값은
 +    /// 사용할 수 없다.
 +    void Insert(const ELEMTYPE min[NUMDIMS],​ const ELEMTYPE max[NUMDIMS],​ const DATATYPE&​ dataId);
 +
 +    /// \brief 데이터를 제거한다.
 +    /// \param min 바운딩 박스의 최소값
 +    /// \param max 바운딩 박스의 최대값
 +    /// \param dataId 실제 데이터의 ID. 양수여야 한다. 0은 되나 음수값은
 +    /// 사용할 수 없다.
 +    void Remove(const ELEMTYPE min[NUMDIMS],​ const ELEMTYPE max[NUMDIMS],​ const DATATYPE&​ dataId);
 +
 +    /// \brief 해당하는 바운딩 박스와 겹치는 모든 데이터들을 찾는다.
 +    /// \param min 바운딩 박스의 최소값
 +    /// \param max 바운딩 박스의 최대값
 +    /// \param results 결과값을 집어넣을 컬렉션 객체
 +    /// \return 찾은 데이터의 갯수
 +    int Search(const ELEMTYPE min[NUMDIMS],​ const ELEMTYPE max[NUMDIMS],​ RESULTS&​ results);
 +
 +    /// \brief 모든 데이터를 제거하고,​ 루트 노드를 초기화한다.
 +    void RemoveAll();​
 +
 +    /// \brief 트리 안에 있는 데이터의 갯수를 반환한다.
 +    ///
 +    /// 내부적으로 데이터의 갯수를 유지하지 않고, 이 함수가 호출될 때마다 ​
 +    /// 계산하기 때문에 느리다. 자주 호출하지 말 것.
 +    ///
 +    /// \return int 트리 안에 있는 데이터의 갯수
 +    int Count();
 +
 +
 +public:
 +    /// \brief 파일에서 트리를 로드한다.
 +    /// \param fileName 파일 이름
 +    /// \return bool 정상적으로 로드한 경우에는 true를 반환하고,​ 뭔가 에러가
 +    /// 생긴 경우에는 false를 반환한다.
 +    bool Load(const char* fileName);
 +
 +    /// \brief 스트림에서 트리를 로드한다.
 +    /// \param stream 스트림 객체
 +    /// \return bool 정상적으로 로드한 경우에는 true를 반환하고,​ 뭔가 에러가
 +    /// 생긴 경우에는 false를 반환한다.
 +    bool Load(RTFileStream&​ stream);
 +
 +    /// \brief 파일에다 트리를 저장한다.
 +    /// \param fileName 파일 이름
 +    /// \return bool 정상적으로 저장한 경우에는 true를 반환한고,​ 뭔가 에러가
 +    /// 생긴 경우에는 false를 반환한다.
 +    bool Save(const char* fileName);
 +
 +    /// \brief 스트림에다 트리를 저장한다.
 +    /// \param stream 스트림 객체
 +    /// \return bool 정상적으로 저장한 경우에는 true를 반환한고,​ 뭔가 에러가
 +    /// 생긴 경우에는 false를 반환한다.
 +    bool Save(RTFileStream&​ stream);
 +
 +
 +public:
 +    //////////////////////////////////////////////////////////////////////////​
 +    /// \class Iterator
 +    /// \brief ​
 +    //////////////////////////////////////////////////////////////////////////​
 +    class Iterator
 +    {
 +    friend RTree;
 +
 +    private:
 +        // Max stack size. Allows almost n^32 where n is number of branches in node
 +        enum { MAX_STACK = 32 }; 
 +
 +        struct StackElement
 +        {
 +            Node* m_node;
 +            int m_branchIndex;​
 +        };
 +
 +        StackElement m_stack[MAX_STACK];​ ///< 재귀호출을 피하기 위한 스택
 +        int          m_tos; ​             ///< 스택 탑
 +
 +    public:
 +        /// \brief 생성자
 +        Iterator() { Init(); }
 +
 +        /// \brief 소멸자
 +        ~Iterator() { }
 +
 +
 +    public:
 +        /// \brief 올바른 값을 가지고 있는가의 여부를 반환한다.
 +        /// \return bool 무효화된 횡단자일 경우 true
 +        bool IsNull() const { return m_tos <= 0; }
 +
 +        /// \brief 올바른 값을 가지고 있는가의 여부를 반환한다.
 +        /// \return bool 유효한 횡단자일 경우 true
 +        bool IsNotNull() { return m_tos > 0; }
 +
 +        /// \brief 현재 횡단자의 데이터 값을 반환한다. 호출하기 이전에
 +        /// 횡단자의 값이 정상적인지를 먼저 체크해야 한다.
 +        /// \return DATATYPE&​ 데이터 값
 +        DATATYPE&​ operator*()
 +        {
 +            Assert(IsNotNull());​
 +            StackElement&​ curTos = m_stack[m_tos - 1];
 +            return curTos.m_node->​m_branch[curTos.m_branchIndex].m_data;​
 +        } 
 +
 +        /// \brief 현재 횡단자의 데이터 값을 반환한다. 호출하기 이전에
 +        /// 횡단자의 값이 정상적인지를 먼저 체크해야 한다.
 +        /// \return const DATATYPE&​ 데이터 값
 +        const DATATYPE&​ operator*() const
 +        {
 +            Assert(IsNotNull());​
 +            StackElement&​ curTos = m_stack[m_tos - 1];
 +            return curTos.m_node->​m_branch[curTos.m_branchIndex].m_data;​
 +        } 
 +
 +        /// \brief 다음 데이터 값을 반환한다.
 +        /// \return bool 다음 데이터값이 존재하는 경우 true, 더 이상의 ​
 +        /// 데이터가 존재하지 않는다면 false.
 +        bool operator++() { return FindNextData();​ }
 +
 +
 +    private:
 +        /// \brief 횡단자를 초기화한다.
 +        void Init() { m_tos = 0; }
 +
 +        /// \brief 트리 안에 잇는 다음 데이터를 찾는다. (내부에서만 사용하는
 +        /// 함수다.)
 +        /// \return bool 다음 데이터값이 존재하는 경우 true, 더 이상의 ​
 +        /// 데이터가 존재하지 않는다면 false.
 +        bool FindNextData()
 +        {
 +            for (;;)
 +            {
 +                if (m_tos <= 0)
 +                    return false;
 +
 +                StackElement curTos = Pop(); // 스택 탑을 복사해둔다.
 +
 +                if (curTos.m_node->​IsLeaf())
 +                {
 +                    // Keep walking through data while we can
 +                    if (curTos.m_branchIndex+1 < curTos.m_node->​m_count)
 +                    {
 +                        // There is more data, just point to the next one
 +                        Push(curTos.m_node,​ curTos.m_branchIndex + 1);
 +                        return true;
 +                    }
 +                    // No more data, so it will fall back to previous level
 +                }
 +                else
 +                {
 +                    if (curTos.m_branchIndex+1 < curTos.m_node->​m_count)
 +                    {
 +                        // Push sibling on for future tree walk
 +                        // This is the 'fall back' node when we finish with 
 +                        // the current level
 +                        Push(curTos.m_node,​ curTos.m_branchIndex + 1);
 +                    }
 +
 +                    // Since cur node is not a leaf,
 +                    // push first of next level to get deeper into the tree
 +                    Node* nextLevelnode = curTos.m_node->​m_branch[curTos.m_branchIndex].m_child;​
 +                    Push(nextLevelnode,​ 0);
 +
 +                    // If we pushed on a new leaf, exit as the data is ready at TOS
 +                    if (nextLevelnode->​IsLeaf())
 +                        return true;
 +                }
 +            }
 +        }
 +
 +        /// \brief 노드와 브랜치를 스택에다 푸쉬한다. (내부적으로만 사용한다.)
 +        /// \param node 노드
 +        /// \param branchIndex 브랜치 인덱스
 +        void Push(Node* node, int branchIndex)
 +        {
 +            m_stack[m_tos].m_node = node;
 +            m_stack[m_tos].m_branchIndex = branchIndex;​
 +            ++m_tos;
 +            Assert(m_tos <= MAX_STACK);
 +        }
 +
 +        /// \brief 스택에서 데이터를 꺼낸다. (내부적으로만 사용한다.)
 +        /// \return StackElement&​ 스택 데이터
 +        StackElement&​ Pop()
 +        {
 +            Assert(m_tos > 0);
 +            --m_tos;
 +            return m_stack[m_tos];​
 +        }
 +    };
 +
 +    /// \brief 제일 앞쪽의 횡단자를 리턴한다.
 +    /// \param it 횡단자의 참조
 +    void GetFirst(Iterator&​ it)
 +    {
 +        it.Init();
 +        if (m_root && (m_root->​m_count > 0))
 +        {
 +            it.Push(m_root,​ 0);
 +            it.FindNextData();​
 +        }
 +    }
 +
 +    /// \brief 다음 횡단자를 계산한다.
 +    /// \param it 횡단자의 참조
 +    void GetNext(Iterator&​ it) { ++it; }
 +
 +    /// \brief 횡단자가 정상적인지의 여부를 반환한다.
 +    /// \param it 횡단자의 참조
 +    bool IsNull(Iterator&​ it) { return it.IsNull();​ }
 +
 +    /// \brief 해당 횡단자의 데이터 값을 반환한다.
 +    /// \param it 횡단자의 참조
 +    DATATYPE&​ GetAt(Iterator&​ it) { return *it; }
 +
 +
 +protected:
 +    /// 바운딩 박스 (N 차원)
 +    struct Rect
 +    {
 +        ELEMTYPE m_min[NUMDIMS];​ ///< 바운딩 박스의 최소값
 +        ELEMTYPE m_max[NUMDIMS];​ ///< 바운딩 박스의 최대값
 +    };
 +
 +    /// 실제 유저 데이터일 수도 있고, 자식 트리일 수도 있다.
 +    /// 부모의 레벨이 이를 결정한다. 부모의 레벨이 0이라면, 유저 데이터이다.
 +    struct Branch
 +    {
 +        Rect m_rect; ///< 바운딩 박스
 +        union
 +        {
 +            Node*    m_child; ///< 자식 노드
 +            DATATYPE m_data; ​ ///< 유저 데이터
 +        };
 +    };
 +
 +    /// 실제 노드
 +    struct Node
 +    {
 +        /// \brief 현재 노드가 리프 노드가 아닌지의 여부를 반환한다.
 +        bool IsInternalNode() const { return (m_level > 0); }
 +
 +        /// \brief 현재 노드가 리프 노드, 즉 실제 데이터를 가지는 노드인지의
 +        /// 여부를 반환한다.
 +        bool IsLeaf() const { return (m_level == 0); }
 +
 +        int    m_count; ​           ///< 카운트
 +        int    m_level; ​           ///< 리프 노드일 경우 0, 다른 경우에는 양수
 +        Branch m_branch[MAXNODES];​ ///< 자식 노드들
 +    };
 +
 +    /// 노드 삭제 후에 새로운 삽입을 위한 링크드 리스트
 +    struct ListNode
 +    {
 +        ListNode* m_next; ///< Next in list
 +        Node*     ​m_node;​ ///< Node
 +    };
 +
 +    /// 트리의 분할을 찾을 때 쓰이는 변수 객체
 +    struct PartitionVars
 +    {
 +        int          m_partition[MAXNODES+1];​
 +        int          m_total;
 +        int          m_minFill;
 +        int          m_taken[MAXNODES+1];​
 +        int          m_count[2];
 +        Rect         ​m_cover[2];​
 +        ELEMTYPEREAL m_area[2];
 +
 +        Branch ​      ​m_branchBuf[MAXNODES+1];​
 +        int          m_branchCount;​
 +        Rect         ​m_coverSplit;​
 +        ELEMTYPEREAL m_coverSplitArea;​
 +    }; 
 +
 +
 +protected:
 +    /// \brief 노드를 할당한다.
 +    /// \return Node* 새로 할당한 노드 객체
 +    Node* AllocNode();​
 +
 +    /// \brief 노드를 삭제한다.
 +    /// \param node 삭제할 노드
 +    void FreeNode(Node* node);
 +
 +    /// \brief 노드를 초기화한다.
 +    /// \param node 초기화할 노드
 +    void InitNode(Node* node);
 +
 +    /// \brief 바운딩 박스를 초기화한다.
 +    /// \param rect 초기화할 바운딩 박스
 +    void InitRect(Rect* rect);
 +
 +    /// \brief 유저 데이터와 사각형을 트리에다 집어넣는다. 재귀적으로 트리를
 +    /// 따라 내려가며,​ 필요하다면 새로운 분할도 만든다.
 +    /// \param rect 바운딩 박스
 +    /// \param id 유저 데이터
 +    /// \param node 부모 노드
 +    /// \param newNode 노드가 분할된 경우, 새로운 노드의 값이 들어간다.
 +    /// \param level 리프 노드로부터 얼마나 올라왔는가를 나타내는 변수.
 +    /// 즉 리프/ 노드(데이터 노드)라면 이 값은 0이다.
 +    /// \return bool 노드가 분할되지 않았다면,​ 0을 반환한다. 노드가 ​
 +    /// 분할되었다면 true를 반환하고,​ newNode 포인터의 값을 새로운 ​
 +    /// 가르키도록 변경한다.
 +    bool InsertRectRec(Rect* rect, const DATATYPE&​ id, Node* node, Node** newNode, int level);
 +
 +    /// \brief 유저 데이터와 사각형을 트리에다 집어넣는다.
 +    /// \param rect 바운딩 박스
 +    /// \param id 유저 데이터
 +    /// \param root 루트 노드
 +    /// \param level 리프 노드로부터 얼마나 올라왔는가를 나타내는 변수.
 +    /// 즉 리프/ 노드(데이터 노드)라면 이 값은 0이다.
 +    /// \return bool 노드가 분할되지 않았다면,​ 0을 반환한다. 노드가 분할되었다면 ​
 +    /// true를 반환한다.
 +    bool InsertRect(Rect* rect, const DATATYPE&​ id, Node** root, int level);
 +
 +    /// \brief 해당하는 노드 안에 들어있는 사각형들을 모두 감싸는 가장 작은
 +    /// 바운딩 박스를 계산한다.
 +    /// \param node 노드
 +    /// \return Rect Minimal Bounding Box
 +    Rect NodeCover(Node* node);
 +
 +    /// \brief 노드에다가 브랜치를 추가한다. 분할이 필요할 경우에는 분할도
 +    /// 한다.
 +    /// \param branch 추가할 브랜치
 +    /// \param node 노드
 +    /// \param newNode 노드가 분할된 경우, 새로운 노드의 값이 들어간다.
 +    /// \return bool 노드가 분할되지 않았다면 0을 반환한다. 분할되었다면 1을
 +    /// 반환한고,​ newNode의 값을 새로운 노드를 가르키도록 변경한다.
 +    bool AddBranch(Branch* branch, Node* node, Node** newNode);
 +
 +    /// \brief 노드와 브랜치의 연결을 끊는다. ​
 +    ///
 +    /// 이 함수를 호출한 다음에는 iterator의 값이 무효화되니 주의해야 한다.
 +    /// 
 +    /// \param node 노드
 +    /// \param index 브랜치 인덱스
 +    void DisconnectBranch(Node* node, int index);
 +
 +    /// \brief 새로운 바운딩 박스를 집어넣었을 때, 부피가 가장 적게 늘어나는
 +    /// 브랜치를 찾는다.
 +    /// \param rect 바운딩 박스
 +    /// \param node 노드
 +    /// \return int 브랜치 인덱스
 +    int PickBranch(Rect* rect, Node* node);
 +
 +    /// \brief 두 바운딩 박스를 모두 포함하는 바운딩 박스를 계산한다.
 +    /// \param rectA 바운딩 박스
 +    /// \param rectB 바운딩 박스
 +    /// \return Rect 두 바운딩 박스를 모두 포함하는 바운딩 박스
 +    Rect CombineRect(Rect* rectA, Rect* rectB);
 +
 +    /// \brief 노드를 분할한다.
 +    ///
 +    /// 주어진 노드의 브랜치 + 새로운 브랜치 == 2 노드로 분할한다.
 +    ///
 +    /// \param node 노드 (변경된다)
 +    /// \param branch 새로운 브랜치
 +    /// \param newNode 새로 생성한 노드
 +    void SplitNode(Node* node, Branch* branch, Node** newNode);
 +
 +    /// \brief 바운딩 박스의 구 부피 값을 반환한다.
 +    /// \param rect 바운딩 박스
 +    /// \return ELEMTYPEREAL 부피 값
 +    ELEMTYPEREAL RectSphericalVolume(Rect* rect);
 +
 +    /// \brief 바운딩 박스의 부피를 계산한다.
 +    /// \param rect 바운딩 박스
 +    /// \return ELEMTYPEREAL 부피 값
 +    ELEMTYPEREAL RectVolume(Rect* rect);
 +
 +    /// \brief 바운딩 박스의 부피를 계산한다.
 +    /// \param rect 바운딩 박스
 +    /// \return ELEMTYPEREAL 부피
 +    ELEMTYPEREAL CalcRectVolume(Rect* rect);
 +
 +    /// \brief 가득찬 노드 하나 + 브랜치 하나를 읽어들여 버퍼를 채운다.
 +    /// \param node 노드
 +    /// \param branch 브랜치
 +    /// \param parVars 버퍼
 +    void GetBranches(Node* node, Branch* branch, PartitionVars* parVars);
 +
 +    /// \brief 분할을 선택하기 위한 함수
 +    ///
 +    /// As the seeds for the two groups, pick the two rects that would waste the
 +    /// most area if covered by a single rectangle, i.e. evidently the worst pair
 +    /// to have in the same group.
 +    /// Of the remaining, one at a time is chosen to be put in one of the two 
 +    /// groups. The one chosen is the one with the greatest difference in area 
 +    /// expansion depending on which group - the rect most strongly attracted to
 +    /// one group and repelled from the other.
 +    /// If one group gets too full (more would force other group to violate min
 +    /// fill requirement) then other group gets the rest.
 +    /// These last are the ones that can go in either group most easily.
 +    /// 
 +    /// \param parVars 버퍼
 +    /// \param minFill 최소 채우기 값
 +    void ChoosePartition(PartitionVars* parVars, int minFill);
 +
 +    /// \brief 분할에 따라, 브랜드치들을 버퍼에서 복사한다.
 +    /// \param nodeA 노드
 +    /// \param nodeB 노드
 +    /// \param parVars 버퍼
 +    void LoadNodes(Node* nodeA, Node* nodeB, PartitionVars* parVars);
 +
 +    /// \brief 트리의 분할을 찾을 때 쓰이는 변수 객체를 초기화한다.
 +    /// \param parVars 변수 객체
 +    /// \param maxRects 사격형의 갯수
 +    /// \param minFill 최소 채우기 값
 +    void InitParVars(PartitionVars* parVars, int maxRects, int minFill);
 +
 +    /// \brief 트리의 분할을 위한 시드 값을 계산한다.
 +    /// \param parVars 트리의 분할을 찾을 때 쓰이는 변수 객체
 +    void PickSeeds(PartitionVars* parVars);
 +
 +    /// \brief 브랜치를 그룹별로 구분한다.
 +    /// \param index 브랜치의 인덱스
 +    /// \param group 그룹 인덱스
 +    /// \param parVars 트리의 분할을 찾을 때 쓰이는 변수 객체
 +    void Classify(int index, int group, PartitionVars* parVars);
 +
 +    /// \brief 바운딩 박스를 삭제한다.
 +    /// \param rect 제거할 바운딩 박스
 +    /// \param id 제거할 유저 데이터
 +    /// \param root 루트 노드
 +    /// \return bool 성공적으로 삭제한 경우에는 0을 반환하고,​ 해당 데이터를 찾지
 +    /// 못한 경우에는 1을 반환한다.
 +    bool RemoveRect(Rect* rect, const DATATYPE&​ id, Node** root);
 +
 +    /// \brief 루트가 아닌 다른 노드에서 바운딩 박스를 삭제한다.
 +    ///
 +    /// RemoveRect 함수에서 호출한다. 트리를 따라내려가며,​ 노드를 합쳐야하는
 +    /// 경우에는 합친다.
 +    ///
 +    /// \param rect 제거할 바운딩 박스
 +    /// \param id 제거할 유저 데이터
 +    /// \param node 부모 노드
 +    /// \param listNode 재삽입 리스트 객체
 +    /// \return bool 성공적으로 삭제한 경우에는 0을 반환하고,​ 해당 데이터를 찾지
 +    /// 못한 경우에는 1을 반환한다.
 +    bool RemoveRectRec(Rect* rect, const DATATYPE&​ id, Node* node, ListNode** listNode);
 +
 +    /// \brief 리스트 노드를 할당한다.
 +    /// \return ListNode* 새로 할당한 리스트 노드
 +    ListNode* AllocListNode();​
 +
 +    /// \brief 리스트 노드를 삭제한다.
 +    /// \param listNode 삭제할 리스트 노드
 +    void FreeListNode(ListNode* listNode);
 +
 +    /// \brief 두 바운딩 박스가 겹치는지의 여부를 반환한다.
 +    /// \param rectA 바운딩 박스
 +    /// \param rectB 바운딩 박스
 +    /// \return bool 겹치는 경우 true, 겹치지 않는 경우 false
 +    bool Overlap(Rect* rectA, Rect* rectB) const;
 +
 +    /// \brief 노드를 재삽입 리스트에다 추가한다. 해당 노드와 브랜치들은 ​
 +    /// 나중에 트리에 새로이 추가한다.
 +    /// \param node 노드
 +    /// \param listNode 리스트 객체
 +    void ReInsert(Node* node, ListNode** listNode);
 +
 +    /// \brief 실제 검색 함수
 +    /// \param node 검색할 노드
 +    /// \param rect 바운딩 박스
 +    /// \param foundCount 찾은 데이터의 갯수
 +    /// \param results 찾은 데이터를 집어넣을 컬렉션
 +    /// \return bool 상위 함수에서 검색을 계속해야하는 경우에는 true, 검색을
 +    /// 중단해야하는 경우에는 false.
 +    bool Search(Node* node, Rect* rect, int& foundCount, RESULTS&​ results);
 +
 +    /// \brief 해당하는 노드와 자식 노드들을 모두 삭제한다.
 +    /// \param node 삭제할 노드
 +    void RemoveAllRec(Node* node);
 +
 +    /// \brief 모든 노드들을 삭제한다.
 +    void Reset();
 +
 +    /// \brief 트리 안에 있는 데이터의 갯수를 센다.
 +    /// \param node 부모 노드의 포인터
 +    /// \param count 데이터의 갯수를 집어넣을 변수
 +    void CountRec(Node* node, int& count);
 +
 +    /// \brief 스트림에서 레코드를 읽어들인다.
 +    /// \param node 부모 노드
 +    /// \param stream 레코드를 읽어들일 스트림 객체
 +    /// \return bool 정상적으로 로드한 경우에는 true를 반환하고,​ 뭔가 에러가
 +    /// 생긴 경우에는 false를 반환한다.
 +    bool LoadRec(Node* node, RTFileStream&​ stream);
 +
 +    /// \brief 스트림에다 레코드를 저장한다.
 +    /// \param node 부모 노드
 +    /// \param stream 레코드를 저장할 스트림 객체
 +    /// \return bool 정상적으로 저장한 경우에는 true를 반환한고,​ 뭔가 에러가
 +    /// 생긴 경우에는 false를 반환한다.
 +    bool SaveRec(Node* node, RTFileStream&​ stream);
 +};
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \class RTFileStream
 +/// \brief Because there is not stream support, this is a quick and dirty 
 +/// file I/O helper. Users will likely replace its usage with a Stream ​
 +/// implementation from their favorite API.
 +//////////////////////////////////////////////////////////////////////////////​
 +
 +class RTFileStream
 +{
 +    FILE* m_file;
 +
 +public:
 +    RTFileStream() : m_file(NULL) {}
 +    ~RTFileStream() { Close(); }
 +
 +    bool OpenRead(const char* fileName)
 +    {
 +        m_file = fopen(fileName,​ "​rb"​);​
 +        return !m_file ? false : true;
 +    }
 +
 +    bool OpenWrite(const char* fileName)
 +    {
 +        m_file = fopen(fileName,​ "​wb"​);​
 +        return !m_file ? false : true;
 +    }
 +
 +    void Close()
 +    {
 +        if (m_file)
 +        {
 +            fclose(m_file);​
 +            m_file = NULL;
 +        }
 +    }
 +
 +    template<​ typename TYPE >
 +    size_t Write(const TYPE& value)
 +    {
 +        Assert(m_file);​
 +        return fwrite((void*)&​value,​ sizeof(value),​ 1, m_file);
 +    }
 +
 +    template<​ typename TYPE >
 +    size_t WriteArray(const TYPE* array, int count)
 +    {
 +        Assert(m_file);​
 +        return fwrite((void*)array,​ sizeof(TYPE) * count, 1, m_file);
 +    }
 +
 +    template<​ typename TYPE >
 +    size_t Read(TYPE&​ value)
 +    {
 +        Assert(m_file);​
 +        return fread((void*)&​value,​ sizeof(value),​ 1, m_file);
 +    }
 +
 +    template<​ typename TYPE >
 +    size_t ReadArray(TYPE* array, int count)
 +    {
 +        Assert(m_file);​
 +        return fread((void*)array,​ sizeof(TYPE) * count, 1, m_file);
 +    }
 +};
 +
 +
 +#define RTREE_TEMPLATE template<​class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL,​ int TMAXNODES, int TMINNODES>​
 +#define RTREE_QUALIFIER RTree<​DATATYPE,​ ELEMTYPE, NUMDIMS, ELEMTYPEREAL,​ TMAXNODES, TMINNODES>​
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 생성자
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +RTREE_QUALIFIER::​RTree()
 +{
 +    Assert(MAXNODES > MINNODES);
 +    Assert(MINNODES > 0);
 +
 +    // 위에서도 설명했듯이,​ int 크기까지의 데이터만 다룰 수 있다.
 +    // 자세한 것은 Branch 구조체를 보면 알 것이다.
 +    Assert(sizeof(DATATYPE) == sizeof(void*) || sizeof(DATATYPE) == sizeof(int));​
 +
 +    // Precomputed volumes of the unit spheres for the first few dimensions
 +    const float UNIT_SPHERE_VOLUMES[] = 
 +    {
 +        0.000000f, 2.000000f, 3.141593f, // Dimension ​ 0,1,2
 +        4.188790f, 4.934802f, 5.263789f, // Dimension ​ 3,4,5
 +        5.167713f, 4.724766f, 4.058712f, // Dimension ​ 6,7,8
 +        3.298509f, 2.550164f, 1.884104f, // Dimension ​ 9,10,11
 +        1.335263f, 0.910629f, 0.599265f, // Dimension ​ 12,13,14
 +        0.381443f, 0.235331f, 0.140981f, // Dimension ​ 15,16,17
 +        0.082146f, 0.046622f, 0.025807f ​ // Dimension ​ 18,​19,​20 ​
 +    };
 +
 +    m_root ​            = AllocNode();​
 +    m_root->​m_level ​   = 0;
 +    m_unitSphereVolume = (ELEMTYPEREAL)UNIT_SPHERE_VOLUMES[NUMDIMS];​
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 소멸자
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +RTREE_QUALIFIER::​~RTree()
 +{
 +    Reset(); // Free, or reset node memory
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 데이터를 집어넣는다.
 +/// \param min 바운딩 박스의 최소값
 +/// \param max 바운딩 박스의 최대값
 +/// \param dataId 실제 데이터의 ID. 양수여야 한다. 0은 되나 음수값은
 +/// 사용할 수 없다.
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +void RTREE_QUALIFIER::​Insert(const ELEMTYPE min[NUMDIMS],​ const ELEMTYPE max[NUMDIMS],​ const DATATYPE&​ dataId)
 +{
 +#ifdef _DEBUG
 +    for (int index=0; index<​NUMDIMS;​ ++index)
 +    {
 +        Assert(min[index] <= max[index]);​
 +    }
 +#endif //_DEBUG
 +
 +    Rect rect;
 +
 +    for (int axis=0; axis<​NUMDIMS;​ ++axis)
 +    {
 +        rect.m_min[axis] = min[axis];
 +        rect.m_max[axis] = max[axis];
 +    }
 +
 +    InsertRect(&​rect,​ dataId, &​m_root,​ 0);
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 데이터를 제거한다.
 +/// \param min 바운딩 박스의 최소값
 +/// \param max 바운딩 박스의 최대값
 +/// \param dataId 실제 데이터의 ID. 양수여야 한다. 0은 되나 음수값은
 +/// 사용할 수 없다.
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +void RTREE_QUALIFIER::​Remove(const ELEMTYPE min[NUMDIMS],​ const ELEMTYPE max[NUMDIMS],​ const DATATYPE&​ dataId)
 +{
 +#ifdef _DEBUG
 +    for (int index=0; index<​NUMDIMS;​ ++index)
 +    {
 +        Assert(min[index] <= max[index]);​
 +    }
 +#endif //_DEBUG
 +
 +    Rect rect;
 +
 +    for (int axis=0; axis<​NUMDIMS;​ ++axis)
 +    {
 +        rect.m_min[axis] = min[axis];
 +        rect.m_max[axis] = max[axis];
 +    }
 +
 +    RemoveRect(&​rect,​ dataId, &​m_root);​
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 해당하는 바운딩 박스에 포함되는 모든 데이터들을 찾는다.
 +/// \param min 바운딩 박스의 최소값
 +/// \param max 바운딩 박스의 최대값
 +/// \param results 결과값을 집어넣을 컬렉션 객체
 +/// \return 찾은 데이터의 갯수
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +int RTREE_QUALIFIER::​Search(const ELEMTYPE min[NUMDIMS],​ const ELEMTYPE max[NUMDIMS],​ RESULTS&​ results)
 +{
 +#ifdef _DEBUG
 +    for (int index=0; index<​NUMDIMS;​ ++index)
 +    {
 +        Assert(min[index] <= max[index]);​
 +    }
 +#endif //_DEBUG
 +
 +    Rect rect;
 +    for (int axis=0; axis<​NUMDIMS;​ ++axis)
 +    {
 +        rect.m_min[axis] = min[axis];
 +        rect.m_max[axis] = max[axis];
 +    }
 +
 +    // NOTE: May want to return search result another way,
 +    // perhaps returning the number of found elements here.
 +    int foundCount = 0;
 +    Search(m_root,​ &rect, foundCount, results);
 +    return foundCount;
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 트리 안에 있는 데이터의 갯수를 반환한다.
 +///
 +/// 내부적으로 데이터의 갯수를 유지하지 않고, 이 함수가 호출될 때마다 ​
 +/// 계산하기 때문에 느리다. 자주 호출하지 말 것.
 +///
 +/// \return int 트리 안에 있는 데이터의 갯수
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +int RTREE_QUALIFIER::​Count()
 +{
 +    int count = 0;
 +    CountRec(m_root,​ count);
 +    return count;
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 트리 안에 있는 데이터의 갯수를 센다.
 +/// \param node 부모 노드의 포인터
 +/// \param count 데이터의 갯수를 집어넣을 변수
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +void RTREE_QUALIFIER::​CountRec(Node* node, int& count)
 +{
 +    if (node->​IsInternalNode()) ​ // not a leaf node
 +    {
 +        for (int index = 0; index < node->​m_count;​ ++index)
 +        {
 +            CountRec(node->​m_branch[index].m_child,​ count);
 +        }
 +    }
 +    else // A leaf node
 +    {
 +        count += node->​m_count;​
 +    }
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 파일에서 트리를 로드한다.
 +/// \param fileName 파일 이름
 +/// \return bool 정상적으로 로드한 경우에는 true를 반환하고,​ 뭔가 에러가
 +/// 생긴 경우에는 false를 반환한다.
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +bool RTREE_QUALIFIER::​Load(const char* fileName)
 +{
 +    RemoveAll();​ // Clear existing tree
 +
 +    RTFileStream stream;
 +    if (!stream.OpenRead(fileName))
 +    {
 +        return false;
 +    }
 +
 +    bool result = Load(stream);​
 +
 +    stream.Close();​
 +
 +    return result;
 +};
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 스트림에서 트리를 로드한다.
 +/// \param stream 스트림 객체
 +/// \return bool 정상적으로 로드한 경우에는 true를 반환하고,​ 뭔가 에러가
 +/// 생긴 경우에는 false를 반환한다.
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +bool RTREE_QUALIFIER::​Load(RTFileStream&​ stream)
 +{
 +    // Write some kind of header
 +    int _dataFileId = ('​R'<<​0)|('​T'<<​8)|('​R'<<​16)|('​E'<<​24);​
 +    int _dataSize = sizeof(DATATYPE);​
 +    int _dataNumDims = NUMDIMS;
 +    int _dataElemSize = sizeof(ELEMTYPE);​
 +    int _dataElemRealSize = sizeof(ELEMTYPEREAL);​
 +    int _dataMaxNodes = TMAXNODES;
 +    int _dataMinNodes = TMINNODES;
 +
 +    int dataFileId = 0;
 +    int dataSize = 0;
 +    int dataNumDims = 0;
 +    int dataElemSize = 0;
 +    int dataElemRealSize = 0;
 +    int dataMaxNodes = 0;
 +    int dataMinNodes = 0;
 +
 +    stream.Read(dataFileId);​
 +    stream.Read(dataSize);​
 +    stream.Read(dataNumDims);​
 +    stream.Read(dataElemSize);​
 +    stream.Read(dataElemRealSize);​
 +    stream.Read(dataMaxNodes);​
 +    stream.Read(dataMinNodes);​
 +
 +    bool result = false;
 +
 +    // Test if header was valid and compatible
 +    if (   ​(dataFileId == _dataFileId) ​
 +        && (dataSize == _dataSize) ​
 +        && (dataNumDims == _dataNumDims) ​
 +        && (dataElemSize == _dataElemSize) ​
 +        && (dataElemRealSize == _dataElemRealSize) ​
 +        && (dataMaxNodes == _dataMaxNodes) ​
 +        && (dataMinNodes == _dataMinNodes) ​
 +        )
 +    {
 +        // Recursively load tree
 +        result = LoadRec(m_root,​ stream);
 +    }
 +
 +    return result;
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 스트림에서 레코드를 읽어들인다.
 +/// \param node 부모 노드
 +/// \param stream 레코드를 읽어들일 스트림 객체
 +/// \return bool 정상적으로 로드한 경우에는 true를 반환하고,​ 뭔가 에러가
 +/// 생긴 경우에는 false를 반환한다.
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +bool RTREE_QUALIFIER::​LoadRec(Node* node, RTFileStream&​ stream)
 +{
 +    stream.Read(node->​m_level);​
 +    stream.Read(node->​m_count);​
 +
 +    if (node->​IsInternalNode()) ​ // not a leaf node
 +    {
 +        for (int index = 0; index < node->​m_count;​ ++index)
 +        {
 +            Branch* curBranch = &​node->​m_branch[index];​
 +
 +            stream.ReadArray(curBranch->​m_rect.m_min,​ NUMDIMS);
 +            stream.ReadArray(curBranch->​m_rect.m_max,​ NUMDIMS);
 +
 +            curBranch->​m_child = AllocNode();​
 +            LoadRec(curBranch->​m_child,​ stream);
 +        }
 +    }
 +    else // A leaf node
 +    {
 +        for (int index = 0; index < node->​m_count;​ ++index)
 +        {
 +            Branch* curBranch = &​node->​m_branch[index];​
 +
 +            stream.ReadArray(curBranch->​m_rect.m_min,​ NUMDIMS);
 +            stream.ReadArray(curBranch->​m_rect.m_max,​ NUMDIMS);
 +
 +            stream.Read(curBranch->​m_data);​
 +        }
 +    }
 +
 +    return true; // Should do more error checking on I/O operations
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 파일에다 트리를 저장한다.
 +/// \param fileName 파일 이름
 +/// \return bool 정상적으로 저장한 경우에는 true를 반환한고,​ 뭔가 에러가
 +/// 생긴 경우에는 false를 반환한다.
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +bool RTREE_QUALIFIER::​Save(const char* fileName)
 +{
 +    RTFileStream stream;
 +    if (!stream.OpenWrite(fileName))
 +    {
 +        return false;
 +    }
 +
 +    bool result = Save(stream);​
 +
 +    stream.Close();​
 +
 +    return result;
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 스트림에다 트리를 저장한다.
 +/// \param stream 스트림 객체
 +/// \return bool 정상적으로 저장한 경우에는 true를 반환한고,​ 뭔가 에러가
 +/// 생긴 경우에는 false를 반환한다.
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +bool RTREE_QUALIFIER::​Save(RTFileStream&​ stream)
 +{
 +    // Write some kind of header
 +    int dataFileId = ('​R'<<​0)|('​T'<<​8)|('​R'<<​16)|('​E'<<​24);​
 +    int dataSize = sizeof(DATATYPE);​
 +    int dataNumDims = NUMDIMS;
 +    int dataElemSize = sizeof(ELEMTYPE);​
 +    int dataElemRealSize = sizeof(ELEMTYPEREAL);​
 +    int dataMaxNodes = TMAXNODES;
 +    int dataMinNodes = TMINNODES;
 +
 +    stream.Write(dataFileId);​
 +    stream.Write(dataSize);​
 +    stream.Write(dataNumDims);​
 +    stream.Write(dataElemSize);​
 +    stream.Write(dataElemRealSize);​
 +    stream.Write(dataMaxNodes);​
 +    stream.Write(dataMinNodes);​
 +
 +    // Recursively save tree
 +    bool result = SaveRec(m_root,​ stream);
 +
 +    return result;
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 스트림에다 레코드를 저장한다.
 +/// \param node 부모 노드
 +/// \param stream 레코드를 저장할 스트림 객체
 +/// \return bool 정상적으로 저장한 경우에는 true를 반환한고,​ 뭔가 에러가
 +/// 생긴 경우에는 false를 반환한다.
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +bool RTREE_QUALIFIER::​SaveRec(Node* node, RTFileStream&​ stream)
 +{
 +    stream.Write(node->​m_level);​
 +    stream.Write(node->​m_count);​
 +
 +    if (node->​IsInternalNode()) ​ // not a leaf node
 +    {
 +        for (int index = 0; index < node->​m_count;​ ++index)
 +        {
 +            Branch* curBranch = &​node->​m_branch[index];​
 +
 +            stream.WriteArray(curBranch->​m_rect.m_min,​ NUMDIMS);
 +            stream.WriteArray(curBranch->​m_rect.m_max,​ NUMDIMS);
 +
 +            SaveRec(curBranch->​m_child,​ stream);
 +        }
 +    }
 +    else // A leaf node
 +    {
 +        for (int index = 0; index < node->​m_count;​ ++index)
 +        {
 +            Branch* curBranch = &​node->​m_branch[index];​
 +
 +            stream.WriteArray(curBranch->​m_rect.m_min,​ NUMDIMS);
 +            stream.WriteArray(curBranch->​m_rect.m_max,​ NUMDIMS);
 +
 +            stream.Write(curBranch->​m_data);​
 +        }
 +    }
 +
 +    return true; // Should do more error checking on I/O operations
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 모든 데이터를 제거하고,​ 루트 노드를 초기화한다.
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +void RTREE_QUALIFIER::​RemoveAll()
 +{
 +    Reset();
 +
 +    m_root = AllocNode();​
 +    m_root->​m_level = 0;
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 모든 노드들을 삭제한다.
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +void RTREE_QUALIFIER::​Reset()
 +{
 +#ifdef RTREE_DONT_USE_MEMPOOLS
 +    // Delete all existing nodes
 +    RemoveAllRec(m_root);​
 +#else // RTREE_DONT_USE_MEMPOOLS
 +    // Just reset memory pools. ​ We are not using complex types
 +    // EXAMPLE
 +#endif // RTREE_DONT_USE_MEMPOOLS
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 해당하는 노드와 자식 노드들을 모두 삭제한다.
 +/// \param node 삭제할 노드
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +void RTREE_QUALIFIER::​RemoveAllRec(Node* node)
 +{
 +    Assert(node);​
 +    Assert(node->​m_level >= 0);
 +
 +    if (node->​IsInternalNode()) // This is an internal node in the tree
 +    {
 +        for (int index=0; index < node->​m_count;​ ++index)
 +        {
 +            RemoveAllRec(node->​m_branch[index].m_child);​
 +        }
 +    }
 +
 +    FreeNode(node); ​
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 노드를 할당한다.
 +/// \return Node* 새로 할당한 노드 객체
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +typename RTREE_QUALIFIER::​Node* RTREE_QUALIFIER::​AllocNode()
 +{
 +    Node* newNode;
 +#ifdef RTREE_DONT_USE_MEMPOOLS
 +    newNode = new Node;
 +#else // RTREE_DONT_USE_MEMPOOLS
 +    // EXAMPLE
 +#endif // RTREE_DONT_USE_MEMPOOLS
 +    InitNode(newNode);​
 +    return newNode;
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 노드를 삭제한다.
 +/// \param node 삭제할 노드
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +void RTREE_QUALIFIER::​FreeNode(Node* node)
 +{
 +    Assert(node);​
 +
 +#ifdef RTREE_DONT_USE_MEMPOOLS
 +    delete node;
 +#else // RTREE_DONT_USE_MEMPOOLS
 +    // EXAMPLE
 +#endif // RTREE_DONT_USE_MEMPOOLS
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 리스트 노드를 할당한다.
 +/// \return ListNode* 새로 할당한 리스트 노드
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +typename RTREE_QUALIFIER::​ListNode* RTREE_QUALIFIER::​AllocListNode()
 +{
 +#ifdef RTREE_DONT_USE_MEMPOOLS
 +    return new ListNode;
 +#else // RTREE_DONT_USE_MEMPOOLS
 +    // EXAMPLE
 +#endif // RTREE_DONT_USE_MEMPOOLS
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 리스트 노드를 삭제한다.
 +/// \param listNode 삭제할 리스트 노드
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +void RTREE_QUALIFIER::​FreeListNode(ListNode* listNode)
 +{
 +#ifdef RTREE_DONT_USE_MEMPOOLS
 +    delete listNode;
 +#else // RTREE_DONT_USE_MEMPOOLS
 +    // EXAMPLE
 +#endif // RTREE_DONT_USE_MEMPOOLS
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 노드를 초기화한다.
 +/// \param node 초기화할 노드
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +void RTREE_QUALIFIER::​InitNode(Node* node)
 +{
 +    node->​m_count = 0;
 +    node->​m_level = -1;
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 바운딩 박스를 초기화한다.
 +/// \param rect 초기화할 바운딩 박스
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +void RTREE_QUALIFIER::​InitRect(Rect* rect)
 +{
 +    for (int index = 0; index < NUMDIMS; ++index)
 +    {
 +        rect->​m_min[index] = (ELEMTYPE)0;​
 +        rect->​m_max[index] = (ELEMTYPE)0;​
 +    }
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 유저 데이터와 사각형을 트리에다 집어넣는다. 재귀적으로 트리를
 +/// 따라 내려가며,​ 필요하다면 새로운 분할도 만든다.
 +/// \param rect 바운딩 박스
 +/// \param id 유저 데이터
 +/// \param node 부모 노드
 +/// \param newNode 노드가 분할된 경우, 새로운 노드의 값이 들어간다.
 +/// \param level 리프 노드로부터 얼마나 올라왔는가를 나타내는 변수. ​
 +/// 즉 리프 노드(데이터 노드)라면 이 값은 0이다.
 +/// \return bool 노드가 분할되지 않았다면,​ 0을 반환한다. 노드가 분할되었다면
 +/// true를 반환하고,​ newNode 포인터의 값을 새로운 가르키도록 변경한다.
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +bool RTREE_QUALIFIER::​InsertRectRec(Rect* rect, const DATATYPE&​ id, Node* node, Node** newNode, int level)
 +{
 +    Assert(rect && node && newNode);
 +    Assert(level >= 0 && level <= node->​m_level);​
 +
 +    int index;
 +    Branch branch;
 +    Node* otherNode;
 +
 +    // Still above level for insertion, go down tree recursively
 +    if (node->​m_level > level)
 +    {
 +        index = PickBranch(rect,​ node);
 +        if (!InsertRectRec(rect,​ id, node->​m_branch[index].m_child,​ &​otherNode,​ level))
 +        {
 +            // Child was not split
 +            node->​m_branch[index].m_rect = CombineRect(rect,​ &​(node->​m_branch[index].m_rect));​
 +            return false;
 +        }
 +        else // Child was split
 +        {
 +            node->​m_branch[index].m_rect = NodeCover(node->​m_branch[index].m_child);​
 +            branch.m_child = otherNode;
 +            branch.m_rect = NodeCover(otherNode);​
 +            return AddBranch(&​branch,​ node, newNode);
 +        }
 +    }
 +    else if (node->​m_level == level) // Have reached level for insertion. Add rect, split if necessary
 +    {
 +        branch.m_rect = *rect;
 +        branch.m_child = (Node*) id;
 +        // Child field of leaves contains id of data record
 +        return AddBranch(&​branch,​ node, newNode);
 +    }
 +    else
 +    {
 +        // Should never occur
 +        Assert(0);
 +        return false;
 +    }
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 유저 데이터와 사각형을 트리에다 집어넣는다.
 +/// 
 +/// 실제로 트리의 분할을 담당하는 함수는 InsertRectRec 함수다.
 +///
 +/// \param rect 바운딩 박스
 +/// \param id 유저 데이터
 +/// \param root 루트 노드
 +/// \param level 리프 노드로부터 얼마나 올라왔는가를 나타내는 변수.
 +/// 즉 리프/ 노드(데이터 노드)라면 이 값은 0이다.
 +/// \return bool 노드가 분할되지 않았다면,​ 0을 반환한다. 노드가 분할되었다면 ​
 +/// true를 반환한다.
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +bool RTREE_QUALIFIER::​InsertRect(Rect* rect, const DATATYPE&​ id, Node** root, int level)
 +{
 +    Assert(rect && root);
 +    Assert(level >= 0 && level <= (*root)->​m_level);​
 +#ifdef _DEBUG
 +    for (int index=0; index < NUMDIMS; ++index)
 +    {
 +        Assert(rect->​m_min[index] <= rect->​m_max[index]);​
 +    }
 +#endif //​_DEBUG  ​
 +
 +    Node* newRoot = NULL;
 +    Node* newNode = NULL;
 +    Branch branch;
 +
 +    if (InsertRectRec(rect,​ id, *root, &​newNode,​ level)) ​ // Root split
 +    {
 +        newRoot = AllocNode(); ​ // Grow tree taller and new root
 +        newRoot->​m_level = (*root)->​m_level + 1;
 +        branch.m_rect = NodeCover(*root);​
 +        branch.m_child = *root;
 +        AddBranch(&​branch,​ newRoot, NULL);
 +        branch.m_rect = NodeCover(newNode);​
 +        branch.m_child = newNode;
 +        AddBranch(&​branch,​ newRoot, NULL);
 +        *root = newRoot;
 +        return true;
 +    }
 +
 +    return false;
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 해당하는 노드 안에 들어있는 사각형들을 모두 감싸는 가장 작은
 +/// 바운딩 박스를 계산한다.
 +/// \param node 노드
 +/// \return Rect Minimal Bounding Box
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +typename RTREE_QUALIFIER::​Rect RTREE_QUALIFIER::​NodeCover(Node* node)
 +{
 +    Assert(node);​
 +
 +    int firstTime = true;
 +    Rect rect;
 +    InitRect(&​rect);​
 +
 +    for (int index = 0; index < node->​m_count;​ ++index)
 +    {
 +        if (firstTime)
 +        {
 +            rect = node->​m_branch[index].m_rect;​
 +            firstTime = false;
 +        }
 +        else
 +        {
 +            rect = CombineRect(&​rect,​ &​(node->​m_branch[index].m_rect));​
 +        }
 +    }
 +
 +    return rect;
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 노드에다가 브랜치를 추가한다. 분할이 필요할 경우에는 분할도
 +/// 한다.
 +/// \param branch 추가할 브랜치
 +/// \param node 노드
 +/// \param newNode 노드가 분할된 경우, 새로운 노드의 값이 들어간다.
 +/// \return bool 노드가 분할되지 않았다면 0을 반환한다. 분할되었다면 1을
 +/// 반환한고,​ newNode의 값을 새로운 노드를 가르키도록 변경한다.
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +bool RTREE_QUALIFIER::​AddBranch(Branch* branch, Node* node, Node** newNode)
 +{
 +    Assert(branch);​
 +    Assert(node);​
 +
 +    if (node->​m_count < MAXNODES) ​ // Split won't be necessary
 +    {
 +        node->​m_branch[node->​m_count] = *branch;
 +        ++node->​m_count;​
 +
 +        return false;
 +    }
 +    else
 +    {
 +        Assert(newNode);​
 +
 +        SplitNode(node,​ branch, newNode);
 +        return true;
 +    }
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 노드와 브랜치의 연결을 끊는다. ​
 +///
 +/// 이 함수를 호출한 다음에는 iterator의 값이 무효화되니 주의해야 한다.
 +/// 
 +/// \param node 노드
 +/// \param index 브랜치 인덱스
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +void RTREE_QUALIFIER::​DisconnectBranch(Node* node, int index)
 +{
 +    Assert(node && (index >= 0) && (index < MAXNODES));
 +    Assert(node->​m_count > 0);
 +
 +    // Remove element by swapping with the last element to prevent gaps in array
 +    node->​m_branch[index] = node->​m_branch[node->​m_count - 1];
 +
 +    --node->​m_count;​
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 새로운 바운딩 박스를 집어넣었을 때, 부피가 가장 적게 늘어나는
 +/// 브랜치를 찾는다.
 +/// \param rect 바운딩 박스
 +/// \param node 노드
 +/// \return int 브랜치 인덱스
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +int RTREE_QUALIFIER::​PickBranch(Rect* rect, Node* node)
 +{
 +    Assert(rect && node);
 +
 +    bool         ​firstTime = true;
 +    ELEMTYPEREAL increase = 0;
 +    ELEMTYPEREAL bestIncr = (ELEMTYPEREAL)-1;​
 +    ELEMTYPEREAL area = 0;
 +    ELEMTYPEREAL bestArea = 0;
 +    int          best = 0;
 +    Rect         ​tempRect;​
 +
 +    for (int index=0; index < node->​m_count;​ ++index)
 +    {
 +        Rect* curRect = &​node->​m_branch[index].m_rect;​
 +        area = CalcRectVolume(curRect);​
 +        tempRect = CombineRect(rect,​ curRect);
 +        increase = CalcRectVolume(&​tempRect) - area;
 +        if ((increase < bestIncr) || firstTime)
 +        {
 +            best = index;
 +            bestArea = area;
 +            bestIncr = increase;
 +            firstTime = false;
 +        }
 +        else if ((increase == bestIncr) && (area < bestArea))
 +        {
 +            best = index;
 +            bestArea = area;
 +            bestIncr = increase;
 +        }
 +    }
 +
 +    return best;
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 두 바운딩 박스를 모두 포함하는 바운딩 박스를 계산한다.
 +/// \param rectA 바운딩 박스
 +/// \param rectB 바운딩 박스
 +/// \return Rect 두 바운딩 박스를 모두 포함하는 바운딩 박스
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +typename RTREE_QUALIFIER::​Rect RTREE_QUALIFIER::​CombineRect(Rect* rectA, Rect* rectB)
 +{
 +    Assert(rectA && rectB);
 +
 +    Rect newRect;
 +
 +    for (int index = 0; index < NUMDIMS; ++index)
 +    {
 +        newRect.m_min[index] = __min(rectA->​m_min[index],​ rectB->​m_min[index]);​
 +        newRect.m_max[index] = __max(rectA->​m_max[index],​ rectB->​m_max[index]);​
 +    }
 +
 +    return newRect;
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 노드를 분할한다.
 +///
 +/// 주어진 노드의 브랜치 + 새로운 브랜치 == 2 노드로 분할한다.
 +///
 +/// \param node 노드 (변경된다)
 +/// \param branch 새로운 브랜치
 +/// \param newNode 새로 생성한 노드
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +void RTREE_QUALIFIER::​SplitNode(Node* node, Branch* branch, Node** newNode)
 +{
 +    Assert(node);​
 +    Assert(branch);​
 +
 +    // Could just use local here, but member or external is faster since it is reused
 +    PartitionVars localVars;
 +    PartitionVars* parVars = &​localVars;​
 +    int level;
 +
 +    // Load all the branches into a buffer, initialize old node
 +    level = node->​m_level;​
 +    GetBranches(node,​ branch, parVars);
 +
 +    // Find partition
 +    ChoosePartition(parVars,​ MINNODES);
 +
 +    // Put branches from buffer into 2 nodes according to chosen partition
 +    *newNode = AllocNode();​
 +    (*newNode)->​m_level = node->​m_level = level;
 +    LoadNodes(node,​ *newNode, parVars);
 +
 +    Assert((node->​m_count + (*newNode)->​m_count) == parVars->​m_total);​
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 바운딩 박스의 부피를 계산한다.
 +/// \param rect 바운딩 박스
 +/// \return ELEMTYPEREAL 부피 값
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +ELEMTYPEREAL RTREE_QUALIFIER::​RectVolume(Rect* rect)
 +{
 +    Assert(rect);​
 +
 +    ELEMTYPEREAL volume = (ELEMTYPEREAL)1;​
 +
 +    for (int index=0; index<​NUMDIMS;​ ++index)
 +    {
 +        volume *= rect->​m_max[index] - rect->​m_min[index];​
 +    }
 +
 +    Assert(volume >= (ELEMTYPEREAL)0);​
 +
 +    return volume;
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 바운딩 박스의 구 부피 값을 반환한다.
 +/// \param rect 바운딩 박스
 +/// \return ELEMTYPEREAL 부피 값
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +ELEMTYPEREAL RTREE_QUALIFIER::​RectSphericalVolume(Rect* rect)
 +{
 +    Assert(rect);​
 +
 +    ELEMTYPEREAL sumOfSquares = (ELEMTYPEREAL)0;​
 +    ELEMTYPEREAL radius;
 +
 +    for (int index=0; index < NUMDIMS; ++index) ​
 +    {
 +        ELEMTYPEREAL halfExtent = ((ELEMTYPEREAL)rect->​m_max[index] - (ELEMTYPEREAL)rect->​m_min[index]) * 0.5f;
 +        sumOfSquares += halfExtent * halfExtent;
 +    }
 +
 +    radius = (ELEMTYPEREAL)sqrt(sumOfSquares);​
 +
 +    // Pow maybe slow, so test for common dims like 2,3 and just use x*x, x*x*x.
 +    if (NUMDIMS == 3)
 +    {
 +        return (radius * radius * radius * m_unitSphereVolume);​
 +    }
 +    else if (NUMDIMS == 2)
 +    {
 +        return (radius * radius * m_unitSphereVolume);​
 +    }
 +    else
 +    {
 +        return (ELEMTYPEREAL)(pow(radius,​ NUMDIMS) * m_unitSphereVolume);​
 +    }
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 바운딩 박스의 부피를 계산한다.
 +/// \param rect 바운딩 박스
 +/// \return ELEMTYPEREAL 부피
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +ELEMTYPEREAL RTREE_QUALIFIER::​CalcRectVolume(Rect* rect)
 +{
 +#ifdef RTREE_USE_SPHERICAL_VOLUME
 +    return RectSphericalVolume(rect);​ // Slower but helps certain merge cases
 +#else // RTREE_USE_SPHERICAL_VOLUME
 +    return RectVolume(rect);​ // Faster but can cause poor merges
 +#endif // RTREE_USE_SPHERICAL_VOLUME  ​
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 가득찬 노드 하나 + 브랜치 하나를 읽어들여 버퍼를 채운다.
 +/// \param node 노드
 +/// \param branch 브랜치
 +/// \param parVars 버퍼
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +void RTREE_QUALIFIER::​GetBranches(Node* node, Branch* branch, PartitionVars* parVars)
 +{
 +    Assert(node);​
 +    Assert(branch);​
 +    Assert(node->​m_count == MAXNODES);
 +
 +    // Load the branch buffer
 +    for (int index=0; index < MAXNODES; ++index)
 +    {
 +        parVars->​m_branchBuf[index] = node->​m_branch[index];​
 +    }
 +    parVars->​m_branchBuf[MAXNODES] = *branch;
 +    parVars->​m_branchCount = MAXNODES + 1;
 +
 +    // Calculate rect containing all in the set
 +    parVars->​m_coverSplit = parVars->​m_branchBuf[0].m_rect;​
 +    for (index=1; index < MAXNODES+1; ++index)
 +    {
 +        parVars->​m_coverSplit = CombineRect(
 +            &​parVars->​m_coverSplit,​ &​parVars->​m_branchBuf[index].m_rect);​
 +    }
 +    parVars->​m_coverSplitArea = CalcRectVolume(&​parVars->​m_coverSplit);​
 +
 +    InitNode(node);​
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 분할을 선택하기 위한 함수
 +///
 +/// As the seeds for the two groups, pick the two rects that would waste the
 +/// most area if covered by a single rectangle, i.e. evidently the worst pair
 +/// to have in the same group.
 +/// Of the remaining, one at a time is chosen to be put in one of the two 
 +/// groups. The one chosen is the one with the greatest difference in area 
 +/// expansion depending on which group - the rect most strongly attracted to
 +/// one group and repelled from the other.
 +/// If one group gets too full (more would force other group to violate min
 +/// fill requirement) then other group gets the rest.
 +/// These last are the ones that can go in either group most easily.
 +/// 
 +/// \param parVars 버퍼
 +/// \param minFill 최소 채우기 값
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +void RTREE_QUALIFIER::​ChoosePartition(PartitionVars* parVars, int minFill)
 +{
 +    Assert(parVars);​
 +
 +    ELEMTYPEREAL biggestDiff;​
 +    int group, chosen, betterGroup;​
 +
 +    InitParVars(parVars,​ parVars->​m_branchCount,​ minFill);
 +    PickSeeds(parVars);​
 +
 +    while (((parVars->​m_count[0] + parVars->​m_count[1]) < parVars->​m_total)
 +        && (parVars->​m_count[0] < (parVars->​m_total - parVars->​m_minFill))
 +        && (parVars->​m_count[1] < (parVars->​m_total - parVars->​m_minFill)))
 +    {
 +        biggestDiff = (ELEMTYPEREAL) -1;
 +        for (int index=0; index<​parVars->​m_total;​ ++index)
 +        {
 +            if (!parVars->​m_taken[index])
 +            {
 +                Rect* curRect = &​parVars->​m_branchBuf[index].m_rect;​
 +                Rect rect0 = CombineRect(curRect,​ &​parVars->​m_cover[0]);​
 +                Rect rect1 = CombineRect(curRect,​ &​parVars->​m_cover[1]);​
 +                ELEMTYPEREAL growth0 = CalcRectVolume(&​rect0) - parVars->​m_area[0];​
 +                ELEMTYPEREAL growth1 = CalcRectVolume(&​rect1) - parVars->​m_area[1];​
 +                ELEMTYPEREAL diff = growth1 - growth0;
 +                if (diff >= 0)
 +                {
 +                    group = 0;
 +                }
 +                else
 +                {
 +                    group = 1;
 +                    diff = -diff;
 +                }
 +
 +                if (diff > biggestDiff)
 +                {
 +                    biggestDiff = diff;
 +                    chosen = index;
 +                    betterGroup = group;
 +                }
 +                else if ((diff == biggestDiff) && (parVars->​m_count[group] < parVars->​m_count[betterGroup]))
 +                {
 +                    chosen = index;
 +                    betterGroup = group;
 +                }
 +            }
 +        }
 +        Classify(chosen,​ betterGroup,​ parVars);
 +    }
 +
 +    // If one group too full, put remaining rects in the other
 +    if ((parVars->​m_count[0] + parVars->​m_count[1]) < parVars->​m_total)
 +    {
 +        if (parVars->​m_count[0] >= parVars->​m_total - parVars->​m_minFill)
 +        {
 +            group = 1;
 +        }
 +        else
 +        {
 +            group = 0;
 +        }
 +        for (int index=0; index<​parVars->​m_total;​ ++index)
 +        {
 +            if (!parVars->​m_taken[index])
 +            {
 +                Classify(index,​ group, parVars);
 +            }
 +        }
 +    }
 +
 +    Assert((parVars->​m_count[0] + parVars->​m_count[1]) == parVars->​m_total);​
 +    Assert((parVars->​m_count[0] >= parVars->​m_minFill) && ​
 +        (parVars->​m_count[1] >= parVars->​m_minFill));​
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 분할에 따라, 브랜드치들을 버퍼에서 복사한다.
 +/// \param nodeA 노드
 +/// \param nodeB 노드
 +/// \param parVars 버퍼
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +void RTREE_QUALIFIER::​LoadNodes(Node* nodeA, Node* nodeB, PartitionVars* parVars)
 +{
 +    Assert(nodeA);​
 +    Assert(nodeB);​
 +    Assert(parVars);​
 +
 +    for (int index=0; index < parVars->​m_total;​ ++index)
 +    {
 +        Assert(parVars->​m_partition[index] == 0 || parVars->​m_partition[index] == 1);
 +
 +        if (parVars->​m_partition[index] == 0)
 +        {
 +            AddBranch(&​parVars->​m_branchBuf[index],​ nodeA, NULL);
 +        }
 +        else if (parVars->​m_partition[index] == 1)
 +        {
 +            AddBranch(&​parVars->​m_branchBuf[index],​ nodeB, NULL);
 +        }
 +    }
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 트리의 분할을 찾을 때 쓰이는 변수 객체를 초기화한다.
 +/// \param parVars 변수 객체
 +/// \param maxRects 사격형의 갯수
 +/// \param minFill 최소 채우기 값
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +void RTREE_QUALIFIER::​InitParVars(PartitionVars* parVars, int maxRects, int minFill)
 +{
 +    Assert(parVars);​
 +
 +    parVars->​m_count[0] = parVars->​m_count[1] = 0;
 +    parVars->​m_area[0] = parVars->​m_area[1] = (ELEMTYPEREAL)0;​
 +    parVars->​m_total = maxRects;
 +    parVars->​m_minFill = minFill;
 +    for (int index=0; index < maxRects; ++index)
 +    {
 +        parVars->​m_taken[index] = false;
 +        parVars->​m_partition[index] = -1;
 +    }
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 트리의 분할을 위한 시드 값을 계산한다.
 +/// \param parVars 트리의 분할을 찾을 때 쓰이는 변수 객체
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +void RTREE_QUALIFIER::​PickSeeds(PartitionVars* parVars)
 +{
 +    int seed0, seed1;
 +    ELEMTYPEREAL worst, waste;
 +    ELEMTYPEREAL area[MAXNODES+1];​
 +
 +    for (int index=0; index<​parVars->​m_total;​ ++index)
 +    {
 +        area[index] = CalcRectVolume(&​parVars->​m_branchBuf[index].m_rect);​
 +    }
 +
 +    worst = -parVars->​m_coverSplitArea - 1;
 +    for (int indexA=0; indexA < parVars->​m_total-1;​ ++indexA)
 +    {
 +        for (int indexB = indexA+1; indexB < parVars->​m_total;​ ++indexB)
 +        {
 +            Rect oneRect = CombineRect(&​parVars->​m_branchBuf[indexA].m_rect,​ &​parVars->​m_branchBuf[indexB].m_rect);​
 +            waste = CalcRectVolume(&​oneRect) - area[indexA] - area[indexB];​
 +            if (waste > worst)
 +            {
 +                worst = waste;
 +                seed0 = indexA;
 +                seed1 = indexB;
 +            }
 +        }
 +    }
 +
 +    Classify(seed0,​ 0, parVars);
 +    Classify(seed1,​ 1, parVars);
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 브랜치를 그룹별로 구분한다.
 +/// \param index 브랜치의 인덱스
 +/// \param group 그룹 인덱스
 +/// \param parVars 트리의 분할을 찾을 때 쓰이는 변수 객체
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +void RTREE_QUALIFIER::​Classify(int index, int group, PartitionVars* parVars)
 +{
 +    Assert(parVars);​
 +    Assert(!parVars->​m_taken[index]);​
 +
 +    parVars->​m_partition[index] = group;
 +    parVars->​m_taken[index] = true;
 +
 +    if (parVars->​m_count[group] == 0)
 +    {
 +        parVars->​m_cover[group] = parVars->​m_branchBuf[index].m_rect;​
 +    }
 +    else
 +    {
 +        parVars->​m_cover[group] = CombineRect(&​parVars->​m_branchBuf[index].m_rect,​ &​parVars->​m_cover[group]);​
 +    }
 +    parVars->​m_area[group] = CalcRectVolume(&​parVars->​m_cover[group]);​
 +    ++parVars->​m_count[group];​
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 바운딩 박스를 삭제한다.
 +/// \param rect 제거할 바운딩 박스
 +/// \param id 제거할 유저 데이터
 +/// \param root 루트 노드
 +/// \return bool 성공적으로 삭제한 경우에는 0을 반환하고,​ 해당 데이터를 찾지
 +/// 못한 경우에는 1을 반환한다.
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +bool RTREE_QUALIFIER::​RemoveRect(Rect* rect, const DATATYPE&​ id, Node** root)
 +{
 +    Assert(rect && root);
 +    Assert(*root);​
 +
 +    Node* tempNode;
 +    ListNode* reInsertList = NULL;
 +
 +    if (!RemoveRectRec(rect,​ id, *root, &​reInsertList))
 +    {
 +        // Found and deleted a data item
 +        // Reinsert any branches from eliminated nodes
 +        while(reInsertList)
 +        {
 +            tempNode = reInsertList->​m_node;​
 +
 +            for (int index = 0; index < tempNode->​m_count;​ ++index)
 +            {
 +                InsertRect(&​(tempNode->​m_branch[index].m_rect),​
 +                    tempNode->​m_branch[index].m_data,​
 +                    root,
 +                    tempNode->​m_level);​
 +            }
 +
 +            ListNode* remLNode = reInsertList;​
 +            reInsertList = reInsertList->​m_next;​
 +
 +            FreeNode(remLNode->​m_node);​
 +            FreeListNode(remLNode);​
 +        }
 +
 +        // Check for redundant root (not leaf, 1 child) and eliminate
 +        if ((*root)->​m_count == 1 && (*root)->​IsInternalNode())
 +        {
 +            tempNode = (*root)->​m_branch[0].m_child;​
 +
 +            Assert(tempNode);​
 +            FreeNode(*root);​
 +            *root = tempNode;
 +        }
 +        return false;
 +    }
 +    else
 +    {
 +        return true;
 +    }
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 루트가 아닌 다른 노드에서 바운딩 박스를 삭제한다.
 +///
 +/// RemoveRect 함수에서 호출한다. 트리를 따라내려가며,​ 노드를 합쳐야하는
 +/// 경우에는 합친다.
 +///
 +/// \param rect 제거할 바운딩 박스
 +/// \param id 제거할 유저 데이터
 +/// \param node 부모 노드
 +/// \param listNode 재삽입 리스트 객체
 +/// \return bool 성공적으로 삭제한 경우에는 0을 반환하고,​ 해당 데이터를 찾지
 +/// 못한 경우에는 1을 반환한다.
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +bool RTREE_QUALIFIER::​RemoveRectRec(Rect* rect, const DATATYPE&​ id, Node* node, ListNode** listNode)
 +{
 +    Assert(rect && node && listNode);
 +    Assert(node->​m_level >= 0);
 +
 +    if (node->​IsInternalNode()) ​ // not a leaf node
 +    {
 +        for (int index = 0; index < node->​m_count;​ ++index)
 +        {
 +            if (Overlap(rect,​ &​(node->​m_branch[index].m_rect)))
 +            {
 +                if (!RemoveRectRec(rect,​ id, node->​m_branch[index].m_child,​ listNode))
 +                {
 +                    if (node->​m_branch[index].m_child->​m_count >= MINNODES)
 +                    {
 +                        // child removed, just resize parent rect
 +                        node->​m_branch[index].m_rect = NodeCover(node->​m_branch[index].m_child);​
 +                    }
 +                    else
 +                    {
 +                        // child removed, not enough entries in node, eliminate node
 +                        ReInsert(node->​m_branch[index].m_child,​ listNode);
 +                        DisconnectBranch(node,​ index); // Must return after this call as count has changed
 +                    }
 +                    return false;
 +                }
 +            }
 +        }
 +        return true;
 +    }
 +    else // A leaf node
 +    {
 +        for (int index = 0; index < node->​m_count;​ ++index)
 +        {
 +            if (node->​m_branch[index].m_child == (Node*)id)
 +            {
 +                DisconnectBranch(node,​ index); // Must return after this call as count has changed
 +                return false;
 +            }
 +        }
 +        return true;
 +    }
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 두 바운딩 박스가 겹치는지의 여부를 반환한다.
 +/// \param rectA 바운딩 박스
 +/// \param rectB 바운딩 박스
 +/// \return bool 겹치는 경우 true, 겹치지 않는 경우 false
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +bool RTREE_QUALIFIER::​Overlap(Rect* rectA, Rect* rectB) const
 +{
 +    Assert(rectA && rectB);
 +
 +    for (int index=0; index < NUMDIMS; ++index)
 +    {
 +        if (rectA->​m_min[index] > rectB->​m_max[index] ||
 +            rectB->​m_min[index] > rectA->​m_max[index])
 +        {
 +            return false;
 +        }
 +    }
 +    return true;
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 노드를 재삽입 리스트에다 추가한다. 해당 노드와 브랜치들은 나중에
 +/// 트리에 새로이 추가한다.
 +/// \param node 노드
 +/// \param listNode 리스트 객체
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +void RTREE_QUALIFIER::​ReInsert(Node* node, ListNode** listNode)
 +{
 +    ListNode* newListNode = AllocListNode();​
 +    newListNode->​m_node = node;
 +    newListNode->​m_next = *listNode;
 +    *listNode = newListNode;​
 +}
 +
 +
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \brief 실제 검색 함수
 +/// \param node 검색할 노드
 +/// \param rect 바운딩 박스
 +/// \param foundCount 찾은 데이터의 갯수
 +/// \param results 찾은 데이터를 집어넣을 컬렉션
 +/// \return bool 상위 함수에서 검색을 계속해야하는 경우에는 true, 검색을
 +/// 중단해야하는 경우에는 false.
 +//////////////////////////////////////////////////////////////////////////////​
 +RTREE_TEMPLATE
 +bool RTREE_QUALIFIER::​Search(Node* node, Rect* rect, int& foundCount, RESULTS&​ results)
 +{
 +    Assert(node);​
 +    Assert(node->​m_level >= 0);
 +    Assert(rect);​
 +
 +    if (node->​IsInternalNode()) // This is an internal node in the tree
 +    {
 +        for (int index=0; index < node->​m_count;​ ++index)
 +        {
 +            if (Overlap(rect,​ &​node->​m_branch[index].m_rect))
 +            {
 +                if (!Search(node->​m_branch[index].m_child,​ rect, foundCount, results))
 +                {
 +                    return false; // Don't continue searching
 +                }
 +            }
 +        }
 +    }
 +    else // This is a leaf node
 +    {
 +        for (int index=0; index < node->​m_count;​ ++index)
 +        {
 +            if (Overlap(rect,​ &​node->​m_branch[index].m_rect))
 +            {
 +                ++foundCount;​
 +                results.push_back(node->​m_branch[index].m_data);​
 +            }
 +        }
 +    }
 +
 +    return true; // Continue searching
 +}
 +
 +#undef RTREE_TEMPLATE
 +#undef RTREE_QUALIFIER
 +
 +#endif
 +</​file>​
 +
 +
 +====== 링크 ======
 +  * [[http://​www.dbnet.ece.ntua.gr/​~mario/​rtree/​ | RTree Visualization Demo]]
 +  * [[http://​www.rtreeportal.org/​ | The R-TREE Portal]]
 +  * [[http://​www.utdallas.edu/​~lkhan/​Summer2001/​Lecture11.ppt | Spatial Index Structures (PPT)]]
 +
 +  * [[http://​www.volny.cz/​r-tree/​ | Mg R-tree Library]]
 +  * [[http://​www.cs.ucr.edu/​~marioh/​spatialindex/​ | Spatial Index Library]]
 +  * [[http://​eprints.ecs.soton.ac.uk/​841/​04/​html/​index.html | Fast k nearest neighbour search for R-tree family]]
 +  * [[http://​gist.cs.berkeley.edu/​libgist-2.0/​ | libgist v.2.0/amdb v.1.0]]
 +  * [[http://​www.superliminal.com/​sources/​sources.htm]]
  
kb/rtree.txt · 마지막으로 수정됨: 2014/11/09 20:02 (바깥 편집)