KD-Tree 예제

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

kd_tree.h 다운로드

이 코드의 문제점은..
1. insert 속도가 너무 느리다
2. 밸런싱 기능이 없다
3. 삭제 기능이 없다

#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;
}

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다


This site uses Akismet to reduce spam. Learn how your comment data is processed.