Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

--- ws1415:projekte_im_wintersemester_2014_15:optimierungsprogramm [2015/02/26 12:21]
jsauder
+++ ws1415:projekte_im_wintersemester_2014_15:optimierungsprogramm [2016/05/10 14:46] (aktuell)
@@ Zeile 4: / Zeile 4: @@
 Ein Programm, welches eine 3d Erhöhungsdatei, sowie zwei Punkte als Input nimmt und den kürzesten Weg zwischen den Beiden Punkten ausgibt.
+====Ergebnis====
+[[https://www.youtube.com/watch?v=nsnEnsky7W4|Youtube Video]]
 ==== Teilnehmer  ====
 *[[jsauder@campus.tu-berlin.de|Jonathan Sauder]]
@@ Zeile 14: / Zeile 17: @@
 Betrachten wir die Datei //run.py// und gehen chronologisch durch die Struktur bis zur Lösung.
-Es beginnt die Main-Methode. Notwendige  Übergabeparameter sind eine Liste aus Zahlenwerten, die die Z-Werte der Koordinaten von der 3D-Oberfläche darstellt. Des weiteren müssen noch Start-und Zielpunkt der Berechnung übergeben werden.
+Es beginnt die Main-Methode. Notwendige  Übergabeparameter sind eine Liste aus Zahlenwerten, die die Z-Werte der Koordinaten von der 3D-Oberfläche darstellt, Start-und Zielpunkt der Berechnung, und eine Auflösung mit der Kanten diskretisiert werden.
 <code Python>
@@ Zeile 109: / Zeile 112: @@
 <code Python>
 def pruefung(kante1,kante2):
-   if (kante2.fertig==True) or (kante2.history is kante1) or (kante2.history is kante1.history):
+   if (kante2.fertig==True):
       return False
+   if len(kante2.history!)=0:
+      if (kante2.history is kante1) or (kante2.history is kante1.history):
+         return False
    return True
 </code>
@@ Zeile 145: / Zeile 151: @@
 </code>
+Danach müssen alle Kanten darauf geprüft werden, ob sie in diesem Schritt fertig geworden sind.
+Kanten, die am Rand der Karte sind (die nur an einem Dreieck angrenzen, werden zunächst aus der Front herausgenommen und zubetrachtend hinzugefügt. Danach werden alle Zubetrachtenden Kanten darauf geprüft, ob sie Fertig sind. Zunächst wird geprüft ob diese Kanten am Rand der Karte liegen, woraufhin sie als Fertig definiert werden. Danach wird geprfüt ob es überhaupt noch ein Element in der Front gibt. Wenn es keins mehr gibt, können keine besseren Wege mehr gefunden werden und alle Kanten werden als fertig definiert. Zudem kann dann die dritte Bedingung nicht erfüllt werden. Wenn es aber noch mindestens ein Element in der Front gibt, sind Kanten genau dann fertig, wenn das Maximum von ihnen kleiner ist als das Minimum des ersten Elements der Front ist.
 <code Python>
-	#Hilfsindex, da aus der Liste waehrend der Schleife elemente entfernt werden
-	index=0
 	#Nimmt Kanten aus der Front, die am Rand der Karte sind (nur ein angrenzendes Dreieck)
 	#heraus und fuegt sie Zubetrachtend hinzu
+	index=0
 	for i in range(len(front)):
 		if (len(front[i-index].borderingTriangles)==1):
@@ Zeile 159: / Zeile 168: @@
-	#Hilfsindex
+	#Prüft ob Kanten in zubetrachtend Fertig sind
 	index=0
+	for i in range(len(zubetrachtend)):
-	for i in range(len(zubetrachtend)):
-		#Kanten am Rand der Karte sind als fertig definiert
 		if (len(zubetrachtend[i-index].borderingTriangles)==1):
 			zubetrachtend[i-index].fertig=True
@@ Zeile 172: / Zeile 177: @@
 			index+=1
+		#Wenn Alle Kanten Fertig oder Zubetrachtend sind, dann kann keine Bessere Lösung mehr gefunden werden
+		#Und die dritte Bedingung kann nicht mehr erfüllt werden
 		elif len(front)==0:
 			zubetrachtend[i-index].fertig=True
@@ Zeile 177: / Zeile 184: @@
 			fertig=reinpacken(fertig,zubetrachtend.pop(i-index))
 			index+=1
-		#Sonst bedingung: maximum der zubetrachtenden Kante muss kleiner sein als das minimum des kleinsten elements von front
+		#Sonst: maximum der zubetrachtenden Kante kleiner als minimum des kleinsten Elements von front
 		elif (zubetrachtend[i-index].maximum<front[0].minimum+0.0000001):
 			zubetrachtend[i-index].fertig=True
@@ Zeile 183: / Zeile 191: @@
 			fertig=reinpacken(fertig,zubetrachtend.pop(i-index))
 			index+=1
 	return zubetrachtend,front,fertig
+</code>
+=== Die Lösung ===
+Wenn diese Schleife nicht mehr läuft, wird dann noch mithilfe der Funktion //ende.py// der Unterpunkt auf den drei Kanten des Enddreiecks gefunden, für den gilt, dass die Summe des Weges vom Anfangspunkt zu diesem Unterpunkt und des Weges von diesem Unterpunkt zum Zielpunkt kleinstmöglich ist.
+Das Attribut weg dieses Punktes hat alle Unterpunkte eingespeichert, die berührt werden, wenn man auf dem optimalen Weg vom Anfangspunkt zum Endpunkt rechnet. Dieser Weg ist also die Lösung.
+<code Python>
+	from ende import ende
+	weg=ende(endkanten,endpoint,enddreieck)
 </code>
+====Insgesamt: ohne grafische Darstellung====
+Insgesamt sieht die datei //run.py// ohne jegliche grafische Darstellung also aus wie folgt:
+<code Python>
+from __future__ import division
+def main(asciidatei,startpoint,endpoint,aufloesung):
+   from datenstruktur import datenstruktur
+   punktliste,delaunay,dreiecksliste,kantenliste=datenstruktur(asciidatei,aufloesung)
+   #Init of Cython, notwendig um anfang.py bzw. berechnung.py auszuführen
+   import pyximport
+   pyximport.install()
+   #Anfangskanten finden
+   from anfang import anfang
+   anfangskanten,anfangsdreieck=anfang(startpoint,dreiecksliste)
+   #Endkanten finden
+   from endpunkt import endpunkt
+   endkanten,enddreieck=endpunkt(endpoint,dreiecksliste)
+   #Erstellen der Input-Listen
+   from copy import copy
+   zubetrachtend=copy(anfangskanten)
+   front=copy(anfangskanten)
+   fertig=[]
+   from schleife import schleife
+   while (endkanten[0].fertig==False or endkanten[1].fertig==False or endkanten[2].fertig==False):
+      zubetrachtend, front, fertig=schleife(zubetrachtend,front,fertig)
+   from ende import ende
+   weg=ende(endkanten,endpoint,enddreieck)
+   return 0
+</code>
+===== Die Visualisierung =====
-====Zwischenziele und nötige Kompetenzen: ====
+Die Visualisierung wurde mit Python-Matplotlib gemacht.
-Wir fangen mit einfachen Daten an, z.B den Eckpunkten eines Würfels(oder Pyramide), die wir selber einfach durch eine X,Y,Z Koordinate beschreiben können.
+Matplotlib ist zwar auf die dauer ziemlich langsam (am Ende mehr als die Hälfte der runtime), aber ist für simple Darstellungen durch eine übersichtliche API ziemlich nützlich. Rote Kanten sind als Kanten in der Front markiert, Grüne Kanten sind zu betrachtende Kanten, und blaue Kanten
+sind fertige Kanten (für die der Optimale Weg schon gefunden wurde)
-Daraufhin müssen wir unser Programm so schreiben, dass es die Punkte im Raum verbindet und in Dreiecke aufteilt, da mit Dreiecken am einfachsten zu rechnen ist.
+{{:ws1415:projekte_im_wintersemester_2014_15:bild1.png?400|}}{{:ws1415:projekte_im_wintersemester_2014_15:bild2_.png?400|}}
-Schließlich müssen wir noch den mathematischen Algorithmus schreiben, der Strecken auf der Dreiecksfläche berechnen kann und die kürzeste Strecke zwischen zwei Punkten findet.
+{{:ws1415:projekte_im_wintersemester_2014_15:bild3.png?400|}}{{:ws1415:projekte_im_wintersemester_2014_15:bild4.png?400|}}
+[[https://www.youtube.com/watch?v=nsnEnsky7W4|Youtube Video]]
 ==== Projektseiten ====

Mathesis Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Unterschiede

Seiten-Werkzeuge