Data structures for efficient manipulation of geometric data

Podatke koji sadrže informacije o geometriji, poput koordinata točka, dužina, poligona i slično, možemo u računalu pohraniti na više načina. U ovom radu proučavali smo strukture podataka koje nam, uz kompaktno pohranjivanje odgovarajućih geometrijskih objekata, omogućavaju efikasno izvod¯enje raznih upita nad pohranjenim skupom. Jedna od takvih struktura je kd-stablo, odnosno binarno stablo čiji listovi reprezentiraju k-dimenzionalne točke. To je struktura čiji unutarnji čvor dijeli zadani skup točaka na dva podskupa približno jednake veličine te spomenute podskupove pohranjuje u djecu čvora sve dok skup ne sadrži samo jednu točku. Proučavali smo pohranjivanje 2-dimenzionalnih točaka te pretraživanje kd-stabla, odnosno kako možemo za zadani 2-dimenzionalni interval efikasno pronaći sve točke koje pripadaju spomenutom intervalu. Druga struktura koju smo istraživali u radu je quadtree. To je struktura slična kd-stablu, no svaki njen unutarnji čvor ima točno četiri djeteta. Takod¯er, svaki čvor predstavlja kvadrat, te su kvadrati djece zapravo particionirani roditeljski kvadrat na četiri dijela, stoga quadtree ima veliku primjenu u pohranjivanju geometrijskih podataka. Skup početnih geometrijskih podataka (točaka, bridova, ...) može biti nepovoljan, odnosno dva susjedna kvadrata mogu imati značajne razlike u veličini stranice kvadrata. To neželjeno svojstvo riješili smo balansiranjem quadtree-a. U balansiranom quadtree-u, duljine dužina stranica susjednih kvadrata razlikuju se najviše za faktor 2, odnosno svaka dva susjedna čvora razlikuju se najviše za jedan u dubini. Balansirani quadtree koristili smo u generiranju triangulacija, odnosno podjeli geometrijskog prostora na trokute. Kreirali smo triangulaciju na dvodimenzionalnim poligonima čija je mreža trokuta gušća oko poligona, a rijed¯a udaljavanjem od njih. Triangulaciju smo generirali podjelom kvadrata balansiranog quadtree-a na trokute uzevši u obzir blizinu zadanih poligona. Svu implementaciju spomenutih struktura podataka i pripadnih algoritama, napisali smo u programskom jeziku C++.Data which contains information about geometry, such as coordinates of points, line segments, polygons and others, can be stored in a computer in several ways. In this thesis, we studied data structures that, along with the compact storage of appropriate geometric objects, enable us to efficiently perform various queries over the stored set. One of the structures with mentioned properties is kd-tree which is a binary tree which contains leaves that represent k-dimensional points. It is a structure whose internal node divides a given set of points into two subsets of approximately equal sizes. Those subsets are stored as left and right child of the node which performs the division. Set of points is divided as long as it contains more than one point. We studied storing 2-dimensional points and kd-tree search, that is, how can we efficiently find all points that belong to the given 2-dimensional interval. Second structure that we studied was quadtree. Quadtree is a structure similar to a kdtree, but each of its internal nodes has exactly four children. Also, each node represents a square and the children’s squares are actually partitioned parent square in four parts, so the quadtree has great application in storing geometric data. A set of initial geometric data (points, edges, ...) can be unfavorable. For example, two adjacent squares can have significant differences in their size. We solved this unwanted feature by balancing the quadtree. In a balanced quadtree, the lengths of the line segment representing one side of the adjacent squares differ at the most by factor 2, that is, every two adjacent nodes differ by at most one in depth. We used balanced quadtree to compute triangular mesh, that is, we divided geometric space into triangles. We performed computation on two-dimensional polygons and the constructed mesh was fine near the edges of the polygons and coarse further away from them. Mesh was generated by square triangulation of the nodes in the balanced quadtree. Implementation of the mentioned data structures and algorithms was done using C++ programming language