Mapping a height map to a grid-based contour format [closed]

Question

I have a 2D height map in the following format

06 36 39 42 43 55 ... 
37 40 43 43 45 46 ...
40 43 44 45 46 48 ...
44 44 46 47 48 50 ...
41 44 45 47 48 48 ...
...

And I need to remap it into a grin based contour format (so it can further be mapped into sprites)

. . . . | . . 
. . . . \ . . 
. . . / / . . 
. . . | . . . 
. . . | . . . 
. / - / . . . 

Here . meaning flat area, | and - straight cliffs, / and \ cliff corners (each representing 2 different possibilities).

I have tried a standard marching squares approach, but found that sampling only 3 neighbours leads to quite a lot of problems, due to overloading the adjacent cases. (Note the extra out of place straight cliffs below)

. . . . | . \ 
. . . . \ \ .
. . . / / - .
. . . | - . .
. . . | . . .
. / - / . . .

What I would like, is some references to algorithms/approaches that help deal with this sort of thing. I know that contour walking with some sort of depth first search is an option but have not tried it out yet, and would prefer to leave that as a last resort. There is also the questions of representation of some features, for example whether to include cliff ridges that are 1 element thick or just ignore them. Another option is to pass through the generated contours and change them so they smoothly fit together, but this seems really hacky...

Answer 1

Create an interpolating/best-fit function. Your model should be a 2D polynomial (in x and y) whose degree is "just right": not too high that you will overfit everything, but not too low so that you lose detail.

You now have a mathematical function that you can slice, by setting f(x,y) = height. The solution to this equation is a contour. You now have two choices, depending on whether or not you can analytically solve.

• Assuming you cannot analytically solve, you can still easily trace out an approximation of the curve:
  • Begin by coloring the grid white if f(x,y)>height and black if f(x,y)<height. Note all "transition" areas where there is a black-white transition within a roughly <1 grid away: these are the squares the contour will lie in.
  • Randomly pick a transition square, and search within a roughly <1 grid radius for f(x,y)==height, to find a point on the contour. At that point (not necessarily on the grid) we calculate the gradient ∇f(x,y) = (∂f/∂x, ∂f/∂y) (the "uphill vector"). We rotate it by 90 degrees in either direction: (∂f/∂y, -∂f/∂x): this way points along the contour. We very slowly (with step size much smaller than the grid) trace the contour. This will take us all the way around a contour.
  • Every time we pass through a gridbox during this trace, we label it as either {|,-,/,} depending on something like which direction the average of the gradient is pointing. (We must also label the neighbors as . if they are not yet labeled; see [&ast;].)
  • Do note that there may still be transition gridboxes left over after that! For example, if you have two hills, you will have filled in one circle, but the contour is two circles. Repeat the above procedure on another random (unlabeled) "transition" gridbox (this is why we needed [&ast;], or else we might fixate on neighbors of spots we already accounted for). Repeat until there are no more unlabeled "transition" gridboxes.
  • Do this for each height-level you wish to draw as a contour, and you're done.
• You may be able to analytically solve like you would for conic sections, but this probably not likely and beyond the scope of this question. If you could solve for the curve, you could "gridify" it using various techniques (e.g. parameterize it, then walk along the contour using step sizes of maybe half-a-grid, noting the nearest-neighbors)

(If one of your contours overlaps another, the spacing between your contour heights is too small. If you are not satisfied with a given contour, the set of possibilities {-,|,/,} is too small.)