Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Vekrtordaten optimieren

Werbeanzeige

Elmi

Treue Seele

  • »Elmi« ist der Autor dieses Themas

Beiträge: 253

  • Private Nachricht senden

1

22.01.2019, 14:08

Vekrtordaten optimieren

Hi,

mal ein etwas trivialeres Problem, allerdings vermute ich, das es dafür schon fertige Lösungen gibt und nich will jetzt nicht unbedingt das Rad neu erfinden:

Ich habe eine Sammlung von Linien die von Koordinate A nach Koordinate B gehen. Diese Linien bilden zusammen ein geschlossenes Polygon. Das Problem: sie sind wild durcheinander gemischt. D.h. das Polygon (=Dreieck im Beispiel) setzt sich nicht aus

A1 -> B1, A2 -> B2, A3 -> B3

zusammen (wobei B1=A2, B2=A3, B3=A1) sondern kann wild gemischt sein und auch in umgekehrter Richtung daher kommen:

A1 -> B1, B3 -> A3, A2 -> B2

Ich würde diese Linien jetzt gerne sortieren und optimieren, so dass sie mit minimal wenigen Daten auskommen:

A1 -> A2 -> A3 -> B3

Gibt's dafür schon eine fertige Lösung, die sowas schnell und zuverlässig erledigt?

Danke :-)

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

2

22.01.2019, 14:38

Um wie viele Segmente handelt es sich denn? An sich kann man da ja erst mal ganz stumpf anfangen und das erste Segment als Start festlegen. Jetzt sucht man solange die nächsten passenden Segmente bis man fertig ist. Das ganze hat dann eine Laufzeit von O(n²). Das geht bestimmt effizienter. Es stellt sich allerdings die Frage ob man das überhaupt braucht. Um den Ansatz noch mal etwas zu verdeutlichen:

Quellcode

 
1
2
3
4
5
6
7

aktuelles_segment = erstes_segment
für alle restlichen Segmente {
  wenn aktuelles_segment.Ende = neues_segment.Anfang {
    bringe neues_segment hinter aktuelles_segment
    aktuelles_segment = neues_segment
  }
}


edit: Das ganze würde ich erst mal testen und gucken ob das reicht. Alternativ könntest du eine Hashtable oder Baumstruktur/Dictionary verwenden und und alle Segmente mit ihrem Startpunkt als Schlüssel hinzufügen. Jetzt nimmst du ein beliebiges Segment als Startwert, guckst dir die Koordinate des Endpunktes an und holst das passende nächste Segment aus deiner Datenstruktur. Das machst du so lange bis du fertig bist, also aktueller Endpunkt dem Startpunkt deines ersten Segments entspricht. Je nach gewählter Datenstruktur und deren Implementierung sollte dieser Ansatz erst mal schneller sein. Es stellt sich allerdings die Frage ob das überhaupt von Interesse ist. An sich kannst du natürlich mal beide Varianten implementieren und messen was schneller ist. Vermutlich reicht der erste Ansatz aber locker aus.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Schorsch« (22.01.2019, 14:44)

Elmi

Treue Seele

  • »Elmi« ist der Autor dieses Themas

Beiträge: 253

  • Private Nachricht senden

3

22.01.2019, 14:48

Äh ja, mögliche Lösungswege hätte ich dafür selber, mir geht es eigebntlich darum, das eben NICHT selbst von Hand zu implementieren, wenn es dafür vielleicht schon was fertiges gibt...

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

4

22.01.2019, 14:54

Na ich weiß ja nicht womit du arbeitest, welche Sprache du verwendest und wie deine Koordinaten bzw Segmente aussehen. Bevor du da jetzt aber lange nach was fertigem suchst kannst du es auch fix selbst implementieren. Der erste Ansatz ist ja im Prinzip einfach ein selection sort. Das ist ja wirklich schnell geschrieben.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Werbeanzeige

Ähnliche Themen