An almost linear-time algorithm for trapezoidation of GIS polygons

摘要

The decomposition of planar polygons into triangles is a well studied area of computer graphics with particular relevance to geographic information systems (GIS). Trapezoidation is often performed as a first step to triangulation. There is a complex linear-time algorithm [Discrete Comput. Geom. 6 (1991) 4851 for the decomposition of a simple polygon into triangles. However, it is extremely complicated and in practice O(n log n) algorithms are used. Our motivation in trapezoidation of large GIS polygons is the fast display of such polygons. It is much faster to display simple shapes like triangles or trapezoids on raster graphics devices, compared to complex polygons. Hence, quite often complex polygons are decomposed into triangles or trapezoids for displaying. Since triangulation is usually more difficult compared to trapezoidation, we are interested in trapezoidation of GIS polygons for faster display. We present a very simple algorithm for the trapezoidation of simple polygons without holes. Our algorithm runs in O(n) time in practice with a very small hidden constant. We have extensively tested our algorithm for polygons in a GIS database. Our algorithm is easy to implement compared to existing algorithms and runs extremely fast even for polygons with thousands of vertices. (C) 2003 Elsevier B.V. All rights reserved.