Durchlauf durch Liste und Vergleich der Einträge

[Michi_J]

@ alle: Ich hätte dazu auch ein Bild vorbereitet, wie kann ich das posten?

[Hyperion]

@ alle: Ich hätte dazu auch ein Bild vorbereitet, wie kann ich das posten?

Link auf externes Picture Repo oder eben mit den img-Tags direkt einbetten (tinpic.com o.ä.).

[Michi_J]

hmmm ich hab das Bild aber in Word selbst erstellt, hat also keine URL...

[Hyperion]

hmmm ich hab das Bild aber in Word selbst erstellt, hat also keine URL...

Was hat denn das damit zu tun? Du musst das Dokument eben irgend wo im Netz ablegen.

Übrigens: Ein Bild in Word erstellt? Wie das? Und vor allem: wieso? Naja, solltest Du def. in ein neutrales Format konvertieren, sonst wird sich das hier kaum einer angucken denke ich mal

[Michi_J]

ja, bin ich grad dabei

[Michi_J]

sooo, anbei die beiden Bilder: Bild 1 stellt die Ausgangssituation dar, wie die Dreiecke in der Liste geordnet sind.
Bild 2 stellt die Ordnung der Liste dar, wie ich sie gerne hätte.

Vielleicht hilft das schon mal weiter.

Vielen Dank nochmals an alle, die mir weiterhelfen

[frabron]

Deine Reihenfolge ist doch total beliebig! Genauso gut könnte man 9=1, 4=2, 1=3 usw. aneinanderreihen. Ein Dreieck hat doch immer mehr als einen Nachbarn, und womit willst du festlegen, welcher der Nachbarn nun in deiner Reihenfolge präferiert wird? Und ausserdem gibt es für so etwas bereits fertige Tools, die benachbarte Geometrien finden können, sei es nun in deinem ArcGIS oder als OS Shapeyl in Python mit GEOS Schnittstelle.

Was ist denn das Endziel deiner Durchnummerierung?

[Michi_J]

genau, es soll ein beliebiger Nachbar gefunden werden. Das Endziel ist eben, dass benachbarte Dreiecke in der Liste aneinandergereit sind.

[Michi_J]

und dabei gibt es keine Präferenz, welcher Nachbar zuerst herangezogen werden soll, wichtig ist nur, dass ein Nachbar dort steht

[.robert]

Gibt es irgendwelche Einschränkungen auf dem Netz? Wenn z.B. sicher gestellt ist, dass jedes Dreieck in mindestens einem Punkt die umspannende Linie tangiert, könnte man sich einfach an der entlang hangeln und danach die Dreiecke nummerieren.

Wenn einfach so auf gut Glück bei einem beliebigen Netz ein beliebiger Nachbar gesucht werden soll, wird es schwer sicher zu stellen, alle Dreiecke zu besuchen bzw. eine durchgängige "Kette" zu erzeugen.

[EyDu]

Hallo.

Dann solltest du dir einen Algorithmus überlegen, wie du das Umsetzen möchtest. Ganz offensichtlich gibt es ja keine eindeutige Lösung um dein jetziges Kriterium zu erfüllen.

Sebastian

[.robert]

Jetzt bezogen auf dein zweites Bild und die Suche nach einem beliebigen Nachbarn, stell dir einfach folgenden Weg vor:
0->1->2->7->8->9->10. Was machst du dann mit 3,4,5,6?

Ein beliebiger Nachbar kann auch beliebig Scheiße sein

[Michi_J]

Nein, eine solche Einschränkung gibt es nicht. Es können dann im Anwendungsfall auch Dreiecke vorkommen, die komplett im Inneren des Netzes liegen

[Michi_J]

@ .robert: genau darin liegt das Problem, es muss der richtige Nachbar gefunden werden, sodass sichergestellt ist, dass kein Dreieck verloren geht. Ich hab aber keine Ahnung, wie ich das anstellen soll :K

[.robert]

Ich denke wir bewegen uns da auf das Thema Backtracking zu!

[.robert]

Vllt. steigst du da mal ein: http://de.wikipedia.org/wiki/Hamiltonkreisproblem

