Using quad tree as data storage for a terrain representation and a core for a path finding algorithm

• Autorzy: Waresiak B. , Skrzyński P.

Warianty tytułu

PL

Zastosowanie drzewa czwórkowego do reprezentacji terenu w świecie 3D oraz poszukiwania drogi

• Języki publikacji: EN

Abstrakty

EN

This paper presents the concept of using single quad tree data structure for data storage for terrain representation and simultaneously a core for a path-finding algorithm. The simulated world is an artificially created two-dimensional world that consists of an island surrounded by water, which is considered to be an impassable terrain. Furthermore, the path-find operation is a possible route for a ship that has to avoid the island. The application of the quad tree data structure for Level of Detail implementation in 3D rendering is also discussed. Implementation details are presented together with initial results. Further research paths are presented in the conclusion.

PL

W artykule zaprezentowana została koncepcja wykorzystania pojedynczego drzewa czwórkowego do reprezentacji terenu oraz poszukiwania optymalnej ścieżki. Zaprezentowane zostało drzewo stworzone dla przykładowego świata, który składa się z wyspy otoczonej wodą, przy czym poruszanie się jest możliwe tylko po wodzie. Ponadto przedyskutowano możliwości zastosowania tego typu struktury do implementacji Level of Detail podczas renderowania kształtów 3D. Poza prezentacją wykorzystywanych w implementacji struktur oraz algorytmów przedstawione są wstępne wyniki oraz zarysowano dalsze kierunki badań.

Słowa kluczowe

EN

quadtree; path finding; terrain representation; graph search; level of detail; A* algorithm

PL

drzewo czwórkowe; poszukiwanie ścieżki; reprezentacja świata; przeszukiwanie grafów; algorytm A*

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2011
• Tom: T. 15, z. 3
• Strony: 681--691
• Opis fizyczny: Bibliogr. 9 poz., rys.

Twórcy

autor

Waresiak B.

• AGH University of Science and Technology, Faculty of Electrical Engineering, Automatics, Computer Science and Electronic, Department of Electronics, al. A. Mickiewicza 30, 30-059 Krakow, Poland

autor

Skrzyński P.

• AGH University of Science and Technology, Faculty of Electrical Engineering, Automatics, Computer Science and Electronic, Department of Electronics, al. A. Mickiewicza 30, 30-059 Krakow, Poland

Bibliografia

• [1] Chen D., Szczerba R., Uhran J., Schnabl H., Planning Conditional Shortest Paths Through an Unknown Environment: A Framed-Quadtree. IEEE, 1995.
• [2] Finkel R.A., Bentley J.L., Quad Trees -A Data StructureforRetrieval on Composite Keys. Acta Informatica 4, Springer-Verlag, 1974, 1-9.
• [3] Gabriani G., Mulkar T., Szuba T., A quad-tree based algorithm for processor allocation in 2D mesh-connected multicomputers. Computer Standards and Interfaces, vol. 27, 2005, 133-147.
• [4] Hart R, A Formal Basis for the Heuristic Determination. IEEE Transactions of Systems Science and Cybernetics, vol. SSC-4, No. 2, July 1968.
• [5] Kambhampati S., Davis L., Multiresolution Path Planning for Mobile Robots. IEEE Journal of Robotics and Automation, vol. RA-2, No. 3, September 1986, 135-145.
• [6] Luo Z. Li Z., Zhong B., Modeling of Earth s Gravity Fields Yisualization Based on Quad Tree. Geospatial Information Science, vol. 13, issue 3, September 2010, 216-220.
• [7] Samal A., Bhatia S., Vadlamani R, Mant D., Searching satellite imagery with integrated measures. Pattern Recognition, vol. 42, 2009, 2502-2513.
• [8] Sun M., A primogenitary linked ąuad tree data structure and its application to discrete multiple criteria optimization. Ann Oper Res, vol. 147, 2006, 87-107.
• [9] Trotts I., Mikula S., Jones E.G., Interactive visualization of multiresolution image stacks in 3D. Neuroimage, vol. 35, 2007, 1038-1043.