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

36

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.)

MarshalSHI
quelle
3
Ich nehme an, Sie müssten gedrehte Quadrate berücksichtigen?
Martijn Pieters
Haben Sie überhaupt Informationen zur Reihenfolge der Punkte? Das heißt, können Sie erkennen, ob zwei Punkte nebeneinander liegen oder eine Diagonale bilden? (Diese Informationen können verwendet werden, um den Prozess zu vereinfachen)
Daniel B
1
@DanielB Keine weiteren Informationen. Es ist so, als hätte ich ein weißes Papier und ziehe 4 Punkte nach dem Zufallsprinzip drauf. Dann möchte ich wissen, ob sie ein Quadrat bilden.
MarshalSHI
5
Insbesondere, wenn die Punkte als Gleitkommazahlen dargestellt werden, ist es nützlich, in jeden der unten vorgeschlagenen Vergleiche ein Gefühl der "Toleranz" aufzunehmen. Genaue Gleichheitsprüfungen können für die Ergebnisse von Gleitkommaoperationen fehlschlagen, selbst wenn wir Menschen sie als "nah genug" betrachten würden.
Stephan A. Terre
Das riecht nach einer Hausaufgabe. Nicht, dass daran etwas falsch ist. : / whathaveyoutried.com
Jim G.

Antworten:

64

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!

Illustration von quadratischen Regeln

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.

Joel Brown
quelle
17
Sie können diesen Vorgang kurzschließen und müssen sich keine Gedanken darüber machen, wie die Punkte angeordnet sind, indem Sie den Abstand zwischen ihnen messen und die Anzahl der gefundenen eindeutigen Abstände verfolgen. Wenn Sie zwei überschreiten (Joel x und z ), ist die Zahl kein Quadrat mehr.
Blrfl
1
Ich glaube nicht, dass es funktioniert. Endlich sagt man "es ist egal, ob BC oder CD". Aber wenn ich nur eine davon anchecke, ist die Figur vielleicht ein spezielles Parallelogramm.
MarshalSHI
2
Eine weitere Optimierung wäre, die quadratischen Abstände anstelle der Abstände zu vergleichen.
Vaughandroid
3
@Blrfl: Dein Test funktioniert nicht. Sei ABCD ein Diamant mit AB = BC = CD = DA = 1, AC = 1 auch (kurze Diagonale), dann AD ~ 1,7 (lange Diagonale) / Sie haben nur zwei Längen x und z, aber die Zahl ist kein Quadrat .
MSalters
2
@JoelBrown: Es ist möglich, eine Trapezform mit den Diagonalen AC = BD = x, den Seiten AB = BC = AD = z und der letzten Seite CD = y! = Z zu erstellen.
Bart van Ingen Schenau
23

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.

sternenblau
quelle
Eine der beiden guten Antworten. Verwenden Sie nicht, es sqrtsei denn, entscheidend! Sie müssen Ganzzahlberechnungen nicht auf FP herabsetzen, ganz zu schweigen von der Genauigkeit der FP-Berechnung.
K.Steff
Danke. ein guter.
MarshalSHI
Das ist der richtige Weg. Eine Multiplikation ist hier in der Tat nicht erforderlich.
KOMMEN SIE VOM
Wie können Sie feststellen, ob zwei Vektoren ohne Punktprodukt senkrecht zueinander stehen, was eine Multiplikation mit sich bringt?
Pavan Manjunath
(x, y), das um einen rechten Winkel gedreht wird, ist (-y, x) oder (y, -x), je nachdem, ob Sie in die positive oder negative Richtung drehen.
Starblue
15

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.

Elian Ebbing
quelle
2
Ja. Dies ist am verständlichsten und wahrscheinlich auch am einfachsten zu implementieren.
Eric G
Es scheint wie Vektorgleichheit von Segmenten. Kann jemand bitte erläutern oder beweisen, warum es funktioniert?
vCillusion
Es schlägt speziell für die Fälle (0,0), (2,1), (3, -1), (1, -2)
fehl
1
Es funktioniert für diesen Fall. Der Mittelpunkt ist (1,5, -0,5), der erste Punkt ist (0, 0) und drei andere Punkte sind (1,5, -0,5) + (1,5, -0,5) = (3, -1); (1,5, -0,5) + (0,5, 1,5) = (2, 1) und (1,5, -0,5) - (0,5, 1,5) = (1, -2), was bedeutet, dass es ein Quadrat ist. Der Beweis ist .. Symmetrie?
Aragaer
5

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.

Kein Quadrat ...

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:

Und das ist auch kein Quadrat ...

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.

woliveirajr
quelle
Nein, sein Algorithmus sagte, dass die 2 Kanten der Abstände x keinen Punkt teilen. aber Sie teilen gerade C. Also, nehmen Sie an, dass AC x ist, dann sollte BD ein anderes x anstelle Ihres BC sein.
MarshalSHI
3

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.

Mark Salzer
quelle
1
Ich denke, Rechteck kann auch Ihre Bedingungen erfüllen.
MarshalSHI
Nein, die erste Bedingung wird von orthogonalen, aber nicht gleich langen Vektoren nicht erfüllt.
Mark Salzer
1
Ja, ich vermisse nur den ersten. Die 4 Punkte sind aber nicht geordnet. Ich denke, wir brauchen weitere Schritte, um dies zu bestätigen.
MarshalSHI
Ja ... wenn keine klügere Idee auftaucht, müsste man eine Schleife machen. Ich denke, man braucht eine äußere Schleife, um w, x, y, z aus jeder möglichen Ordnung von a, b, c, d und eine innere Schleife für jede mögliche Ordnung des w, x, y, z-Tupels zu berechnen.
Mark Salzer
2

Ä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.

Max
quelle
Gute Idee, aber Sie müssen immer noch prüfen, ob der 4. Scheitelpunkt im richtigen Abstand zu den anderen Punkten liegt. Sie überprüfen nur, dass es auf der Diagonale ist.
Starblue
@starblue Richtig! Andernfalls kann sich ein Drachen bilden. Aktualisiert.
Max
2

Bildbeschreibung hier eingeben

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).

Reactgular
quelle
1

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.

bad_keypoints
quelle
1
Sie können den Algorithmus hier zusammenfassen. Sie verlinken auf eine andere SE-Site, was etwas besser ist, als auf eine andere Site zu verweisen. Wir möchten jedoch, dass sich die Antwort auf dieser Seite befindet, auf der die Frage gestellt wird. Jetzt müssen die Leute erneut klicken, um zu erfahren, wie die Antwort lauten könnte.
Martijn Pieters
1

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.

GlenPeterson
quelle
-3

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

singh13
quelle