R-TREES: A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING

N 차원의 공간에서 N 차원의 사각형(엄밀히 말하자면 2차원에서나 사각형이지만, 딱히 따로 부르기 귀찮다.)을 빠르게 찾기 위한 자료 구조다. 이 자료구조를 이용하면 아래와 같은 쿼리를 효과적으로 처리할 수 있다.

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

노드의 삽입/삭제에는 그리 효과적인 자료구조가 아니므로, 동적인 자료 구조를 처리하는 데에는 맞지 않다. 게임에서는 정적인 맵 정보를 구성하는 데 사용할 수 있을 듯 하다.

http://www.superliminal.com/sources/sources.htm 에서 다운로드받아 약간의 수정을 가한 C++ 소스이다.

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

• RTree Visualization Demo
• The R-TREE Portal
• Spatial Index Structures (PPT)

• Mg R-tree Library
• Spatial Index Library
• Fast k nearest neighbour search for R-tree family
• libgist v.2.0/amdb v.1.0
• http://www.superliminal.com/sources/sources.htm