NPAC Technical Report SCCS-310
GORDIUS: A Data Parallel Algorithm for Spatial Data Conversion
Kim Mills, Ferenc Csillag, Maher Kaddoura
Submitted October 01 1993
Abstract
A data parallel algorithm is presented for spatial data (raster-to-vector)
conversion. It operates on pure two-dimensional raster images and derives a
fully topological vector data set, where polygons are defined by homogeneity
criteria. The algorithm is implemented in data parallel C, and makes
extensive use of scan functions that combine communication and computation
along grid axes. Code segments listing each step in building a
hierarchy of points, lines, and polygons are listed. Performance evaluations
on a Connection Machine-2 reveal that run-time is not sensitive to the
number of polygons in the image, and increases sublinearly with grid size.