Efficient Data Search Organized in Tree

Računalni vid i ostale grane računarske znanosti često se bave obradom podataka o velikom broju točaka. Javlja se potreba za učinkovitom organizacijom točkovnih podataka koja bi omogućila njihovo brže pretraživanje. Strukture podataka razvijene u tu svrhu uglavnom imaju hijerarhijsku organizaciju u obliku stabla. Od poznatijih takvih struktura vrijedi izdvojiti BSP stablo, \emph{k}-d stablo , quadtree i octree. Sve su zasnovane na principu podjele prostora u kojem se nalazi promatrani skup točaka na podregije te pridruživanju točaka pripadnim podregijama. Jedan od važnijih problema u kojem se spomenute strukture koriste je pretraživanje najbližeg susjeda, koje se bavi pronalaskom točke iz predodređenog skupa koja je najbliža određenoj točki. Uz korištenje vlastitih programskog ostvarenja struktura \emph{k}-d stablo i octree pokazuje se da hijerarhijska organizacija točkovnih podataka znatno poboljšava izvedbu pretraživanja najbližeg susjeda.Computer vision, along with other branches of computer science, often deals with processing point data, which causes a need for efficient organization of points which would allow faster searching. Data structures developed for this purpose commonly have a hierarchical organization in shape of a tree. BSP tree, \emph{k}-d tree, quadtree and octree are among the well-known such structures. They are all based on the principle of recursive subdivision of point space and placing points into correspondent regions. Nearest neighbour search is one of the notable problems which uses mentioned structures. The problem deals with finding a point in a predetermined set which is nearest to the given query point. It is determined, using self-implemented \emph{k}-d tree and octree, that hierarchical organization significantly improves nearest neighbour search