A topology-preserving polygon rasterization algorithm. Issue 6 (2nd November 2018)

• Record Type: Journal Article
• Authors: Zhou, Chen; Li, Dingmou; Xiao, Ningchuan; Chen, Zhenjie; Li, Xiang; Li, Manchun
• Is Part Of: Cartography and geographic information science. Volume 45:Issue 6(2018)
• Page Start: 495
• Page End: 509
• Publication Date: 2018-11-02
• Subjects: Polygon rasterization -- rasterization error -- topological error -- topology preservation -- topological accuracy; Cartography -- Periodicals; Geographic information systems -- Periodicals; 526
• DOI: 10.1080/15230406.2017.1401488
• Languages: English
• ISSNs: 1523-0406

Abstract

ABSTRACT: Conventional algorithms for polygon rasterization are typically designed to maintain non-topological characteristics. Consequently, topological relationships, such as the adjacency between polygons, may also be lost or altered, creating topological errors. This paper proposes a topology-preserving polygon rasterization algorithm to avoid topological errors. Four types of topological error may occur during polygon rasterization. The algorithm starts from an initial polygon rasterization and uses a set of preserving strategies to increase topological accuracy. The count of the four types of error measures the topological errors of the conversion. Topological accuracy is summarized as 1 minus the ratio of actual topological errors to the total number of possible error cases. When applied to a land-use dataset with a data volume of 128 MB, 127, 836 polygons, and extending 1352 km 2, the algorithm achieves a topological accuracy of more than 99% when raster cell size is 30 m or smaller (100% for 5 and 10 m). The effects of cell size, polygon shape, and number of iterations on topological accuracy are also examined.