Wie überprüfe ich, ob 4 Punkte ein Quadrat bilden?

Angenommen, ich habe 4 Punkte (sie sind zweidimensional), die sich voneinander unterscheiden, und ich möchte wissen, ob sie ein Quadrat bilden. Wie es geht? (Lassen Sie den Vorgang so einfach wie möglich sein.)

Angenommen, Ihr Quadrat wird möglicherweise gegen das vorhandene Koordinatensystem gedreht, können Sie sich nicht darauf verlassen, dass sich die X- und Y-Werte in Ihren vier Punkten wiederholen.

Was Sie tun können, ist die Entfernungen zwischen jedem der vier Punkte zu berechnen. Wenn Sie feststellen, dass Folgendes zutrifft, haben Sie ein Quadrat:

1. Es gibt zwei Punkte, A und C, die den Abstand x voneinander haben, und zwei andere Punkte, B und D, die ebenfalls den Abstand x voneinander haben.

2. Jeder Punkt {A, B, C, D} ist gleich weit von den beiden Punkten entfernt, die nicht x entfernt sind. Dh: Wenn A x von C entfernt ist, dann ist es z von B und D.

Übrigens muss der Abstand z SQRT (( x ^ 2) / 2) sein, aber Sie müssen dies nicht bestätigen. Wenn die Bedingungen 1 und 2 erfüllt sind, haben Sie ein Quadrat. HINWEIS: Einige Leute sind besorgt über die Ineffizienz der Quadratwurzel. Ich habe nicht gesagt , dass Sie sollten diese Berechnung tun, ich sagte nur , dass , wenn Sie getan haben Sie würden ein vorhersagbares Ergebnis bekommen!

Das Nötigste, was Sie tun müssten, wäre, einen Punkt auszuwählen, beispielsweise A, und den Abstand zu jedem der anderen drei Punkte zu berechnen. Wenn Sie feststellen, dass A x von einem Punkt und z von zwei anderen Punkten ist, müssen Sie nur diese beiden anderen Punkte gegeneinander prüfen. Wenn sie auch x voneinander sind, haben Sie ein Quadrat. dh:

• AB = z
• AC = x
• AD = z

Da AB = AD, überprüfe BD:

• BD = x

Um sicherzugehen, müssen Sie die anderen Seiten überprüfen: BC und CD.

• BC = z
• CD = z

Da AC = BD und AB = AD = BC = CD ist, ist dies daher ein Quadrat.

Wenn Sie auf dem Weg mehr als zwei unterschiedliche Kantenabstände finden, kann die Figur kein Quadrat sein, sodass Sie aufhören können zu suchen.

Arbeitsbeispiel Implementierung

Ich habe ein funktionierendes Beispiel für jsfiddle erstellt (siehe hier ). In meiner Erklärung des Algorithmus verwende ich beliebige Punkte A, B, C und D. Diese beliebigen Punkte befinden sich zufällig in einer bestimmten Reihenfolge, um das Beispiel durchzugehen. Der Algorithmus funktioniert auch dann, wenn sich die Punkte in einer anderen Reihenfolge befinden. Das Beispiel funktioniert jedoch nicht unbedingt, wenn sich diese Punkte in einer anderen Reihenfolge befinden.

Vielen Dank an: meshuai, Blrfl, MSalters und Bart van Ingen Schenau für nützliche Kommentare zur Verbesserung dieser Antwort.

Wähle drei der vier Punkte.

Stellen Sie fest, ob es sich um ein rechtwinkliges gleichschenkliges Dreieck handelt, indem Sie prüfen, ob einer der drei Vektoren zwischen den Punkten gleich dem anderen ist, der um 90 Grad gedreht wurde.

Wenn ja, berechnen Sie den vierten Punkt durch Vektoraddition und vergleichen Sie ihn mit dem angegebenen vierten Punkt.

Beachten Sie, dass dies keine teuren Quadratwurzeln erfordert, nicht einmal eine Multiplikation.

Ich denke, die einfachste Lösung ist die folgende:

• Berechnen Sie zunächst den Mittelpunkt der 4 Punkte: center = (A + B + C + D)/4

• Berechnen Sie dann den Vektor A - center. Lass das seinv := (x,y)

• Sei v2der Vektor vum 90 Grad gedreht:v2 := (-y, x)

• Nun sollten die anderen Punkte sein center - v, center + v2und center - v2.

Der Vorteil dieser Lösung ist, dass Sie überhaupt keine Quadratwurzeln verwenden müssen.

Es tut mir leid, aber einige Antworten gelten nicht.

Für den Fall, dass Sie 3 Kanten messen (sagen wir AB, AC und AD), haben zwei die gleiche Größe (sagen wir AC und AD) und eine ist größer (sagen wir AB). Dann würden Sie die CD messen, um festzustellen, ob sie die gleiche Größe wie AB hat, und Sie stellen fest, dass dies der Fall ist. Anstelle eines Quadrats könnten Sie das Bild unten haben, und das macht es zu einer falschen Lösung.

Versuchen Sie es mit einer anderen Lösung: Messen Sie mindestens einmal alle Entfernungen: AB, AC, AD, BC, BD, CD. Dann stellen Sie fest, dass 4 von dann gleich sind und die anderen 2 auch untereinander gleich sind. Sie könnten aber auch ein Bild wie das folgende haben:

Daher sind diese Antworten trotz der hohen Stimmen nicht korrekt.

Eine mögliche Lösung: Wenn die beiden gleichen Maße nicht den gleichen Punkt verbinden. Also: Wenn AB und CD gleich lang sind, sind auch alle anderen Kombinationen (AC, AD, BC, BD) gleich, Sie haben ein Quadrat. Wenn Sie den gleichen Punkt haben, der die größte Länge ergibt (AB und AC sind die größten und alle anderen sind gleich), haben Sie eines der obigen Bilder.

Die vier Punkte sollen Koordinatenvektoren a, b, c, d haben.

Nennen wir dann ihre Differenzen w = (ad), x = (ba), y = (cb), z = (dc).

Dann ist w orthogonal zu a, wenn Sie aus a ein um 90 Grad gedrehtes w erzeugen können. Mathematisch ist die 90-Grad-Rotationsmatrix im 2-Raum ((0, -1), (1, 0)). Somit ergibt sich die Bedingung, ob w um 90 Grad gedreht ist

(w_1 == -x_2 und w_2 == x_1)

Wenn dies zutrifft, müssen Sie überprüfen, ob w == -y und x == -z oder

((w_1 == -y_1 und w_2 == -y_2) und (x_1 == -z_1 und x_2 == -z_2))

Wenn diese drei Beziehungen gelten, ergibt a, b, c, d ein orientiertes Quadrat.

Ähnlich wie die Antwort von Starblue

Wählen Sie drei der vier Punkte.

Suchen Sie einen rechtwinkligen Scheitelpunkt zwischen ihnen : Prüfen Sie, ob das Skalarprodukt von zwei der drei Vektoren Null ist. Wenn nicht gefunden, kein Quadrat.

Überprüfen Sie, ob die diesem Winkel benachbarten Scheitelpunkte ebenfalls rechtwinklig sind. Wenn nicht, kein Quadrat.

Überprüfen Sie, ob die Diagonalen senkrecht sind : Wenn das Skalarprodukt der Vektoren zwischen dem ersten und vierten Eckpunkt und den beiden anderen Eckpunkten (Diagonalen) Null ist, ist es ein Quadrat.

Hier gibt es einige gute Antworten, aber die Frage wurde nach dem einfachsten Ansatz gestellt. Ich dachte kurz darüber nach und so würde ich es machen.

Sie können feststellen, ob vier Punkte ein Quadrat darstellen (auch wenn sie gedreht sind), aber den Durchschnitt der vier Punkte ermitteln.

R = (A+B+C+D)/4

Sobald Sie den Durchschnitt haben, müsste der Abstand zwischen jedem Punkt und dem Durchschnitt für alle vier Punkte gleich sein.

if(dist(R,A) == dist(R,B) == dist(R,C) == dist(R,D) then
   print "Is Square"
else
   print "Is Not Square"

BEARBEITEN:

Mein Fehler. Das würde dir nur sagen, wenn die Formpunkte auf einem Kreis wären. Wenn Sie auch den Abstand zwischen Punkten prüfen, muss es sich um ein Quadrat handeln.

if(dist(R,A) == dist(R,B) == dist(R,C) == dist(R,D) AND
  (dist(A,B) == dist(B,C) == dist(C,D) == dist(A,D) then
   print "Is Square"
else
   print "Is Not Square"

Dies setzt voraus, dass sich die Punkte A, B, C, D nicht kreuzen (wie bei einer gültigen Wicklungsreihenfolge).

Dies ist keine Antwort gemäß den festgelegten Standards, aber ich hoffe, dies hilft:

[Kopiert vom unten stehenden Link, damit Sie den Link nicht öffnen müssen] Python 76-Zeichen

def S(A):c=sum(A)/4.0;return set(A)==set((A[0]-c)*1j**i+c for i in range(4))

Die Funktion S verwendet eine Liste komplexer Zahlen als Eingabe (A). Wenn wir sowohl die Mitte als auch eine Ecke eines Quadrats kennen, können wir das Quadrat rekonstruieren, indem wir die Ecke um 90, 180 und 270 Grad um den Mittelpunkt drehen (c). Auf der komplexen Ebene erfolgt die Drehung um 90 Grad um den Ursprung, indem der Punkt mit i multipliziert wird. Wenn unsere ursprüngliche Form und das rekonstruierte Quadrat die gleichen Punkte haben, muss es ein Quadrat gewesen sein.

Dies wurde entnommen aus: Bestimmen Sie, ob 4 Punkte ein Quadrat bilden

Wenn Sie die Antwort mögen, sage ich, nehmen Sie sich einen Moment Zeit, um der Person zu danken, oder stimmen Sie ihre Antwort auf dieser Seite ab.

Ich denke, Sie können dies durch einfaches Addieren und Subtrahieren und Finden von min / max tun. Begriffe (entspricht dem Diagramm anderer Personen):

• Punkt mit dem höchsten y-Wert => A
• höchstes x => B
• niedrigstes y => C
• niedrigstes x => D

Wenn 4 Punkte nur 2 x-Werte und 2 y-Werte gemeinsam haben, haben Sie ein Ebenenquadrat.

Andernfalls haben Sie ein Quadrat, wenn Ihre Punkte die folgenden Kriterien erfüllen:

• Axe + Cx = Bx + Dx
• Ay + Cy = By + Dy
• Ay - Cy = Bx - Dx

Erläuterung: Die Liniensegmente AC und BD sollten sich an ihren Mittelpunkten treffen. Somit ist (Ax + Cx) / 2 der Mittelpunkt von AC und (Bx + Dx) / 2 ist der Mittelpunkt von BD. Multiplizieren Sie jede Seite dieser Gleichung mit 2, um meine erste Gleichung zu erhalten. Die zweite Gleichung gilt auch für Y-Werte. Diamantformen (Rhomboide) erfüllen diese Eigenschaften, daher müssen Sie sicherstellen, dass Sie gleiche Seiten haben - dass die Breite der Höhe entspricht. Das ist die dritte Gleichung.

Die Lösung ähnelt den Denkmedien.

Erster Schritt:

x = (A+B+C+D)/4
f=0
if(dist(x,A) == dist(x,B) == dist(x,C) == dist(x,D) 
   f=1
else
   f=0

Auf diese Eigenschaft folgt ein Quadrat, da es zyklisch ist. Nun folgt ein Kreis dieser Eigenschaft. Also, jetzt einfach nachschauen

if(A.B==B.C==C.D==D.A==0)
  f=1
else 
  f=0

if (f==1)
  square
else 
  not square

Hier bedeutet AB Punktprodukt von A und B