2.1 Der String-Algorithmus



next up previous contents
Next: 2.1.1 Die Bewegung der Up: 2 Analyse bestehender Algorithmen Previous: 2 Analyse bestehender Algorithmen

2.1 Der String-Algorithmus

 

Der String-Algorithmus wurde von Jewett et al. [Jew77] vorgeschlagen und hat wohl die größte Verbreitung in der Topographiesimulation gefunden. Der Algorithmus approximiert den Rand des Simulationsgebietes durch eine Aneinanderreihung von Punkten (String), die durch Geradenstücke verbunden werden. Während der Simulation wird nun jeder Punkt entlang einer vorausberechneten Richtung bewegt, die Verbindungslinie der neuen Punkte stellt die Randkurve der Geometrie zum nächsten Zeitschritt dar (Abbildung 2.1). Die Richtung des Bewegungsvektors eines Punktes ergibt sich aus dem arithmetischen Mittel der Normalvektoren der angrenzenden Liniensegmente, und der Betrag errechnet sich aus der Multiplikation von Zeitschritt und Ätzrate. Das Vorzeichen der Ätzrate entscheidet über die Richtung der Punktbewegung und damit über Ätzung oder Deposition.

  
Abbildung 2.1: Der String-Algorithmus

Zu beachten ist, daß die Information über die Punktkoordinaten allein für die Implementierung nicht ausreicht. Es muß stets eine geordnete Folge von Punktkoordinaten oder Zusatzinformation über die Richtung der Liniensegmente vorhanden sein, um die Richtung der Punktbewegung bestimmen zu können. Durch die Bewegung des Strings rücken einige Punkte näher zusammen, andere entfernen sich voneinander. Der Algorithmus geht von einer idealen Segmentlänge und einer zugehörigen unteren und oberen Schranke aus. In Bereichen, wo die untere Segmentlänge unterschritten wird, müssen Punkte aus dem String entfernt werden, nicht nur um Speicherplatzproblemen vorzubeugen, sondern auch, um nicht mit der Segmentlänge in Bereiche der Maschinengenauigkeit zu gelangen und damit die Bestimmung der Orientierung des Liniensegments unmöglich zu machen. Abbildung 2.2 zeigt das Entfernen eines Punktes aus dem String.

  
Abbildung 2.2: Das Entfernen von Punkten aus dem String; (a) vor dem Entfernen des Punktes P3, (b) nach dem Entfernen des Punktes P3.

Als Alternative zur Entfernung des Punktes P3 wäre auch denkbar, für eine bessere Approximation der Randkurve, die Punkte P2 und P3 zu entfernen und einen neuen Punkt auf die Position der Streckenhalbierenden dieses Segmentes zu setzen. In Bereichen, wo die Segmentlänge einen oberen Grenzwert überschreitet, müssen Punkte eingefügt werden, wobei für den oberen Grenzwert entscheidend ist, wie gut die Geometrie mit einer bestimmten Segmentlänge approximiert werden kann. Die Krümmung der Randurve spielt damit indirekt eine Rolle, als Kriterium für das Entfernen und Einfügen von Punkten wird jedoch nur die Segmentlänge verwendet. Abbildung 2.3 zeigt das Einfügen eines Punktes in den String.

  
Abbildung 2.3: Das Einfügen von Punkten in den String; (a) vor dem Einfügen des Punktes P4, (b) nach dem Einfügen des Punktes P4.





next up previous contents
Next: 2.1.1 Die Bewegung der Up: 2 Analyse bestehender Algorithmen Previous: 2 Analyse bestehender Algorithmen



Martin Stiftinger
Thu Nov 24 17:41:25 MET 1994