GORDIUS - A DATA-PARALLEL ALGORITHM FOR SPATIAL DATA CONVERSION

A data parallel algorithm is presented for spatial data (raster-to-vec tor) conversion. It operates on pure two-dimensional raster images and derives a fully topological vector data set, where polygons are defin ed by homogeneity criteria. The algorithm is implemented in data paral lel C, and makes extensive use of scan functions that combine communic ation and computation along grid axes. Code segments listing each step in building a hierarchy of points, lines, and polygons are listed. Pe rformance evaluations on a Connection Machine-2 reveal that run-time i s not sensitive to the number of polygons in the image, and increases sublinearly with grid size.