Ein Hamiltonkreis ist ein geschlossener Pfad in einem Graphen, der jeden Knoten genau einmal enthält. Ob ein solcher Kreis in einem gegebenen Graph besteht, ist ein fundamentales Problem der Graphentheorie. Im Gegensatz zum leicht lösbaren Eulerkreisproblem, bei dem alle Kanten genau einmal durchlaufen werden, ist das Hamiltonkreisproblem NP-vollständig, also wahrscheinlich nur mit hohem Aufwand lösbar.

[frabron]

Ich denke, du solltest deine Dreiecke in eine geeignetere Struktur (Objekt) überführen und entsprechende Methoden implementieren. Oder du nimmst etwas, was dir bereits solche Methoden implementiert, wie Shapely. Dort kannst du dann direkt mittels der Methode touches() direkt fragen, ob ein Objekt ein anderes berührt. Und es ist auch noch performant, da unter der Haube die GEOS Bibliothek werkelt, die in C geschrieben ist.

Oder du verräts endlich mal, warum du die Dreiecke durchnummerieren willst, und ich kann dir dann evt. noch ein paar Tipps geben, die deine Arbeit mit Geodaten betrifft und nichts mit Python zu tun hat

[Michi_J]

es geht im Grunde um die Kopplung eines GIS mit einem hydraulischen Modell. Und im hydraulischen Modell muss das Netz in 4 Dateien abgespeichert werden: Owner, Neighbour, Faces, Boundary-conditions. Deshalb brauch ich diese Struktur.

[frabron]

Ich denke, du solltest eine bessere Datenstruktur für deine Dreiecke nehmen. Für diesen Fall bieten sich Objekte ja geradezu an. Dann würde ich festhalten, wie die Nachbarschaftsbeziehungen für jedes einzelne Dreieck sind, also die Id eines jeden benachbarten Dreiecks festhalten. Um die Nachbarschaft festzustellen würde ich wie gesagt, auf Shapely zurückgreifen, wenn es dafür im GIS keine Funktion gibt, was ich mir aber zumindest bei ArcGIS nicht vorstellen kann. Zur Not musst du halt ein geeignetes Objekt dazu erzeugen (Polygon, oder besser je nach Lizenz halt ein Coverage - Äquivalent).

Von dieser Datenstruktur ausgehend kannst du dann deine Liste von Dreiecken erstellen um sie dann entsprechend in die vier Dateien zu speichern (komisches Format btw., gibt's da kein TIN Import?).

In Owner kommt das Dreieck?, in Neighbor der/die Nachbarn? Faces hat ja wohl was mit 3D Objekten zu tun, oder? Das sind doch die sichtbaren Flächen eines 3D-Körpers, oder erinnere ich mich da falsch?

[.robert]

Also "im Prinzip" solltest du dir bei so einem doch recht komplexen Problem nicht noch dadurch Probleme machen, dass du an einem bestimmten Ein-/Ausgabeformat fest hältst. Wenn das Problem gelöst ist lässt sich die Lösung immer noch in andere Formate übertragen.

Wichtiger ist es, das Problem so zu beschreiben (= in eine passende Datenstruktur zu biegen), dass es sich so leicht wie möglich lösen lässt.

Kleiner Gedankenanstoß hier:

Du hast ein beliebiges Netz von benachbarten Dreiecken, und suchst einen Weg, der einmal in jedes Dreieck führt. Eine passende Datenstruktur wäre, wenn du jedes Dreieck als Knoten siehst, und wenn zwei Dreiecke benachbart sind, existiert eine Kante zwischen den Knoten. Du ziehst also einen Graphen über die Dreiecke.

Jetzt suchst du dir auf dem Graphen den entsprechenden Startpunkt, und suchst dann einen Weg, der alle Knoten besucht.

Das wäre die triviale Herangehensweise. Vllt. hast du ja noch irgendwelche Einschränkungen und investierst noch ein wenig Gehirnschmalz, und kommst auf eine Idee, wie du das Problem so abbilden kannst, dass es einfacher zu lösen ist.