An international conference connecting people
in CAD research, education and business
Bookmark and Share
Copyright (C) CAD Solutions, LLC. All rights reserved.
Proceedings of CAD'14, 2014, 212-214
Investigations on Different Geometric Elements for Quadtree-based Scanning of 2-D Spaces

Karthik Vijayakumar, National Institute of Technology, Tiruchirappalli
Saravana Kumar, G, Indian Institute of Technology, Madras
Sandipan Badyopadhyay, Indian Institute of Technology, Madras

Abstract. Quadtrees are hierarchical data structures which are based on the principle of recursive sub-division of space. Quadtrees date back to 1970s [3], and since then they have been used heavily for representation of spatial data. One of the prime motivations of using hierarchical quadtrees over other techniques is to save memory space, as well as to improve the computational efficiency of computational procedures. Different geometric elements have been used to decompose space in terms of quadtrees, such as rectangles, triangles, and their higher-dimensional counterparts. The computational complexity in triangular sub-division is the same as in rectangles, but the triangular subdivision may perform better for capturing the boundaries of certain regions, since scanning in triangles takes place for every 60˚ compared to the 90˚ in the case of squares or rectangles. This paper proposes a novel decomposition technique for quadtrees in the form of circular segments for representation of 2D data. Rectangular, triangular, and the newly suggested circular subdivision techniques were tested to detect the traces of implicitly defined planar curves. This has immense utilities in the domain of mechanism design and analysis, among others. 

Keywords. Quadtrees, rectangular, triangular, circular, computational efficiency

DOI: 10.14733/cadconfP.2014.212-214