KD-Tree 예제

공간 검색에 탁월하다는 KD-Tree 알고리즘..
http://blog.daum.net/pg365/140 이 사이트에 간단하게 구현해 놓은 코드가 있어 테스트해 봄.

kd_tree.zip

0.00MB

 

이 코드의 문제점은..

• insert 속도가 너무 느리다
• 밸런싱 기능이 없다
• 삭제 기능이 없다

#include <stdio.h>
#include <assert.h>
#include <time.h>
#include <windows.h>
#include "kd_tree.h"
 
unsigned int get_msec(void)
{
    return GetTickCount ();
}
 
class KDTree : public kd_tree<double, 3>
{
public:
    void insert_xyz (double x, double y, double z, void *data)
    {
        double buf[3] = { x, y, z };
         
        insert (buf, data);
    }
 
    kd_node *nearest_neighbour_search (double x, double y, double z)
    {
        double pos[3] = {x, y, z};
         
        return nn_search (pos);
    }
 
    list<kd_node *> *bounding_box_search (double lx, double ly, double lz, double hx, double hy, double hz)
    {
        double low[3]  = { lx, ly, lz };
        double high[3] = { hx, hy, hz };
 
        return range_search (low, high);
    }
};
 
 
int main(int argc, char **argv)
{
    KDTree kd;
 
    unsigned int start = get_msec();
 
    int point_id = 0;
 
    printf("-- insert points ... \n"); fflush(stdout);
 
    for(int i=0; i<1000; i++) {
 
        for (int x=0; x < 10; x++) {
            for (int y=0; y < 10; y++) {
                for (int z=0; z < 10; z++) {
                    kd.insert_xyz (x, y, z, (void *)point_id);
                    point_id++;
                }
            }
        }
 
        for (int x=20; x < 30; x++) {
            for (int y=20; y < 30; y++) {
                for (int z=0; z < 10; z++) {
                    kd.insert_xyz (x, y, z, (void *)point_id);
                    point_id++;
                }
            }
        }
 
        for (int x=0; x < 10; x++) {
            for (int y=20; y < 30; y++) {
                for (int z=0; z < 10; z++) {
                    kd.insert_xyz (x, y, z, (void *)point_id);
                    point_id++;
                }
            }
        }
 
        for (int x=20; x < 30; x++) {
            for (int y=0; y < 10; y++) {
                for (int z=0; z < 10; z++) {
                    kd.insert_xyz (x, y, z, (void *)point_id);
                    point_id++;
                }
            }
        }
    }
 
    unsigned int msec = get_msec() - start;
    printf("inserting %d points... %.3f sec\n", point_id, msec/1000.0);
 
    start = get_msec();
 
    list<kd_tree<double,3>::kd_node *> *ret = kd.bounding_box_search(0, 0, 0, 10, 10, 10);
#if 1
    for (list<kd_tree<double,3>::kd_node *>::iterator it = ret->begin (); it != ret->end(); it++) {
        kd_tree<double,3>::kd_node *n = *it;
        printf ("(%g, %g, %g) \n", n->_pos[0], n->_pos[1], n->_pos[2]);
    }
#endif
 
    msec = get_msec() - start;
    printf("range query returned %d items in %.5f sec\n", ret->size(), msec/1000.0);
    return 0;
}

결론은.. github에 꽤 좋은 kd-tree 라이브러리를 쓰기로...

https://github.com/jlblancoc/nanoflann