资源简介
KD-Tree是一种由二叉搜索树推广而来的用于多维检索的树的结构形式(K即为空间的维数)。它与二叉搜索树不同的是它的每个结点表示k维空间的一个点,并且每一层都根据该层的分辨器(discriminator)对相应对象做出分枝决策。顶层结点按由分辨器决定的一个维度进行划分,第二层则按照该层的分辨器决定的一个维进行划分···,以此类推在余下各维之间不断地划分。直至一个结点中的点数少于给定的最大点数时,结束划分。
KD-Tree的分辨器根据不同的用途会有不同的分辨器,最普通的分辨器为:n mod k(树的根节点所在层为第0层,根结点孩子所在层为第1层,以此类推) 即:若它的左子树非空,则其左子树上所有结点的第i维值均小于其根结点的第i维值;
若它的右子树非空,则其右子树上所有结点的第i维值均大于其根结点的第i维值;并且它的左右子树也分别为KD-Tree。
代码片段和文件信息
/**************************
* Includes
*
**************************/
#include “kdtree.h“
#include
#include
#include
float theta = 0.0;
/**************************
* Function Declarations
*
**************************/
LRESULT CALLBACK WndProc (HWND hWnd UINT message
WPARAM wParam LPARAM lParam);
void EnableOpenGL (HWND hWnd HDC *hDC HGLRC *hRC);
void DisableOpenGL (HWND hWnd HDC hDC HGLRC hRC);
double rand01(void)
{
double num = double(rand())/double(RAND_MAX);
return num;
}
/**************************
* WinMain
*
**************************/
int WINAPI WinMain (HINSTANCE hInstance
HINSTANCE hPrevInstance
LPSTR lpCmdLine
int iCmdShow)
{
WNDCLASS wc;
HWND hWnd;
HDC hDC;
HGLRC hRC;
MSG msg;
BOOL bQuit = FALSE;
float theta = 0.0f;
/* register window class */
wc.style = CS_OWNDC;
wc.lpfnWndProc = WndProc;
wc.cbClsExtra = 0;
wc.cbWndExtra = 0;
wc.hInstance = hInstance;
wc.hIcon = LoadIcon (NULL IDI_APPLICATION);
wc.hCursor = LoadCursor (NULL IDC_ARROW);
wc.hbrBackground = (HBRUSH) GetStockobject (BLACK_BRUSH);
wc.lpszMenuName = NULL;
wc.lpszClassName = “GLSample“;
RegisterClass (&wc);
/* create main window */
hWnd = CreateWindow (
“GLSample“ “Kd-tree demo“
WS_CAPTION | WS_POPUPWINDOW | WS_VISIBLE
0 0 556 556
NULL NULL hInstance NULL);
/* enable OpenGL for the window */
EnableOpenGL (hWnd &hDC &hRC);
vector P;
for (int ctr = 0; ctr < 10000; ctr++)
P.push_back(Point(rand01()*2-1 rand01()*2-1));
Kdtree kdtree(P);
/* program main loop */
while (!bQuit)
{
/* check for messages */
if (PeekMessage (&msg NULL 0 0 PM_REMOVE))
{
/* handle or dispatch messages */
if (msg.message == WM_QUIT)
{
bQuit = TRUE;
}
else
{
TranslateMessage (&msg);
DispatchMessage (&msg);
}
}
else
{
/* OpenGL animation code goes here */
glClearColor (0.0f 0.0f 0.0f 0.0f);
glClear (GL_COLOR_BUFFER_BIT);
theta+=.05;
float circlex = cos(theta)/2.0 circley = sin(theta)/2.0;
vector selected =
kdtree.searchtree(circlex-0.5 circley-0.5 circlex+0.5 circley+0.5);
vector::iterator i = selected.begin();
glBegin (GL_POINTS);
while (i != selected.end())
{
Point &p = *i++;
glVertex3f(p.x p.y 0);
}
glEnd ();
SwapBuffers (hDC);
Sleep (1);
}
}
/* shutd
属性 大小 日期 时间 名称
----------- --------- ---------- ----- ----
文件 589 2005-08-30 03:20 @PSC_ReadMe_9767_3.txt
文件 7911 2005-08-30 01:21 kdtree.h
文件 4825 2005-08-29 12:40 oglkd.cpp
----------- --------- ---------- ----- ----
13325 3
- 上一篇:STEP7 编程软件的使用方法
- 下一篇:ajax带多个参数上传图片
评论
共有 条评论