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...

Selina

Can you explain a bit more your marching squares approach with 3 neighbours? I would think marching squares is ideal to render zero-crossings of (height_map - threshold). – Telephone

Marching square cases overwrite each other, I have set up a priority to ensure that flats don't overwrite cliffs but that still gives errors. The use thresholds is totally fine, it's picking the correct cases that is the problem. Half the time the algorithm might be trying to do the correct thing, and I'm just lacking the representation symbols to make any sense of it. – Selina

what is the function that relates your 2D height map to your grin based map? Do you assign a symbol based on the number stored in the map each symbol depends on its neighbours as well? – Nonreturnable

Have you checked the Wikipedia intro on the topic? (The article also describes edge thinning which is what you seem to need in your case.) I used to get rather good results with the Sobel operator (given that your picture is not noisy, this should work for you, too.) This SO question also mentions an algo giving good results. – Upanchor

Why can't you sample all 8 neighbours ? (if available) – Agler

The guys at gis.stackexchange.com might be able to help you with this. – Mcdonough

Can you use a Sobel filter (or another border detection filter) and process the output to replace the filter output values to ., -, |, / and \ – Platoon

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 [*].)
  • 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 [*], 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.)

Caprice

I think a best-fit function will be very sensitive to the order of his points. If they're all on a line (unique X coordinates), that's fine, but if it's a closes contour shape, that won't work. – Arel

@WouterLievens: I never suggested a best-fit function; that would be bad. In the first paragraph, I specifically suggested that he/she should pick "a 2D polynomial whose degree is "just right": not too high that you will overfit everything, but not too low so that you lose detail". – Caprice

I understand that. I just don't understand how you will sort the points. If he can sort them, he might as well connect-the-dots and smoothen that. – Arel

@WouterLievens: sorting a contour is done by following the vector orthogonal to the gradient, described where (∂f/∂y, -∂f/∂x) is mentioned. – Caprice

Oh I think I get it now. The fitted curve is not a fit to the contour, but to the sample coordinate space and the height map. It's all there - I just misread it. Sorry! :-) – Arel

The curve traced out is a contour. – Caprice

Hey, sorry for the long reply and thanks very much! I will try out a constraint-based correction approach for what I already have implemented (will post what I have if it works), but shall definitely have a good look at this. – Selina