Posted by Toby A Inkster on 02/16/07 09:43

Jerry Stuckle wrote:

> Nice algorithm. For your dead end, might I suggest you make the lowest
> square a lake and take the next lowest square as the outlet? Repeat
> until you get an outlet.

If I understand you correctly, I think you might end up with lakes that go
uphill that way. Consider the following landscape; heights in
metres, co-ordinates as A1, C2, etc:

A B C D E F G
1 800 600 400 500 600 800 800
2 800 550 350 480 550 650 600
3 800 550 200 300 310 300 300
4 880 650 220 400 400 450 500
5 900 700 240 400 450 500 550
6 900 700 280 450 500 550 600
7 900 650 350 500 550 600 650
8 900 650 300 550 600 650 700

Now imagine our river comes onto this map from the North at C1. Using my
algorithm it flows to C2 and then C3. Here it reaches a local minimum, so
should form a lake.

Using your algorithm, it will look to C4 as an outlet. Assuming we can't
go back to C3 as this would result in an infinite loop, we are again at a
local minimum, so we look to C5 as an outlet, and so on, eventually
expanding the lake into C5, C6 and C7 and then finally finding a way
downhill at C8.

In real life, although C3, C4, C5 and C6 would fill up as a lake, C7 would
not; D3 would become part of the lake, and the outlet would be through E3,
F3 and G3.

It's a rather contrived map -- a valley with two possible outlets for the
river: one that initially seems less favourable, but ultimately should
prove the chosen outlet. I'm sure it would crop up from time to time
though.

It *can* be dealt with computationally, but it's rather hard.

Personally I'd be tempted to not give the lake an outlet and explain it
away by saying that the water flows into an underground stream from there.
This might be a realistic explanation for one or two lakes on a map, but
not for hundreds though -- having not run the algorithm myself, I'm not
sure how often they would crop up.

--
Toby A Inkster BSc (Hons) ARCS
Contact Me ~ http://tobyinkster.co.uk/contact
Geek of ~ HTML/SQL/Perl/PHP/Python*/Apache/Linux

* = I'm getting there!

[Back to original message]