Comment vérifier si 4 points forment un carré?

Supposons que j'ai 4 points (ils sont en 2 dimensions), qui sont différents les uns des autres, et je veux savoir s'ils forment un carré. Comment faire? (Que le processus soit aussi simple que possible.)

En supposant que votre carré puisse être pivoté par rapport au système de coordonnées en place, vous ne pouvez pas compter sur la répétition des valeurs X et Y dans vos quatre points.

Ce que vous pouvez faire, c'est calculer les distances entre chacun des quatre points. Si vous trouvez que ce qui suit est vrai, vous avez un carré:

1. Il y a deux points, disons A et C, qui sont la distance x l'un de l'autre, et deux autres points, disons B et D, qui sont aussi la distance x l'un de l'autre.

2. Chaque point {A, B, C, D} est à égale distance des deux points non distants de x . c'est-à-dire: si A est x éloigné de C, alors il sera z éloigné de B et D.

Incidemment, la distance z devra être SQRT (( x ^ 2) / 2), mais vous n'avez pas besoin de le confirmer. Si les conditions 1 et 2 sont vraies, vous avez un carré. NOTE: Certaines personnes s'inquiètent de l'inefficacité de la racine carrée. Je n'ai pas dit que vous devriez faire ce calcul, j'ai juste dit que si vous le faisiez, vous obtiendriez un résultat prévisible!

Le strict minimum de travail que vous auriez à faire serait de choisir un point, par exemple A et de calculer la distance entre chacun des trois autres points. Si vous pouvez trouver que A est x d'un point et z de deux autres points, il vous suffit de vérifier ces deux autres points l'un par rapport à l'autre. S'ils sont aussi x l'un de l'autre, alors vous avez un carré. c'est à dire:

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

Puisque AB = AD, vérifiez BD:

• BD = x

Juste pour être sûr, vous devez vérifier les autres côtés: BC et CD.

• BC = z
• CD = z

Puisque AC = BD et puisque AB = AD = BC = CD, il s’agit donc d’un carré.

En cours de route, si vous trouvez plus de deux distances de bord distinctes, la figure ne peut pas être un carré, vous pouvez donc arrêter de regarder.

Exemple de mise en œuvre

J'ai créé un exemple de travail sur jsfiddle (voir ici ). Dans mon explication de l'algorithme, j'utilise des points arbitraires A, B, C et D. Ces points arbitraires se trouvent dans un certain ordre dans le but de parcourir l'exemple. L' algorithme fonctionne même si les points sont dans un ordre différent. Toutefois, l' exemple ne fonctionne pas nécessairement si ces points sont dans un ordre différent.

Merci à: meshuai, Blrfl, MSalters et Bart van Ingen Schenau pour leurs commentaires utiles visant à améliorer cette réponse.

Choisissez trois des quatre points.

Déterminez s'il s'agit d'un triangle rectangle isocèle en vérifiant si l'un des trois vecteurs entre les points est égal à un autre ayant subi une rotation de 90 degrés.

Si tel est le cas, calculez le quatrième point par addition de vecteur et comparez-le au quatrième point donné.

Notez que cela ne nécessite pas de racines carrées coûteuses, pas même de multiplication.

Je pense que la solution la plus simple est la suivante:

• Commencez par calculer le centre des 4 points: center = (A + B + C + D)/4

• Puis calcule le vecteur A - center. Que ce soitv := (x,y)

• Soit v2le vecteur vpivoté de 90 degrés:v2 := (-y, x)

• Maintenant, les autres points devraient être center - v, center + v2et center - v2.

L'avantage de cette solution est que vous n'avez pas du tout besoin d'utiliser des racines carrées.

Je suis désolé mais certaines réponses ne s'appliquent pas.

Dans le cas où vous mesurez 3 arêtes (disons AB, AC et AD), deux ont la même taille (disons AC et AD) et l’autre est plus grand (disons AB). Ensuite, vous mesureriez CD pour voir s’il s’agit de la même taille que AB et vous constaterez que c’est le cas. Au lieu d'un carré, vous pourriez avoir l'image ci-dessous, ce qui en fait une mauvaise solution.

Ensuite, vous essayez une autre solution: mesurez toutes les distances au moins une fois: AB, AC, AD, BC, BD, CD. Ensuite, vous trouvez que 4 d’entre eux sont égaux et les 2 autres sont égaux entre eux. Mais vous pouvez simplement avoir une photo comme ci-dessous:

Donc, ces réponses ne sont pas correctes, malgré les hauts votes qu'ils ont reçus.

Une solution possible: si les deux mesures égales ne connectent pas le même point. Donc, si AB et CD ont la même longueur, toutes les autres combinaisons (AC, AD, BC, BD) sont également égales, vous avez un carré. Si vous faites le même point en faisant la plus grande longueur (AB et AC sont les plus gros, et que tous les autres sont égaux), vous avez l'une des images ci-dessus.

Laissez les quatre points avoir des vecteurs de coordonnées a, b, c, d.

Appelons ensuite leurs différences w = (ad), x = (ba), y = (cb), z = (dc).

