Algorithmus oder Funktion zur Erzeugung von Isolinien

[EccoBravo]

Hallo allerseits,

ich will ein großes 2D-Array of single grafisch darstellen wie eine Wetterkarte (Isobaren).

Dazu will oder muß ich Linien gleicher Werte erzeugen, also Isolinien.

Kennt Ihr nicht irgend eine Funktion / Komponente oder einen simplen und sicheren Algorithmus, mit dem ich das machen kann?

Vielen Dank

E. B.

[EccoBravo]

Bitte um Verschieben dieses Beitrages, ich bin in der falschen Sparte gelandet

Danke E. B.

[dizzy]

Ein nD Array von Werten bezeichnet man als "Skalares Feld". Um beliebige skalare Felder im n-Dimensionalen zu Kanten zu verhelfen, bietet sich generell das "Marching Square" (2D) bzw. "Marching Cube" (3D) Verfahren an (beides ist an sich das selbe, und kann für beliebige Dimensionen > 1 erweitert werden). Eine schnelle Googlesuche ergab z.B. diese Webseite, die sich zwar relativ kurz fasst, dafür aber ein paar Illustrationen bietet.

[EccoBravo]

Erst mal vielen Dank,

schöne Seite und gut zu verstehen, aber nun kommen gleich die nächsten Fragen:

also ich rastere das Skalarfeld mit einem Quartipel durch, untersuche die Fläche Stück für Stück und male gleich die Isolinienstücken, die dann irgend wann mal ein ganzes Isolinienbild ergeben.

Frage 1:
Wenn ich nun diese Isolinien für weitere Datenverarbeitung abspeichern will, macht es sich gut, dieses in einer fortlaufenden Punktekette zu tun, die dann von Anfang bis Ende (auch geschlossene Kurven) später fortlaufend gezeichnet werden könnte.
Damit ich mit der Punktemenge nun kein wirres Zickzack erhalte, müssten diese Punkte fortlaufend sortiert werden.
Wie mache ich das?



Frage 2:
Mein Skalarfeld hat angenommen 512x512 Werte. Wenn ich nun hochauflösende Isolinien erhalten will nehme ich ein Quartripel im Orte m,n wie folgt

Delphi-Quellcode:

(m, n )    (m+1, n )

(m, n+1)   (m+1, n+1)

Step=1

Dann fällt ja das Interpolieren weg und das Zeichnen reduziert sich auf 6 Fälle.

Ist dieses Vorgehen sinnvoll, oder sollte ich ein gröberes Quartipel wählen, derart

Delphi-Quellcode:

(m, n )    (m+5, n )

(m, n+5)   (m+5, n+5)

Step=5

Sind meine Überlegungen sinnvoll oder was würdet Ihr empfehlen?

Grüße zum Wochenende

E. B.

[dizzy]

Zu 1)
Das ist garnicht mal sooo trivial. Eine schnell geschossene Idee: Du legst die zunächst ein weiteres Array an, in dem einfach nur alle möglichen Punkte vorkommen, die theoretisch möglich sind. (Die Verbindungspunkte der Strecken die bei dem Verfahren herauskommen.)
Dann eine Datenstruktur, die für bis zwei Strecken je zwei Referenzen auf die betreffenden Punkte in unserem ersten Array enthalten, die Start und Ende der Strecke markieren. Diese Datenstruktur dann wiederum als 2D Array, so dass sie nun alle "Squares" Repräsentiert. (Ich würde noch einen Zähler mitliefern, der angibt wie viele Strecken tatsächlich hinterlegt sind.) Zudem müssten in diese Struktur noch zwei Flags, mit denen man nachher signalisieren kann, ob eine Strecke bereits bearbeitet wurde.
Im ersten Ansatz dann einfach nach Anwendung von Marching Squares diese durchgehen, und sobald irgendwo eine Strecke vorkommt, an dieser weiter machen. Die Punkte merken, und an den 4 möglichen umliegenden prüfen, ob die letzte Strecke dort fortgesetzt wird, und ob diese Strecke noch nicht anderweitig bearbeitet wurde. Das wird dann duch einen einfachen Vergleich der Referenzen auf die Punkte möglich. (Rein theoretisch reicht auch eine Nummerierung der Punkte, jeodch müsste man dann jedes Mal die Koordinaten anhand des Index neu berechnen.)
Dann noch das Bearbeitet-Flag setzen, und so lange so weiter machen, bis sich keine freie Fortsetzung mehr angrenzend findet.
Alle Punkte die man auf diesem Weg dann findet, einfach in eine Liste speichern, und schwupps hast du eine sortierte (wenn auch nicht richtungsdefinierte) Liste von Punkten die eine Isobare beschreiben.
Das alles machen, bis man für alle Squares weiss, dass sie entweder keine Strecken mehr enthalten, oder alle bereits bedacht sind.


Zu 2)
Hängt voll und ganz davon ab, wie genau du es haben willst. Wenn du aber das Raster größer als die Samples wählst, solltest du den Mittelwert aller in einem Square befindlichen Samples als Grundlage nehmen. Mehr gibt es da glaube ich nicht zu bedenken.
Wie sinnvoll eine grobere Rasterung ist, hängt nur davon ab ob dein RAM ausreicht (o.g. Methode ist zugegebenerweise nicht grad Mr. Speichersparer *hüstel*), bzw. wie genau du es nun haben musst.


Gruss,
Fabian