Mathesis Wiki

Vorüberlegungen zum Lösungsalgorhitmus

Definition Fertig: Eine noch zu betrachtende Kante ist genau dann fertig, wenn das Maximum der Distanz zum Startpunkt kleiner ist als das kleinste Minimum der noch zu betrachtenden Kanten Hier müssen wir genau arbeiten, da wir Intervalle und keine Kanten betrachten. Eine Kante ist also dann Fertig, wenn alle „fertigen“ Intervalle zusammen die gesamte Länge der Kante abdecken

1) Übergebe einen Anfangspunkt und finde das Dreieck in dem er sich befindet

2) Startauflösung festlegen, Berechne für die ersten drei Kanten alle Punkte (je nach Auflösung)

3) Suche Kante mit kleinstem Minimum

4) Laufe „geradeaus“ vom Anfang über diese Kante und prüfe, in in welchem Dreieck wir uns befinden sobald wir über die Kante rechnen. Prüfe außerdem ob eine Kante fertig ist.

5) Rechne „über die Kante“ und prüfe an welchen beiden Kanten wir ankommen

6) Teile die ursprüngliche Kante in zwei Intervalle entsprechend dazu, welche Kante der „lichtkegel“ im zweiten Dreieck trifft

7) Suche die Kante in der Liste zu betrachtenden Kante mit dem kleinsten Minimum und Führe Schritte 4,5,6 noch einmal durch.

Im Grunde haben wir heute nichts geschafft: Heute haben wir weiteere Attribute, die wir unseren Objekten zuweisen wollen, beschlossen.

Dreiecke werden nun auch eine Ebenenengleichung, einen Normalvektor, und eine Funktion, die einem X,Y Punkt in einem Dreieck eine Z Koordinate zuweist.

Punkte erhalten als Attribut zusätzlich ihre Z Koordinate und ihren zugehörigen Ortsvektor.

Schließlich werden wir „Gerade aus“ definieren.

• Wir wählen einen Anfangspunkt und definieren diesen durch seinen Ortsvektor
• Wir wählen einen Richtungsvektor, der die Richtung bestimmt, in die wir gerade aus schießen.
• Wir rechnen bis zur nächsten Kante
• An der Kante prüfen wir, ob dies an einem weiteren Dreieck angenzt, wenn ja, rechnen wir in diesem weiter
• Um dies zu tun müssen wir den Winkel zwischen dem Richtungsvektor unseres Punktes und dem Vektor der Kante berechnen
• Den selben Winkel muss der Richtungsvektor im nachfolgenden Dreieck zur Kante haben

Heute haben wir folgende Datenstruktur festgelegt: Dreiecke als Objekte mit den Attributen:

• Punkte
• Menge der Punkte (um Mengenoperationen durchführen zu können)
• Kanten
• Nachbar-Dreiecke
• Funktion zum Testen ob ein Punkt in diesem Dreieck liegt

Punkte als Objekte mit den Attributen:

• Dreiecke deren Eckpunkt er ist
• Seine Koordinaten
• Kanten, deren Knoten er ist

Kanten

• Dreiecke deren Kante sie ist
• Knoten der Kante
• Funktion zum Testen ob ein Punkt auf dieser Kante liegt

Funktion, die Kanten erstellt muss sicher gehen, dass keine Kante doppelt existiert.

Folgende Lösungsüberlegungen:

• Wir haben einen Punkt, und können den Abstand zu jeder Stelle einer Kante des Dreieck berechnen in dem er liegt. Für das nachfolgende Dreieck können wir das selbe tun bis zum Endpunkt und dessen Dreieck. Das Ergebnis wäre das Minimum aller Lösungen, ausgedrückt durch die Folge der Punkte an den Kanten der durchquerten Dreiecke
• In alle Richtungen vom Anfangspunkt aus „schießen“, und gucken ob einige der Geraden in der Nähe des Lösungspunktes liegen
• Analog zur ersten Lösung, nur mit Wellen dargestellt