1 개요

어떤 점에 가장 가까운 사각형은 어느 것인가?
어떤 점을 포함하는 사각형은 어느 어느 것인가?
어떤 사각형과 겹치는 사각형은 어느 어느 것인가?
어떤 사각형을 포함하는 사각형은 어느 어느 것인가?
2 C++ Implementation

http://www.superliminal.com/sources/sources.htm
//////////////////////////////////////////////////////////////////////////////
/// \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)
{