Sunday, January 13, 2008

How to rasterize a polygon in JGrass - the quick and dirty scan line algorithm

After trying for a while to rasterize polygons by quering every point of the raster matrix to be inside of the given polygon, Martin Davis pointed me out to the scan line algorythm.

To make a quick and dirty implementation of it with the support of the JTS suite was fairly easy in JGrass:


GeometryFactory gFactory = new GeometryFactory();
int rows = active.getRows();
int cols = active.getCols();

for( int i = 0; i < rows; i++ ) {
for( int j = 0; j < cols; j++ ) {
if (rasterToMap != null) {
raster.setValueAt(i, j, JGrassConstans.defaultNovalue);
} else {
raster.setValueAt(i, j, 0.0);
}
}
// do scan line to fill the polygon
LineString line = gFactory.createLineString(new Coordinate[]{
rowColToCenterCoordinates(active, i, 0),
rowColToCenterCoordinates(active, i, cols - 1),});
if (polygon.intersects(line)) {
Geometry internalLines = polygon.intersection(line);
Coordinate[] coords = internalLines.getCoordinates();
for( int j = 0; j < coords.length; j = j + 2 ) {

int[] startcol = coordinateToNearestRowCol(active, coords[j]);
int[] endcol = coordinateToNearestRowCol(active, coords[j + 1]);

if (startcol == null || endcol == null) {
// vertex is outside of the region, ignore it
continue;
}
/*
* the part in between has to be filled
*/
for( int k = startcol[0]; k <= endcol[0]; k++ ) {
if (rasterToMap != null) {
raster.setValueAt(i, k, rasterToMap.getValueAt(i, k));
} else {
raster.setValueAt(i, k, 1.0);
}
}
}
}
}


Where raster and rasterToMap are two RasterData objects that simply wrap a double[][] matrix. Raster is an empty matrix to be filled, whereas rasterToMap is a map that can be used to "cut" out the data inside the polygon area to be put in the matrix to be filled.

As I said, quick and dirty :)

No comments: