Bei einer Reihe von Punkten, wie finde ich die beiden Punkte, die am weitesten voneinander entfernt sind? [Duplikat]

Question

  

Mögliche Duplizieren:
   größte lineare Dimension 2d Satz von Punkten

Ich kann den Abstand zwischen jedem Punkt berechnen und den größten nehmen, aber das klingt nicht wie eine sehr effiziente Art und Weise, es zu tun, wenn eine große (> 1000) Anzahl von Punkten.

. Hinweis: Diese für das iPhone ist, so dass ich eine Tonne nicht haben Macht der Verarbeitung

Answer 1

Sie fragen den Durchmesser des Satzes zu berechnen. Die Standardtechnik besteht darin, zuerst die konvexe Hülle zu berechnen, das das Problem zu finden, um den Durchmesser eines konvexen Polygons verringert. Selbst in dem Fall, dass Sie keine Punkte nicht beseitigen, hat dieses Bild Informationen sind genau das, was das Problem effizient zu lösen benötigt wird. Jedoch ist der Durchmesser eines konvexen Vielecks finden nicht ganz trivial; mehrere veröffentlichten Papiere mit Algorithmen für diese Aufgabe als falsch erweisen.

Hier ist ein eines korrektes O (n) Algorithmus für die Aufgabe (wobei n die Anzahl der Punkte in der konvexen Hülle ist).

Beachten Sie auch, die das iPhone ist nicht , die begrenzt; eine sorgfältig geschriebene Umsetzung auch der völlig naiven Algorithmus kann 1000 Punkte in weniger als eine Zehntelsekunde behandeln. Natürlich werden wir den richtigen Algorithmus Sie gehen viel schneller =)

Answer 2

Warum berechnen nicht nur die konvexe Hülle der Punkte? In Abhängigkeit von den Algorithmus verwenden, dauert es entweder O(n) oder O(n log n) Zeit und eliminiert alle inneren Punkte aus der Betrachtung. Dann nur diese äußersten Punkte überprüfen, die beide zu finden, die am weitesten entfernt sind.

Answer 3

Beginnen Sie mit Punkt mit dem niedrigsten x-Koordinaten zum Runterladen. (Nennen wir es Punkt X) Construct Satz von „Grenzpunkte“    mit Punkt x beginnt und vertikale Linie durch den Punkt, sollte es keine weiteren Punkte auf der PointX links sein, den nächsten Punkt in Grenze finden), indem Sie die Linie im Uhrzeigersinn langsam drehen (oder gegen den Uhrzeigersinn), bis die Linie einen anderen Punkt berührt, (siehe unten ). Fügen Sie diesen Punkt auf den Satz und wiederholen Sie mit diesem nächsten Punkt die nächsten zu bekommen, bis Sie schließlich wieder auf den ursprünglichen Punkt x erhalten. Sie NPW einen Satz von Punkten haben die Grenze des vollständigen Satz bilden. Vergleichen Abstand zwischen jedem Paar in diesem reduzierten Satz das Paar zu finden, die am weitesten voneinander entfernt sind.

To „drehen, um die Linie“ (an jeden sequentiellen Randpunkt zu finden), nehmen den Punkt, der „am weitesten“ in die Richtung ist, perpindicular an der Leitung für den letzten Grenzpunkt verwendet, und baut eine neue Linie zwischen dem letzten Randpunkt und dass „next“ Punkt. Dann sicher, dass es keine andere Punkte in der neuen perpindicular Richtung durch diese neue Linie gebildet Furthur. Wenn es keine anderen Punkte „Furthur out“ in der Dirtection perpindicular auf dieser Linie oder bis zur letzten Zeile sind, dann ist dies der richtige cjhoice für den nächsten Grenzpunkt, wenn es einen solchen Punkt ist, wechseln Sie zu dieser ein und wiederholen Sie den Test.

Answer 4

Siehe diesen Seiten (die ein verbunden und die Seiten erreichbar, indem Sie auf die Berechnung der Durchmesser der konvexen Hülle einer Menge von Punkten auf den „next“ Links) klicken.

Meine kurze Zusammenfassung:

1. Compute Menge von Punkten in konvexer Hülle (= O (n log n), die einzige Zeit, die Sie O (n bekommen), wenn Sie die Liste zuerst sortieren, die O nimmt (n log n) sowieso)
2. Reihenfolge entlang Grenze (Sie diese kostenlos erhalten, wenn Sie einen Graham Scan # 1)
3. Verwenden Sie eine der O (n) Durchmesser Algorithmen für die gegenüberliegende Punkte mit dem größten Durchmesser zu scannen. Shamos Algorithmus mir gut aussieht, wie es einer der Drehsattel Algorithmen.