Ensuite, w est orthogonal à a si vous pouvez créer w à partir d'une rotation de 90 degrés. Mathématiquement, la matrice de rotation à 90 degrés dans l'espace 2 est ((0, -1), (1, 0)). Ainsi, la condition selon laquelle w est une rotation de 90 degrés a aboutit à

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

Si cela est le cas, vous devez vérifier que w == -y et x == -z, ou

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

Si ces trois relations tiennent, a, b, c, d font un carré orienté.

Semblable à la réponse de starblue

Choisissez n'importe lequel des trois points.

Cherchez un sommet à angle droit parmi eux : En vérifiant si le produit scalaire de deux des trois vecteurs est nul. Si non trouvé, pas un carré.

Vérifiez si les sommets adjacents à cet angle sont également à angle droit. Sinon, pas un carré.

Vérifiez si les diagonales sont perpendiculaires : Si le produit scalaire des vecteurs situés entre le premier et le quatrième sommet et les deux autres sommets (diagonales) est égal à zéro, alors c'est un carré.

Je pense que vous pouvez le faire avec une simple addition et soustraction et trouver min / max. Termes (correspond au schéma d'une autre personne):

• Point avec la valeur y la plus élevée => A
• plus haut x => B
• plus bas y => C
• x le plus bas => D

Si 4 points ne partagent que 2 valeurs x et 2 valeurs y, vous avez un carré de niveau.

Sinon, vous avez un carré si vos points satisfont aux critères suivants:

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

Explication: Les segments AC et BD doivent se rencontrer à mi-chemin. Ainsi (Ax + Cx) / 2 est le milieu de AC et (Bx + Dx) / 2 est le milieu de BD. Multipliez chaque côté de cette équation par 2 pour obtenir ma première équation. La deuxième équation est la même chose pour les valeurs Y. Les losanges (rhomboïdes) satisferont ces propriétés. Vous devez donc vérifier que vous avez des côtés égaux - que la largeur est identique à la hauteur. C'est la troisième équation.

Il y a quelques bonnes réponses ici, mais la question demandait l'approche la plus simple. J'ai réfléchi rapidement à cette question et voici comment je le ferais.

Vous pouvez savoir si quatre points représentent un carré (même s'il est pivoté), mais en recherchant la moyenne des quatre points.

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

Une fois la moyenne établie, la distance entre chaque point et la moyenne devrait être identique pour les quatre points.

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

MODIFIER:

Mon erreur. Cela ne vous dirait que si les points de forme étaient sur un cercle. Si vous vérifiez également la distance entre les points, alors il doit s'agir d'un carré.

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"

Cela suppose que les points A, B, C et D ne se croisent pas (comme dans le cas d’un ordre de bobinage valide).

ce n'est pas une réponse selon les normes établies, mais j'espère que cela aidera:

[Copié à partir du lien ci-dessous afin que vous n'ayez pas à ouvrir le lien] Python 76 caractères

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

La fonction S prend une liste de nombres complexes en entrée (A). Si nous connaissons à la fois le centre et le coin d'un carré, nous pouvons reconstruire le carré en faisant pivoter les coins de 90,180 et 270 degrés autour du point central (c). Sur le plan complexe, la rotation de 90 degrés autour de l'origine est effectuée en multipliant le point par i. Si notre forme originale et le carré reconstruit ont les mêmes points, alors ce doit être un carré.

Cela a été pris de: Déterminer si 4 points forment un carré

Si vous aimez la réponse, dis-je, prenez quelques instants pour remercier la personne, ou votez positivement pour sa réponse sur cette page.

Idée de base (cela répond à la question de savoir si je contribuais à quelque chose de nouveau, ce qui a été demandé par le bot lorsque j'ai cliqué pour fournir une réponse):

• un losange de diagonales égales est un carré.
• "simple que possible" comprend:
  • pas de division,
  • pas de racines carrées,
  • pas de ramification,
  • pas de recherche,
  • pas de contrôle d'angle ou de chachage,
  • pas de vecteurs,
  • pas de transformations,
  • pas de nombres complexes,
  • pas de fonctions multilignes, et
  • aucune importation de packages spéciaux (utilisez uniquement les éléments intégrés).
  • (Et pas d’éléments impériaux!)

Ma solution dans R est présentée ci-dessous. Je suppose qu'il y a exactement quatre points et que, selon l'énoncé du problème, il a déjà été déterminé que les points sont uniques.

sumsq <- function(x) sum(x^2)

quadrances.xy <- function(xy) vapply(
    as.data.frame(t(diff(xy)), optional=T), sumsq, 1)

Voir les travaux de Norman Wildberger, en particulier ses vidéos YouTube ( Poisson réel, Chiffres réels, emplois réels, etc.) et son livre Divine Proportions pour une discussion sur "quadrance".

xyse réfère à un type de matrice acceptée par de R plot, pointset les linesfonctions.

L'application de as.data.frameest un truc pour que R fasse les choses en colonne.

La optional=Tclause élimine les noms, qui ne sont de toute façon pas utilisés.

quadrances.xy..i2. <- function(xy, i2) vapply(
    as.data.frame(i2, optional=T),
    function(k) quadrances.xy(m[k,]),
    1)

C'est une fonction permettant de calculer les quadrances entre les points spécifiés, les paires de points étant spécifiées par l' i2argument. Le i2symbole fait référence à une matrice d'index qui a une colonne par index et 2 éléments par colonne (le même type de matrice renvoyée par la combnfonction).

quadrance.every.xy <- function(xy, .which=combn(nrow(xy), 2))
        quadrances.xy..i2.(xy, .which)

Le .whichest présenté comme un argument simplement pour l'exposer formalset pour tenter de communiquer ce qui se passe.

is.square.xy <- function(xy) {
    qq <- sort(quadrance.every.xy(xy))
    all(qq[2:4] == qq[1]) && # ALL SIDES (SHORT QUADRANCES) EQUAL
    qq[5] == qq[6] # ALL DIAGONALS (LONG QUADRANCES) EQUAL
}

J'ai dit "simple" n'incluait pas de fonctions multilignes. Vous devrez excuser cette fonction à deux lignes.

xy <- t(matrix(c(3,0,  7,3,  4,7,  0,4), ncol=4))
xy
#      [,1] [,2]
# [1,]    3    0
# [2,]    7    3
# [3,]    4    7
# [4,]    0    4
is.square.xy(xy)
# [1] TRUE

Notez que les quatre premières fonctions sont utiles, à part la question sur les quatre points.

Supposons quatre points A = (ax, ay), B = (bx, par), C = (cx, cy), D = (dx, dy), et ils forment les points d'un carré dans le sens inverse des aiguilles d'une montre. Nous déplaçons les points pour que A soit à (0, 0) en soustrayant ax de bx, cx et dx, et en soustrayant y de by, cy et dy, en définissant ax = ay = 0.

Si les points sont exactement les coins d'un carré dans le sens contraire des aiguilles d'une montre, on peut calculer où C et D sont: A et B: On devrait avoir (cx, cy) = (bx - par, bx + par) et (dx, dy) = (-by, bx). Nous calculons donc la distance au carré entre C et D, et le lieu où ils devraient se trouver: errC = (cx - bx + by) ^ 2 + (cy - bx - by) ^ 2, et errD = (dx + by) ^ 2 + (dy - bx) ^ 2. Nous les ajoutons et divisons par (bx ^ 2 + par ^ 2) en donnant err = (errC + errD) / (bx ^ 2 + par ^ 2).

Le résultat err serait 0 si un carré parfait, ou un petit nombre si presque un carré, et le nombre resterait inchangé à l'exception des erreurs d'arrondi si nous traduisions, mettions à l'échelle ou tournions les points du carré. Nous pouvons donc utiliser err pour décider de la qualité de notre carré.

Mais nous ne connaissons pas l'ordre des points. B et D doivent être à la même distance de A; si on multiplie cela par la racine carrée de 2, cela devrait être la distance de A à C. On l'utilise pour déterminer le point C: Calculer distB = bx ^ 2 + par ^ 2, distD = dx ^ 2 + dy ^ 2. Si distD ≥ 1,5 distB, alors nous échangeons C et D; si distB ≥ 1,5 distD, nous échangeons C et B. Maintenant, C a raison.

Nous pouvons également déterminer quels points sont B et D: si nous devinions mal lequel est B et D, notre calcul place D dans le tout mauvais emplacement, exactement à l'opposé de l'endroit où il se trouve. Donc si errD ≥ (bx ^ 2 + by ^ 2), alors nous échangeons B et D.

Cela arrangera correctement B, C et D si nous avons effectivement un carré ou du moins approximativement un carré. Mais si nous n’avons même pas approximativement un carré, nous savons que le calcul de l’erreur à la fin le montrera.

Sommaire:

1. Soustrayez ax de bx, cx, dx. Soustrayez y de par, cy, dy.
2. Soit distB = bx ^ 2 + de ^ 2, distD = dx ^ 2 + dy ^ 2.
3. Si distD ≥ 1,5 * distB, permutez C et D et calculez distD à nouveau.
4. Sinon, si distB ≥ 1,5 * distD, permutez B et C et calculez à nouveau distB.
5. Soit errD = (dx + by) ^ 2 + (dy - bx) ^ 2.
6. Si errD ≥ distB, permutez B et D, permutez distB et distD, calculez errD à nouveau.
7. Soit errC = (cx - bx + by) ^ 2 + (cy - bx - by) ^ 2.
8. Soit err = (errC + errD) / distB.
9. Décidez si nous avons un carré ou presque un carré en fonction de la valeur de err.

Si nous connaissons l'ordre des points, cela peut évidemment être simplifié.

La solution est similaire à la pensée médiatique.

Premier pas:

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

Cette propriété est suivie de square car elle est cyclique. maintenant un cercle pour suivre cette propriété. alors, maintenant il suffit de vérifier

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

if (f==1)
  square
else 
  not square

Ici, AB signifie produit scalaire de A et B