Say I have a graph with various vertex weights ("height"). How can I say "from this point, what is the descent path to a minimum?"

I feel like I'm just being stupid and this is like a second derivative of something or other, but I don't know anything :)

(a GridGraph, I should say)

@CarlLange You'll need FindShortestPath for this.

Look at the wiki page for the Dijkstra algorithm, which is one way to solve this.

However, you need the start point and the end point (your minimum). Do you know the minimum or would you have to calculate this as well?

@halirutan I thought so too, but I actually don't know if it's really what I'm looking for.

I came out with this in the end, which is really crap but basically does what I wanted:

descend[data_, {x_, y_}] :=
 Module[{startV = data[[x, y]],
   surround = data[[x - 1 ;; x + 1, y - 1 ;; y + 1]]},
  If[startV != Min[surround],
   {x, y} + (RandomChoice[Position[surround, Min@surround]] - 2),
   Nothing
   ]
  ]
descend[data_, Nothing] := Nothing

(I ended up not going the graph route at all)

I make maps as a hobby (toughsoles.ie/maps) and was playing around with generating this type of "contouring"

(from the 1801 General Survey of Kent maps)

I just assumed (for no good reason) that there was a Graph function to do something approximating the gradient descent-style functionality I was looking for originally.

@CarlLange OK, so you have a map and you try to calculate a way through it?

@halirutan Not quite.

@CarlLange Your first image could be interpreted as an energy (or weight) grid.

For something like this, algorithms do exist.

just to show what my method above gets, first is from a grid of start points and second is from pixels over a certain height:

Sorry for the screenshot spam.

The underlying image is a DEM - each pixel is a height value, this is a mountain range.

You can basically get similar data from GeoElevationData.

@CarlLange OK.

And what then?

Well, I thought, to get a look sort of similar to the 1801 map above, you basically roll a ball down from the top of a hill and draw the line it tracks. So that's what I was looking for

@CarlLange So basically you want to replicate the old style texture for mountains

It's kind of hard to show what I was looking for in the map above, let me see if I can find a better example.

@halirutan Yep, exactly.

Without hand-drawing it, ideally. ;)

@CarlLange And on your DEM maps, dark means high, right?

@halirutan No, light means high.

Might be easier to see the style I'm looking for on this page of the map: mapco.net/kent1801/kent40_01.htm

Obviously I'm not looking for a super-artistic look straight out of WL, I was just curious to what level I could get results.

(I'm certain there's a proper GIS algorithm for this to estimate river flows and so on, again, just curious if we could do it with WL 😉)

@CarlLange Your approach will most likely not work imo. The reason is simple: If you follow the "energy path", you will get straight lines. But what you want is an imitation of 3D. So the paths down the hills must be like projected curves.

@halirutan Ah, very good point.

@CarlLange I would simplify this problem:

(one sec)

f[x_, y_] := 1 - Sqrt[x^2 + y^2];
DensityPlot[f[x,y],{x,-1,1},{y,-1,1}]

Now, you can imaging, that going downhill from the center would simply result in straight, radial lines.

Sure, makes sense. I suppose I expected that it would be different because the DEM is so erratic.

@CarlLange One way I see here is to simply make a 3D projection. That means, you calculate the straight lines in 3D, so that you have line-strips consisting of points in 3D and then you project from a tilted perspective.

In case you're interested, here's the DEM:

CloudGet["https://www.wolframcloud.com/obj/5a37cec8-5245-45a4-aa78-4319ed0a21ce"]

@CarlLange Thanks, would have been my next question.

(Just a small sample of my actual dataset, but presumably enough to be getting on with. Actual dataset is about 10x the size.

(Actual actual dataset is multiple GB, but I'm happy to do this for a small area. just an experiment)

@CarlLange Ok, here is an idea:

1. img is your DEM. Calculate the regions where you want to draw your starting positions from:

starting = LocalAdaptiveBinarize[img, 10, {1.05, 0, 0}]

You can either take, say 10% of the white positions randomly or you use something more clever like (1) draw a point randomly, (2) select the next point that is most far away from this point, (3) select the next point that is most far away from both selected points, etc..

That gives you a sampling with points that are nicely distributed over the mountain tops.

2. You adjust your DEM, so that the algorithm stops in the valleys. You can use something like this

valleys = LocalAdaptiveBinarize[img, 10, {.99, 0, 0}];
img*valleys

Then, you let your algorithm compute the path for each starting point until it reaches a black valley pixel and you record (x, y, DEM(x,y))

3. Now you have a path for all starting points that you can (for a test) visualize with Graphics3D. Choose an orthogonal projection and look from directly above. Then you slightly rotate the graphics so that you see the 3D effect.

If this looks good, you can create this by a simple 3D projection matrix and turn it back into an image.

Interesting, thanks a lot for that! Sounds very clever.

@CarlLange If this works, it will definitely look more 3D than your maps. Your hand-drawn maps don't really care about a consistent perspective. They just try to simulate it a bit.

@halirutan Yeah, I agree. I'm curious how it'll turn out. I made a reasonably nice grayscale map recently and I thought it would be interesting to see how a different height representation would look with it.

@CarlLange Well, creating iso-lines is far easier.

@halirutan Certainly is! That's why I turned to WL to try out this different method, since QGIS does contours perfectly easily by itself :)

Thanks a lot for your suggestions! Helps loads.

@CarlLange It's just from the top of my head. It might be worth checking the literature if someone else thought about this problem.

@halirutan Certainly possible. It's possible to do "slope" analysis which gives you the gradient (in degrees) of each pixel (presumably by some radius) - I wonder does that make more sense to start with.

@CarlLange Yes, it's what you should use to get the path. You start and use a gradient map to find the way downhill.

@halirutan Yeah, rather than the absolute heights...

Don't you get that with a GradientFilter actually?

@CarlLange No, you need the direction and this is.. wait

GradientOrientationFilter

Oh, yep.

Well, I'm going to leave it for the night and give it another go in the near future, but thanks a lot for talking it out with me!

@CarlLange No problem. See you soon.

Need to go and walk our 40th out of 42 trails :) Only 500km left to go!

✌🏽

Oh god

@CarlLange Btw, I just remembered a nice way to make height lines without any computation at all. You just draw horizontal lines and you add the values of the DEM to each point:

img = CloudGet["https://www.wolframcloud.com/obj/5a37cec8-5245-45a4-aa78-4319ed0a21ce"];
data=ImageData[ImageAdjust@img,"Real"];
lines=Line[MapIndexed[Reverse[#2]+{0,#1*30}&,Reverse@data,{2}][[1;;-1;;5]]];

Graphics[
 {Inset[img, {1, 1}, {1, 1}, ImageDimensions[img]], lines},
 PlotRange -> {{1, 274}, {1, 240}}]

And you might enjoy this here: mewo2.com/notes/terrain