erhält die nächsten Punkte, die ein Dreieck bilden
Ich habe einige Punkte (blau) in 2D.
Ich möchte diese drei Punkte, die ein Dreieck bilden, so erhalten, dass der Punkt D (rot) innerhalb dieses Dreiecks liegt. Wenn es kein solches Dreieck gibt, kann eine Ausnahme ausgelöst werden.
Also für das obige Bild möchte ich die schwarzen Punkte bekommen:
Was ich bisher gemacht habe: Ich dachte, ich könnte die Punkte nach ihrer Entfernung zu D ordnen und dann die ersten drei Punkte aus dieser sortierten Liste nehmen. Aber das Problem ist, dass es sein könnte, dass diese drei nächsten Punkte ein Dreieck bilden, das nicht den Punkt D enthält. Dies wird in diesem Bild gezeigt:
Zusätzlich zu den falschen Punkten konnte ich nicht bestimmen, ob das Wetter oder nicht D in der konvexen Hülle der gefundenen Punkte liegt und ob es ein Dreieck gibt, das den Punkt D enthält Dies ist der Punkt, wo ich stecken geblieben bin.
4 Antworten
Wie in den Kommentaren von TaW richtig angemerkt, wird der folgende Algorithmus in seiner Grundform nicht immer den besten finden Lösung oder überhaupt eine Lösung, weil es gierig mit den beiden Schränken beginnt.
Aber das könnte behoben werden, indem der Algorithmus wiederholt wird: Wenn das Dreieck nicht gefunden wird, können Sie es wiederholen, indem Sie den nächstliegenden Punkt ignorieren.
Wenn Sie nicht viele Punkte haben, können Sie den Algorithmus immer für verschiedene Startpunkte wiederholen, um sicherzugehen, dass Sie die optimale Lösung finden.
1) Finden Sie den nächsten Punkt zu D , nennen wir es A
2) Finden Sie den zweitnächsten Punkt zu D , nennen wir ihn B
3) finde die Gleichung einer Linie, die durch D und A verläuft, nennen wir es L1 (der fehlende Punkt muss) sei auf der anderen Seite von L1 als B )
4) Finden Sie die Gleichung einer Linie durch D und B , nennen wir es L2 (der fehlende Punkt muss) sei auf der anderen Seite von L2 als A )
5) Filtern Sie die restlichen Punkte: Lassen Sie nur Punkte auf der anderen Seite von L1 als B , die sich auf der anderen Seite von befinden L2 als A
6) Wenn es keine solchen Punkte gibt, werfen Sie die Ausnahme (oder wiederholen Sie sie mit einem anderen Startpunkt)
7) Finden Sie sonst den nächsten, nennen wir ihn C
8) Ergebnis ist das Dreieck ABC
Zusätzliche Hinweise:
Zwei Punkte befinden sich auf verschiedenen Seiten einer Linie, wenn diese Gleichung aufgrund ihrer Koordinaten unterschiedliche Vorzeichen ergibt ( X , Y , Z ) Liniengleichungskoeffizienten, normalerweise A , B , C werden verwendet, aber ich wollte sie nicht mit Punktelabels oben verwechseln):
Die Gleichung einer Linie, die durch zwei Punkte mit Koordinaten (V1x, V1y) und (V2x, V2y) verläuft, kann mit dieser Formel gefunden werden:
Dies gibt Ihnen die folgenden Formeln für Koeffizienten der Liniengleichung:
Der Schlüssel ist, nach einer gültigen Lösung zu suchen, während Sie sich gleichzeitig auf die optimale Lösung konzentrieren:
Für jeden Punkt: - Abstand zum Zielpunkt speichern - Position relativ zum Zielpunkt speichern.
Ich würde die folgende Enumeration verwenden, um die Position zu speichern:
%Vor%Dabei steht der erste Buchstabe für die x-Koordinate des Punkts relativ zur x-Koordinate des Ziels und der zweite Buchstabe für die y-Koordinate des Punkts relativ zur y-Koordinate des Ziels.
l weniger, g größer, e gleich
Bestellen Sie Ihre Punkte nach Entfernung (aufsteigend) zum Zielpunkt Beginne mit dem nächsten Punkt und erhalte abhängig von der relativen Position eine Liste von Kandidaten, die ein Dreieck um dein Ziel bilden würden. Erreichen Sie aus diesen Kandidaten auch das Ziel und fahren Sie mit dem dritten Punkt auf die gleiche Weise fort.
Ich bin jetzt auf dem Handy und es ist schwer, Code zur Verfügung zu stellen, aber ich werde es in ein oder zwei Stunden schreiben können.
Bearbeiten:
Entschuldigung für Verspätung. Hier ist ein Code.
Sie werden sehen, dass in ValidPositions method alle gültigen Positionen relativ zu den Positionen des ersten und zweiten Punktes fest codiert wurden. Ich weiß, dass es eine mathematische Beziehung zwischen ihnen gibt und dass sie generiert werden können, aber lassen wir das als Übung. :)
Auch bei dieser Methode gibt es Fälle, in denen Sie nicht sicher sein können, ob der Zielpunkt im Bereich des Dreiecks liegt (siehe UncertainSolution -Methode). Die Anzahl der Tests, wenn TriangleContainsPoint reduziert ist.
Edit 2: Fehler in der Methode TriangleContainsPoint
behoben %Vor%Ich bin mir nicht sicher, aber ich denke, das sollte funktionieren. 1) Finde zwei nächste schwarze Punkte 2) Finde andere nächste schwarze Punkte und speichere sie in ihrem zunehmenden Abstand von dem roten Punkt 3) Für jeden der obigen schwarzen Punkte, die in Schritt 2 gefunden wurden, konstruiere ein Dreieck mit Punkten in Schritt 1 4) Wenn der rote Punkt innerhalb der Dreiecksdistanz von einem roten Punkt zu einem der schwarzen Punkte liegt, sollte er nicht größer sein als die längste Seite des Dreiecks