Fast summarizing algorithm for polygonal statistics over a regular grid. (September 2020) - Haag, Scott; Tarboton, David; Smith, Martyn; Shokoufandeh, Ali
Abstract: We describe a data structure and associated algorithm called Fast Zonal Statistics (FZS) for the retrieval of the summary characteristics of an arbitrary polygon derived from a regular grid. The FZS algorithm can return numerical (e.g., mean, sum, and count) attributes for a polygonal object over a regular grid (e.g., raster data model). The computational complexity of the FZS algorithm is constant in relation to the length of the polygon perimeter. This contrasts with existing approaches which scale in relation to the polygon area, therefore we expect and measure geometric decreases in execution time using the proposed approach for simple polygon surfaces. We demonstrate applications of the algorithm and data structure on example datasets extracting the sum of impervious surface for watershed boundaries in the Chesapeake Bay watershed, a common use case. Highlights: This manuscript describes a novel algorithm called Fast Zonal Statistics (FZS). The FZS returns univariate statics for a polygon region over a raster dataset. Theoretical estimates show a 99.83% reduction of complexity vs existing techniques. A code library was developed (https://github.com/ScottHaag/fast_zonal_statistics ).