Come verificare se 4 punti formano un quadrato?

Supponendo che il tuo quadrato possa essere ruotato contro qualsiasi sistema di coordinate che hai in atto, non puoi fare affidamento sul fatto che ci siano ripetizioni dei valori X e Y nei tuoi quattro punti.

Quello che puoi fare è calcolare le distanze tra ciascuno dei quattro punti. Se trovi che quanto segue è vero, hai un quadrato:

1. Ci sono due punti, ad esempio A e C che sono distanza x l'uno dall'altro e altri due punti, ad esempio B e D che sono anche distanza x gli uni dagli altri.

2. Ogni punto {A, B, C, D} è alla stessa distanza dai due punti che non sono x di distanza. vale a dire se A è x lontano da C, allora sarà z lontano da B e D.

Per inciso, la distanza z dovrà essere SQRT (( x ^ 2) / 2), ma non è necessario confermarlo. Se le condizioni 1 e 2 sono vere, allora hai un quadrato. NOTA: alcune persone sono preoccupate per l'inefficienza della radice quadrata. Non ho detto che dovresti fare questo calcolo, ho appena detto che se lo facessi avresti un risultato prevedibile!

Ilminimodilavorochedovrestifaresarebbeselezionareunpunto,direAecalcolareladistanzadaciascunodeglialtritrepunti.SeriesciatrovarecheAèxdaunpuntoezdaaltriduepunti,devisolocontrollareglialtriduepuntil'unocontrol'altro.Sesonoanchexgliunidaglialtri,allorahaiunquadrato.cioè:.

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

PoichéAB=AD,selezionaBD:

• BD=x

Persicurezza,devicontrollareglialtrilati:BCeCD.

• BC=z
• CD=z

PoichéAC=BDepoichéAB=AD=BC=CD,questoèquindiunquadrato.

Lungoilpercorso,setrovipiùdiduedistintedistanzedalbordo,lafiguranonpuòessereunquadrato,quindipuoismetteredicercare.

Implementazionediesempidilavoro

Hocreatounesempiofunzionantesujsfiddle(vedi qui ). Nella mia spiegazione dell'algoritmo, io uso i punti arbitrari A, B, C e D. Quei punti arbitrari si trovano in un certo ordine al fine di camminare nell'esempio. L'algoritmo funziona anche se i punti sono in un ordine diverso, tuttavia, l' esempio non funziona necessariamente se questi punti sono in un ordine diverso.

Grazie a: meshuai, Blrfl, MSalters e Bart van Ingen Schenau per i commenti utili a migliorare questa risposta.

Scegli tre dei quattro punti.

Scopri se è un triangolo isoscele di destra controllando se uno dei tre vettori tra i punti è uguale a un altro ruotato di 90 gradi.

Se è così, calcola il quarto punto per addizione vettoriale e confrontalo con il quarto punto indicato.

Nota che questo non richiede costose radici quadrate, nemmeno la moltiplicazione.

Penso che la soluzione più semplice sia la seguente:

• Innanzitutto, calcola il centro dei 4 punti: center = (A + B + C + D)/4

• Quindi calcola il vettore A - center . Lascia che sia questo v := (x,y)

• Lascia che v2 sia il vettore v ruotato di 90 gradi: v2 := (-y, x)

• Ora gli altri punti dovrebbero essere center - v , center + v2 e center - v2 .

Il vantaggio di questa soluzione è che non devi usare le radici quadrate affatto.

Mi dispiace ma alcune risposte non si applicano.

Per il caso misuri 3 bordi (diciamo AB, AC e AD) per scoprire che due hanno le stesse dimensioni (diciamo AC e AD) e uno è più grande (diciamo AB). Quindi misureresti il CD per vedere se ha le stesse dimensioni di AB e lo trovi. Invece di un quadrato, potresti avere l'immagine qui sotto e questo la rende una soluzione sbagliata.

Quindiprovaun'altrasoluzione:misuratutteledistanzealmenounavolta:AB,AC,AD,BC,BD,CD.Poiscopriche4diallorasonouguali,eglialtri2sonougualitraloro.Mapotrestisemplicementeavereunafotocomediseguito:

Quindi, quelle risposte non sono corrette, nonostante gli alti voti che hanno ricevuto.

