Algorithmus zum Punkte verbinden

multimolti

Erfahrenes Mitglied
Hallo!

Ich brauche einen Algorithmus, dem ich eine Anzahl (ein Vielfaches von 3) Koordinaten gebe und der mir dann die beste Möglichkeit (oder zumindest eine Möglichkeit) bietet, immer 3 Punkte zu einem Dreieck zu verbinden, OHNE dass sich die Linien der verschiedenen Dreiecke überschneiden.

  1. Gibt es dafür schon Algorithmen, die ich implementieren kann?
  2. Wenn nicht, kann mir jemand einen Ansatz sagen, wie ich sowas programmieren könnte? Ich habe absolut keine Ahnung, wie ich anfangen soll...

Vielen Dank
 
Zuletzt bearbeitet:
Ja, die Koordinaten liegen alle im Bereich von 0 bis 1, aber das lässt sich ja beliebig skalieren.

Ich habe es jetzt geschafft, einen Algorithmus zu schreiben, der zumindest überhaupt mal Dreiecke zeichnet, aber sonderlich schön ist es noch nicht.

Meine Idee:
  1. Beliebigen Punkt suchen und als "benutzt" markieren
  2. Vom ersten Punkt aus den Punkt mit dem kürzesten Abstand suchen und auch als "benutzt" markieren
  3. Vom zweiten Punkt das gleiche machen und den 3. Punkt auch als "benutzt" markieren
Alle benutzen Punkte werden nie wieder verwendet. Dann zeichne ich Linien zwischen den 3 gefundenen Punkten und dachte, ich müsste viele kleine Dreiecke erhalten.
Leider klappt das irgendwie nicht so toll, meine Dreiecke sind oft sehr groß und langgezogen. Ich verstehe das nicht, es müsste doch klein werden!

So sieht es zum Beispiel aus: http://www.multimolti.de/download/stuff/dreiecke01.jpg
Und das hier sind die Daten, die ich verwende: http://www.multimolti.de/download/stuff/daten01.txt

Es muss aber eine bessere Idee als diesen Algorithmus geben, bitte helft mir!

Danke
 
Zeig am besten mal deinen derzeitigen Code.
Da kann man sich denke ich eher vorstellen, wie du die Daten behandelst.
Weil in der Txt-Datei sehe ich zum Beispiel 2 Koordinaten nebeneinander, für ein Dreieck braucht man jedoch 3 Koordinaten.

Zumal das anpassen sicher schneller geht, als alles noch ein zweites mal zu entwickeln.
 
Dein Problem ist der erste Punkt, die beliebige Auswahl eines Knotens. Denn dadurch bleiben irgendwann beliebige Knoten übrig, die nicht unbedingt optimal zueinander entfernt sind.

Statt der beliebigen Auswahl müssest du also eine bestimmte Auswahl treffen. Und das kannst du machen, indem du die Entfernungen der Knoten zueinander bestimmst und Gruppen von drei Knoten mit minimaler Entfernung zueinander bildest.
 
Hi,

du könntest immer mit einem Punkt in der Ecke anfangen.und dich am Rand entlang arbeiten. Sollte in den meisten fällen ein ordentliches Ergebniss liefern.

Lg
 
Hallo und Danke für die Antworten!

@Deluxe:
In der Textdatei sind natürlich zwei Koordinaten nebeneinander, einmal x und einmal y, also ein Punkt. Und ich muss jetzt aus jeweils 3 solcher Punkte Dreiecke zeichnen.

@Dunas:
Leider weiß ich nicht, welcher Punkt in einer Ecke ist. Das müsste ich erst mal durchrechnen lassen, und ich weiß auch nicht, ob das hilft.

@Gumbo:
Das klingt sehr plausibel, nur wie mache ich das am Besten?
 
Wie die Distanzen berechnet werden können, solltest du wissen (Pythagoras). Der Rest wird jedoch kniffliger.
 
Das mit den Distanzen habe ich doch schon längst, das brauche ich ja selbst für meinen Teil. Aber das Gruppieren, da habe ich keine Idee, wie ich das machen könnte.
 
Hmm..

Ein Dreieck zu zeichnen, ohne dass sich Linien kreuzen ist recht einfach, weil es im Dreieck gar nicht möglich ist, dass sich Linien schneiden. Daraus folgere ich, Du suchst einen Algorithmus der mehrere Dreiecke auf Deckung überprüft, und im vorliegenden Fall die Punkte neu gruppiert, oder ?

Vielleicht wäre es erstmal sinnvoll, nach Linienpaaren zu suchen, die sich kreuzen, damit ausgeschlossen werden kann, wo keine Dreieckskanten entstehen dürfen..

mfg chmee
 

Neue Beiträge

Zurück