Algorithmus zur Ermittlung der 3 nächstgelegenen Punkte, die, wenn sie trianguliert werden, einen anderen Punkt überdecken

Question

Stellen Sie sich eine Leinwand vor, auf der eine Reihe von Punkten wahllos verstreut sind. Wählen Sie nun einen dieser Punkte aus. Wie würden Sie die 3 nächstgelegenen Punkte finden, so dass ein Dreieck, das diese Punkte verbindet, den gewählten Punkt abdeckt?

Klarstellung: Mit "am nächsten" meine ich die minimale Summe der Entfernungen zum Punkt.

---

Dies ist hauptsächlich aus Neugierde. Ich dachte, es wäre eine gute Möglichkeit, den "Wert" eines Punktes abzuschätzen, wenn dieser unbekannt ist, aber die umliegenden Punkte bekannt sind. Mit 3 umgebenden Punkten könnte man den Wert extrapolieren. Ich habe noch nie von einem solchen Problem gehört. Es scheint nicht sehr trivial zu sein, also dachte ich, es könnte eine lustige Übung sein, auch wenn es nicht die beste Art ist, etwas zu schätzen.

Answer 1

Ihre Problembeschreibung ist zweideutig. Welches Dreieck suchen Sie in dieser Abbildung, das rote oder das blaue?

Das blaue Dreieck liegt auf der Grundlage des lexikografischen Vergleichs der Abstände der Punkte näher, während das rote Dreieck auf der Grundlage der Summe der Abstände der Punkte näher ist.

Bearbeiten: Sie haben klargestellt, dass Sie wollen, dass die Summe der Entfernungen minimiert wird (das rote Dreieck).

Wie wäre es also mit diesem Sketch-Algorithmus?

1. Nehmen wir an, dass der gewählte Punkt im Ursprung liegt (das erleichtert die Beschreibung des Algorithmus).
2. Sortieren Sie die Punkte nach dem Abstand zum Ursprung: P(1) ist am nächsten, P( n ) ist am weitesten entfernt.
3. Beginnen Sie mit i \= 3, s \= .
4. Für jedes Tripel von Punkten P( a ), P( b ), P( i ) mit a < b < i wenn das Dreieck den Ursprung enthält, sei s \= min( s , |P( a )| + |P( b )| + |P( i )|).
5. Si s |P(1)| + |P(2)| + |P( i )|, stopp.
6. Si i \= n Stopp.
7. Andernfalls wird die Zahl i und gehen Sie zurück zu Schritt 4.

Offensichtlich ist dies im schlimmsten Fall O(n³).

Hier ist eine Skizze eines anderen Algorithmus. Betrachten Sie alle Punktpaare (A, B). Damit ein dritter Punkt ein Dreieck bilden kann, das den Ursprung enthält, muss er in dem grau schattierten Bereich in dieser Abbildung liegen:

Durch die Darstellung der Punkte in Polarkoordinaten ( r ) und sortiert sie nach , ist es einfach, alle diese Punkte zu untersuchen und den Punkt auszuwählen, der dem Ursprung am nächsten liegt.

Auch dies ist im schlimmsten Fall O(n³), aber eine vernünftige Reihenfolge der Besuchspaare (A, B) sollte in vielen Problemfällen zu einem frühen Ausgang führen.

Answer 2

1. Wie @thejh vorschlägt, sortieren Sie die Punkte nach der Entfernung zum gewählten Punkt.
2. Beginnen Sie mit den ersten 3 Punkten und suchen Sie nach einem Dreieck, das den gewählten Punkt abdeckt.
3. Wenn kein Dreieck gefunden wird, erweitern Sie den Bereich auf den nächstgelegenen Punkt und versuchen Sie alle Kombinationen.
4. Sobald ein Dreieck gefunden ist, haben Sie nicht unbedingt die endgültige Antwort. Allerdings haben Sie jetzt die Anzahl der zu prüfenden Punkte eingeschränkt. Der am weitesten entfernte zu prüfende Punkt wäre gleich der Summe der Abstände des ersten gefundenen Dreiecks. Bei jeder weiteren Entfernung ist die Summe der Abstände garantiert größer als das erste gefundene Dreieck.
5. Erweitern Sie Ihren Punktebereich um den letzten Punkt, dessen Abstand <= die Summe der Abstände des ersten gefundenen Dreiecks ist.
6. Prüfen Sie nun alle Kombinationen, und die Antwort ist das Dreieck, das aus dieser Menge mit der minimalen Summe der Abstände gefunden wurde.

