사용자 도구

사이트 도구


kb:kdtree

차이

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

차이 보기로 링크

kb:kdtree [2014/11/08 15:14] (현재)
줄 1: 줄 1:
 +====== KD Tree ======
 +N 차원의 공간에서 임의의 영역에 포함되는 점들을 효율적으로 찾기 위한 트리.
 +
 +노드 추가와 검색은 상당히 빠르나, 삭제가 느리다. 즉 동적으로 움직이는 점들을 관리하는 데에는 적당하지 않다.
 +
 +
 +====== 샘플 ======
 +헤더 파일은 알아서...
 +
 +<code cpp>
 +//////////////////////////////////////////////////////////////////////////////​
 +/// \class KdTree
 +/// \brief N 차원의 공간에서 임의의 영역에 포함되는 점들을 효율적으로 찾기 ​
 +/// 위한 트리 자료 구조
 +///
 +/// T         : 좌표를 나타내는 데 사용할 데이터의 타입 (e.g : int, float...)
 +/// DIMENSION : 차원의 수. 최소 1보다는 커야한다.
 +//////////////////////////////////////////////////////////////////////////////​
 +
 +template <class T, int DIMENSION>​
 +class KdTree
 +{
 +private:
 +    /// 내부적으로 사용하는 노드
 +    struct NODE
 +    {
 +        T     ​data[DIMENSION];​ ///< 실제 좌표
 +        NODE* left;            ///< 좌측 자식
 +        NODE* right; ​          ///<​ 우측 자식
 +
 +        ​
 +        /// \brief 생성자
 +        /// \param value[DIMENSION] ​
 +        NODE(const T value[DIMENSION]) ​
 +            : left(NULL), right(NULL) ​
 +        {
 +            memcpy(data,​ value, sizeof(T) * DIMENSION);
 +        }
 +
 +        /// \brief 소멸자
 +        ~NODE()
 +        {
 +            SAFE_DELETE(left);​
 +            SAFE_DELETE(right);​
 +        }
 +    };
 +
 +    NODE* m_pRoot; ///< 루트 노드
 +
 +
 +public:
 +    /// \brief 생성자
 +    KdTree() : m_pRoot(NULL) {}
 +
 +    /// \brief 소멸자
 +    virtual ~KdTree() { SAFE_DELETE(m_pRoot);​ }
 +
 +
 +public:
 +    /// \brief 좌표값을 트리에다 집어넣는다.
 +    /// \param value[DIMENSION] 좌표값
 +    void insert(const T value[DIMENSION]) ​
 +    { 
 +        insert(value,​ m_pRoot, 0);
 +    }
 +
 +    /// \brief 특정 범위 안에 들어오는 점들을 출력한다.
 +    /// \param low[DIMENSION] 범위 최소값
 +    /// \param high[DIMENSION] 범위 최대값
 +    /// \return int 비교 연산의 횟수
 +    int search(const T low[DIMENSION],​ const T high[DIMENSION])
 +    {
 +        return search(low, high, m_pRoot, 0);
 +    }
 +
 +
 +private:
 +    /// \brief 좌표값을 트리에다 집어넣기 위해 내부적으로 사용하는 함수
 +    /// \param value[DIMENSION] 좌표값
 +    /// \param pParent 부모 노드
 +    /// \param level 비교할 축 인덱스
 +    void insert(const T value[DIMENSION],​ NODE*& pParent, int level)
 +    {
 +        if (pParent == NULL)
 +        {
 +            pParent = new NODE(value);​
 +        }
 +        else if (value[level] < pParent->​data[level])
 +        {
 +            insert(value,​ pParent->​left,​ (level + 1) % DIMENSION);
 +        }
 +        else
 +        {
 +            insert(value,​ pParent->​right,​ (level + 1) % DIMENSION);
 +        }
 +    }
 +
 +    /// \brief 특정 범위 안에 들어오는 점들을 출력하기 위해 내부적으로 ​
 +    /// 사용하는 함수
 +    /// \param low[DIMENSION] 범위 최소값
 +    /// \param high[DIMENSION] 범위 최대값
 +    /// \param pParent 부모 노드
 +    /// \param level 비교할 축 인덱스
 +    /// \return int 비교 연산의 횟수
 +    int search(const T low[DIMENSION],​ const T high[DIMENSION],​ NODE* pParent, int level)
 +    {
 +        if (pParent == NULL) return 0;
 +
 +        int comparison = 1;
 +
 +        bool bSuitable = true;
 +        for (int i=0; i<​DIMENSION;​ ++i)
 +        {
 +            if (pParent->​data[i] < low[i] || high[i] < pParent->​data[i])
 +            {
 +                bSuitable = false;
 +                break;
 +            }
 +        }
 +
 +        if (bSuitable)
 +        {
 +            cout << "​(";​
 +
 +            for (int i=0; i<​DIMENSION;​ ++i)
 +            {
 +                cout << pParent->​data[i];​
 +                if (i != DIMENSION - 1) cout << ",";​
 +            }
 +
 +            cout << "​)"​ << endl;
 +        }
 +
 +        if (low[level] <= pParent->​data[level])
 +            comparison += search(low, high, pParent->​left,​ (level + 1) % DIMENSION);
 +
 +        if (pParent->​data[level] <= high[level])
 +            comparison += search(low, high, pParent->​right,​ (level + 1) % DIMENSION);
 +
 +        return comparison;
 +    }
 +};
 +</​code>​
 +
 +<code cpp>
 +void test( )
 +{
 +    KdTree<​int,​ 3> t;
 +
 +    for( int i = 0; i < 1000; i++ )
 +    {
 +        int it[3] = { i, i, i };
 +        t.insert(it);​
 +    }
 +
 +    int low[3] = { 10, 10, 10 };
 +    int high[3] = { 15, 15, 15 };
 +
 +    cout << "​============================="​ << endl;
 +    int total = t.search(low,​ high);
 +
 +    cout << "​============================="​ << endl;
 +    cout << "Total comparison: " << total << endl;
 +
 +}
 +</​code>​
 +
 +====== 링크 ======
 +  * [[http://​www.rolemaker.dk/​nonRoleMaker/​uni/​algogem/​kdtree.htm | KD Tree Demo]]
 +  * [[http://​www.secretrobot.com/​Articles/​KDTrees.html | Devon Strawn : Quick KD-Tree Tutorial]]
 +  * [[http://​www.codeproject.com/​cpp/​KDTree.asp | KD Tree - Searching in N-dimensions,​ Part I]]
 +
 +
  
kb/kdtree.txt · 마지막으로 수정됨: 2014/11/08 15:14 (바깥 편집)