AHD: alternate hierarchical decomposition : towards LoD based dimension independent geometric modeling

Abstract

The thesis shows that the separation of metric and topological processing for GIS geometry is possible and opens the doors for better geometric data structures. The separation leads to the novel combination of homogeneous coordinates with big integers and convex polytopes.<br />Firstly, the research shows that a consistent metric processing for geometry of straight lines is possible with homogeneous coordinates stored as arbitrary precision integers (so called big integers). Secondly, the geometric model called Alternate Hierarchical Decomposition (AHD), is proposed that is based on the convex decomposition of arbitrary (with or without holes) regions into their convex components. The convex components are stored in a hierarchical tree data structure, called convex hull tree (CHT), each node of which contains a convex hull. A region is then composed by alternately subtracting and adding children convex hulls in lower levels from the convex hull at the current parent node. The solution fulfills following requirements:<br />Provides robustness in geometric computations by using arbitrary precision big integers.<br />Supports fast Boolean operations like intersection, union and symmetric difference etc.<br />Supports level of detail based processing.<br />Supports dimension independence, i.e. AHD is extendable to n-dimensions (n >1).<br />The solution is tested with three real datasets having large number of points. The tests confirm the expected results and show that the performance of AHD operations is acceptable. The complexity of AHD based Boolean operation is near optimal with the advantage that all operations consume and produce the same CHT data structure.