17. April 2005

Algorithmus gesucht!

Prosa

Man stelle sich eine "Hügellandschaft" vor (hier mal als Schnittmodell vereinfacht dargestellt):
2D Huegellandschaft
Auf diese prallen jetzt sintflutartige Regengüsse nieder, welche die Hänge hinabrinnen und die abflusslosen Täler allmählich fluten. Irgenwann sind alle diese Täler bis zum Rand gefüllt und sie fangen an, überzulaufen:
2D Hügellandschaft mit Wasser
gefüllt
Jetzt hört es zu regnen auf und es bricht der Winter herein, wodurch alle Talseen blitzartig zufrieren. Es schneit etwas, so dass eine infinitesimal Schneeschicht sich über die Landschaft legt. Nun fliegt ein Satellit über die Gegend und kartographiert die Höhenstufen. Er erkennt jedoch nicht, welche Flächen Gebirge sind und welche Flächen Eisseen.
Am Ende wurde eine Höhenkarte erstellt, welche auf den Landflächen die tatsächliche Höhe widerspiegelt, und bei den Tälern den maximalen Wasserstand, den dieses Tal fassen kann.
2D Huegellandschaft vereist

Aufgabenstellung

Was im obigen Schnittmodell sehr einfach aussieht, ist bei "echten" Höhenfeldern um einiges schwieriger. Hier mal ein so genanntes Plasma-Fraktal, welches oft zur Generierung natürlich wirkender 3D-Landschaften benutzt wird:
3D Huegellandschaft
Gegeben sei ein 2dimensionales Array mit Werten, welches die Höhenstufen des Geländes repräsentiert. Kleine Werte repräsentieren die tiefen Punkte, im Bild schwarz dargestellt, große Werte repräsentieren die Bergspitzen, im Bild weiß dargestellt. Außerhalb des Arrays ist stets der Wert 0 anzunehmen; das ganze ist also quasi eine "Insel im Ozean" (Es gibt keine negativen Werte für die Höhen!). In 3D sähe das dann schick gerendert etwa so aus:
3D Höhenfeld,
rerendert
Man schreibe nun eine Funktion, welche aus diesem 2D-Array nun die abflusslosen Täler und ihre maximalen Füllstände findet und als Ausgabe ein 2D-Array generiert, welches die Höhenstufen der gleichen Landschaft nach der "Sintflut" repräsentiert.

C

// already given
extern const int Width;
extern const int Height;
extern const unsigned** heightfield;

// todo!
void raining(int width, int height, const unsigned** original_landscape, unsigned** filled_landscape);

C++

// already given
extern const unsigned Width;
extern const unsigned Height;
typedef std::vector< std::vector<unsigned> > Heightfield;
extern const Heightfield heightfield;

// todo!
void raining(int width, int height, const Heightfield& original_landscape, Heightfield& filled_landscape);
Ich habe ein kleines Rahmenprogramm geschrieben, welches PGM-Dateien von stdin einliest, raining() aufruft und das Ergebnis nach stdout schreibt. Den Quellcode gibts natürlich auch.

Java

// already given
static final int Width;
static final int Height;
static final int[][] heightfield;

// todo!
void raining(int width, int height, int[][] original_landscape, int[][] filled_landscape);


Beispielbilder:Beispielbild 1 - Beispielbild 2
Ich bin auf eure Vorschläge gespannt.

Lars R. alias "Roker"