An investigation into trapezoidation and its application to geographic information systems and computer graphics
Decomposition, the breaking up of a polygon into elementary parts, is an essential first step for almost all operations on simple polygons. This approach allows for a more efficient algorithm, as the processing of each elementary part is simpler and more efficient than the processing of the whole polygon. The most common form of decomposition for polygons in 2D is trapezoidation, the breaking up of a polygon into trapezoids. The primary focus of this thesis is the trapezoidation process. Specifically, we show a new approach to the trapezoidation of simple polygons in 2D that is both simple yet practical and we improve upon the previous best algorithm for the trapezoidation of nested simple polygons in 2D. We also explore the previously unknown practical benefits to computer graphics of 2D trapezoidation in 3D environments.
We present a new 0(n) time heuristic based algorithm for the trapezoidation of simple polygons in 2D, where n is the number of vertices defining the polygon. Our approach is as simple as the 0(n log n) algorithms used in practice, but with better algorithmic performance. The solution is based on exploiting geometric characteristics of simple polygons. Importantly, we show that the algorithm will always produce a correct trapezoidation. We also provide an upper bound of 0(n^2) for worst-case performance. However, we show that for many simple polygons the algorithm runs in linear time. In particular, we show that our algorithm runs in linear time for a large number of polygons found in Geographic Information Systems (GIS).
An interesting problem within simple polygon trapezoidation is that of decomposing nested simple polygons. Such polygons are often encountered in GIS. To date only one algorithm has been presented for the trapezoidation of nested simple polygons in which both the enclosing and nested polygons are decomposed. This algorithm runs in 0(n^2 log n) time. Specifically it requires an expensive 0(n^2) post- processing stage. We present a new approach to the problem employing a novel data structure for storing polygon edges. It is this structure that allows us to avoid any costly post-processing stage and consequently our algorithm runs in O(nlogn). An improvement of 0(n) over the previous best algorithm. We show the performance of our algorithm using data sets typical to those found in GIS.
The trapezoidation of simple polygons defined in 3D produces a spatial scene representation similar to an octree or binary space partitioning (BSP) tree. Although a 3D trapezoidation has been considered for use in computer graphics its practical value is unknown. Given the extensive use of octree and BSP data structures in computer graphics it is interesting to investigate 3D trapezoidation in a similar context. Specifically, we show its use in walkthrough visualisations of architectural scenes. We present a simple method for constructing a 3D trapezoidation and con sider its use for visibility computation. We draw on the work performed in portal based rendering systems and in particular the past work in cell-to-cell visibility algorithms. We show how such visibility computation may be adapted for use with a 3D trapezoidation. We also present a novel visibility algorithm for walkthrough style visualisations based on this adaption.
This research will create a new approach to the trapezoidation of simple polygons in 2D that is both simple yet practical and will improve upon the previous best algorithm for the trapezoidation of nested simple polygons in 2D.
It will also explore the previously unknown practical benefits to computer graphics of 2D trapezoidation in 3D environments.