Una possibile soluzione: se le due misure uguali non collegano lo stesso punto. Quindi: se AB e CD hanno la stessa durata, anche tutte le altre combinazioni (AC, AD, BC, BD) sono uguali, hai un quadrato. Se hai lo stesso punto con la lunghezza maggiore (AB e AC è il più grande e tutti gli altri sono uguali), hai una delle foto sopra.

Lascia che i quattro punti abbiano i vettori di coordinate a, b, c, d.

Quindi chiamiamo le loro differenze w = (a-d), x = (b-a), y = (c-b), z = (d-c).

Quindi w è ortogonale a a se puoi creare w da una rotazione di 90 gradi. Matematicamente la matrice di rotazione di 90 gradi in 2-spazi è ((0, -1), (1, 0)). Quindi, la condizione se w è ruotata di 90 gradi risulta

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

Se questo è valido, allora devi controllare che w == -y e x == -z, o

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

Se queste tre relazioni mantengono, a, b, c, d creano un quadrato orientato.

Simile alla risposta di starblue

Scegli uno qualsiasi dei quattro punti.

Cerca tra di loro un vertice ad angolo retto : controllando se il prodotto punto di due dei tre vettori è zero. Se non trovato, non un quadrato.

Controlla se i vertici adiacenti a quest'angolazione sono anche ad angolo retto. Se no, non un quadrato.

Controlla se le diagonali sono perpendicolari : se il prodotto punto dei vettori tra il primo e il quarto vertice e gli altri due vertici (diagonali) è zero, allora è un quadrato.

Cisonoalcunebuonerispostequi,maladomandaharichiestol'approcciopiùsemplice.Hodatounpensieroveloceequestoècomelofarei.

Puoicapiresequattropuntirappresentanounquadrato(ancheseruotato),matrovilamediadeiquattropunti.

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

Unavoltaottenutalamedia,ladistanzatraognipuntoelamediadovrebbeesserelastessapertuttiequattroipunti.

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

Modifica

Il mio errore. Questo ti direbbe solo se i punti forma erano su un cerchio. Se controlli anche la distanza tra i punti, allora deve essere un quadrato.

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"

Ciò presuppone che i punti A, B, C, D non si incrocino (come in un ordine di avvolgimento valido).

questa non è una risposta secondo gli standard impostati, ma spero che questo aiuti:

[Copiato dal link sottostante in modo da non dover aprire il link] Python 76 caratteri

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

La funzione S prende come elenco un elenco di numeri complessi (A). Se conosciamo sia il centro che l'angolo di un quadrato, possiamo ricostruire il quadrato ruotando l'angolo di 90.180 e 270 gradi attorno al punto centrale (c). Sulla rotazione del piano complesso di 90 gradi circa l'origine viene eseguita moltiplicando il punto per i. Se la nostra forma originale e il quadrato ricostruito hanno gli stessi punti, deve essere stato un quadrato.

Questo è stato preso da: Determina se 4 punti formano un quadrato

Se ti piace la risposta, ti dico, concediti qualche momento per ringraziare la persona o per votare la sua risposta in quella pagina.

Penso che tu possa farlo con semplici addizioni e sottrazioni e trovando min / max. Termini (corrisponde allo schema di altre persone):

• Punto con il valore y più alto = > A
• più alto x = > B
• più basso y = > C
• lower x = > D

Se 4 punti condividono solo 2 valori x e 2 valori y hai un quadrato di livello.

Altrimenti, hai un quadrato se i tuoi punti soddisfano il seguente:

• A.x + C.x = B.x + D.x
• A.y + C.y = B.y + D.y
• A.y - C.y = B.x - D.x

Spiegazione: i segmenti di linea A-C e B-D dovrebbero incontrarsi ai loro punti medi. Quindi (A.x + C.x) / 2 è il punto medio di A-C e (B.x + D.x) / 2 è il punto medio di B-D. Moltiplicare ciascun lato di questa equazione per 2 per ottenere la mia prima equazione. La seconda equazione è la stessa cosa per i valori Y. Le forme romboidali (romboidi) soddisfano queste proprietà, quindi è necessario verificare che si abbiano lati uguali - che la larghezza sia uguale all'altezza. Questa è la terza equazione.

La soluzione è simile ai media pensanti.

Primo passo:

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

Questa proprietà è seguita da un quadrato perché è ciclica. ora un cerchio per seguire questa proprietà. quindi, ora controlla

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

if (f==1)
  square
else 
  not square

Qui A.B significa punto prodotto di A e B