Search code examples
algorithmgeospatialrastergeography

Converting vector-contoured regions (borders) to a raster map (pixel grid)

I have a map that is cut up into a number of regions by borders (contours) like countries on a world map. Each region has a certain surface-cover class S (e.g. 0 for water, 0.03 for grass...). The borders are defined by:

  • what value of S is on either side of it (0.03 on one side, 0.0 on the other, in the example below)
  • how many points the border is made of (n=7 in example below), and
  • n coordinate pairs (x, y).

This is one example. 

0.0300      0.0000           7
2660607.5   6332685.5   2660565.0   6332690.5   2660541.5   6332794.5 
2660621.7   6332860.5   2660673.8   6332770.5   2660669.0   6332709.5 
2660607.5   6332685.5

I want to make a raster map in which each pixel has the value of S corresponding to the region in which the center of the pixel falls.

Note that the borders represent step changes in S. The various values of S represent discrete classes (e.g. grass or water), and are not values that can be averaged (i.e. no wet grass!).

Also note that not all borders are closed loops like the example above. This is a bit like country borders: e.g. the US-Canada border isn't a closed loop, but rather a line joining up at each end with two other borders: the Canada-ocean and the US-ocean "borders". (Closed-loop borders do exist nevertheless!)

Can anyone point me to an algorithm that can do this? I don't want to reinvent the wheel!

Solution

  • The way I've solved this is as follows:

    1. March along each segment; stop at regular intervals L.
    2. At each stop, place a tracer point immediately to the left and to the right of the segment (at a certain small distance d from the segment). The tracer points are attributed the left and right S-value, respectively.
    3. Do a nearest-neighbour interpolation. Each point on the raster grid is attributed the S of the nearest tracer point.

    This works even when there are non-closed lines, e.g. at the edge of the map.

    This is not a "perfect" analytical algorithm. There are two parameters: L and d. The algorithm works beautifully as long as d << L. Otherwise you can get inaccuracies (usually single-pixel) near segment junctions, especially those with acute angles.