Research Group Geoinformation

Home | Research | Publications | Download | Projects | Teaching | Staff

... to the Cartography Group

Bulbul Rizwan

AHD: Alternate Hierarchical Decomposition Towards LoD Based Dimension Independent Geometric Modeling

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. 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 ful fills following requirements:
  •  Provides robustness in geometric computations by using arbitrary precision
big integers.
  •  Supports fast Boolean operations like intersection, union and symmetric
di erence etc. Supports level of detail based processing.
  •  Supports dimension independence, i.e. AHD is extendable to n-dimensions
(n  2).
The solution is tested with three real datasets having large number of points.
The tests confirms 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.

Powered by CMSimple