• 大小: 4KB
    文件类型: .rar
    金币: 1
    下载: 0 次
    发布日期: 2021-06-16
  • 语言: 其他
  • 标签: KD-Tree  

资源简介

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


评论

共有 条评论