Title: An Improved Algorithm for Calculating the Perimeter and Area of Raster Polygons

Date: 25 July 1999

Authors: Steven Prashker

Link: http://www.geovista.psu.edu/sites/geocomp99/Gc99/076/gc_076.htm

Abstract:

Key Words: algorithm, polygon, perimeter, area

The algorithm presented here was designed to improve the results obtained in calculating the perimeter or area of raster polygonal areas represented in a Geographic Information System (GIS). Generally, raster GIS systems use simplistic methods for calculating the perimeter and area of a polygon. For the area calculation, they typically count the number of pixels that make up the polygon, then multiply that total by the area of one pixel to get the area of the polygon. For the perimeter calculation, they typically count the number of edges of individual pixels that are considered on the boundary of the polygon, then multiply that total by the length of the side of the pixel (assuming square pixels) to get the perimeter of the polygon. The problem is that these simplistic methods do not take into account the aliasing error that is introduced for non-vertical or non-horizontal sides of polygons. Any polygon that has diagonal edges will usually have an overestimate for the perimeter, due to counting two edges per pixel (2 times the edge length) contributing to the perimeter, rather than counting the diagonal distance (sqrt(2) times the edge length). In severe cases, this can lead to a 50 percent error for the perimeter statistic. The error is not as severe for area calculations, since only the edge pixels of a polygon contribute to the aliasing error, but it can be as high as 20 percent, if the area of the polygon is small relative to the perimeter.

The method presented here compensates for the aliasing by visiting each pixel in an image, and surrounds it with an eight-pixel grouping, thereby forming a 3 by 3 grid. This results in up to 256 different combinations of pixels of the same class value surrounding the centre pixel. For each one of these unique combinations, a value or factor is associated with that combination that will compensate for the aliasing. Once the sums of these pixels or pixel edge factors are totaled for each unique class, they are then multiplied by the length or area of the pixel resulting in the corrected perimeter or area, respectively. The paper will examine extreme polygonal shape examples, such as square and diamond shaped polygons, in vector space, then rasterize these shapes, at varying resolutions, and compare the computed perimeters and areas with their vector equivalents. Tests will be performed on a typical raster map. Conclusions will be drawn based on empirical experiments in altering the combinations' values or factors. Preliminary results have shown the average error of raster polygon perimeter calculations approaching 2 percent, compared to the approximately 20 percent error reported from typical GIS software packages.

Reference:

IV International Conference on GeoComputation, Mary Washington College, Fredericksburg, VA, USA, 25-28 July 1999.