Answer 3

Nur eine Warnung zur iterativen Methode. Es kann sein, dass du ein Dreieck mit 3 "nahen Punkten" findest, dessen "Länge" größer ist als die eines anderen, das sich ergibt, wenn du einen weiter entfernten Punkt zur Menge hinzufügst. Sorry, ich kann das nicht als Kommentar posten.

Siehe Grafik.

Das rote Dreieck hat einen Umfang von fast 4 R, während das schwarze Dreieck 3 Sqrt[3] -> 5,2 R hat.

Answer 4

Zweite Aufnahme

subsolution: (Grundlagen der analytischen Geometrie, überspringen Sie es, wenn Sie damit vertraut sind) Punkt der gegenüberliegenden Halbebene finden

Beispiel: Nehmen wir an, es gibt zwei Punkte: A \=[a,b]=[2,3] und B \=[c,d]=[4,1]. Vektor finden u \= A-B = (2-4,3-1) = (-2,2). Dieser Vektor ist parallel zu AB Linie, so auch der Vektor (-1,1). Die Gleichung für diese Linie ist definiert durch den Vektor u und zeigen in AB (d.h. A ):

X = 2 -1*t
Y = 3 +1*t

Wo t eine beliebige reelle Zahl ist. Beseitigen Sie t :

t = 2 - X
Y = 3 + t = 3 + (2 - X) = 5 - X
X + Y - 5 = 0

Jeder Punkt, der in diese Gleichung passt, liegt auf der Linie.

Nehmen wir nun einen weiteren Punkt, um die Halbebene zu definieren, d. h. C \=[1,1], erhalten wir:

X + Y - 5 = 1 + 1 - 5 < 0

Jeder Punkt mit entgegengesetztem Nichtgleichungszeichen liegt in einer anderen Halbebene, die diese Punkte darstellen:

X + Y - 5 > 0

Lösung: Suche nach dem kleinsten Dreieck, das dem Punkt entspricht S

1. Finden Sie den nächstgelegenen Punkt P as min(sqrt( ( Xp - Xs )^2 + ( Yp - Ys )^2 ))
2. Finden Sie den senkrechten Vektor zu SP como u \= (-Yp+Ys,Xp-Xs)
3. Zwei nächstgelegene Punkte finden A , B von der gegenüberliegenden Halbebene nach sigma \= pP donde p \= Su (siehe Teillösung), wie zum Beispiel A befindet sich auf der anderen Seite der Linie q \= SP (siehe letzter Teil der Teillösung)
4. Jetzt haben wir das Dreieck ABP die sich auf S : Summe der Entfernungen berechnen | SP |+| SA |+| SB |
5. Finden Sie den zweitnächsten Punkt zu S und fahren Sie mit 1 fort. Wenn die Summe der Entfernungen kleiner ist als in den vorherigen Schritten, merken Sie sie sich. Anhalten, wenn |SP| größer ist als die kleinste Summe der Abstände oder keine weiteren Punkte verfügbar sind.

Ich hoffe, dieses Diagramm macht es deutlich.

Answer 5

Dies ist mein erster Versuch:

1. den Raum in Quadranten aufteilen mit dem ausgewählten Punkt auf der [0,0] Koordinaten
2. den nächstgelegenen Punkt finden aus jedem Quadranten (Sie haben also 4 Punkte)
3. ein beliebiges Dreieck aus diesen sollte klein genug sein (aber nicht notwendigerweise das kleinste)