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

35

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

MarshalSHI
la source
3
Je suppose que vous devez tenir compte des carrés tournés?
Martijn Pieters
Avez-vous des informations sur l'ordre des points? C'est-à-dire, pouvez-vous dire si deux points sont adjacents ou forment une diagonale? (Cette information peut être utilisée pour simplifier le processus)
Daniel B
1
@DanielB Aucune autre information. C'est comme si j'avais un papier blanc et que je dessinais 4 points au hasard. Ensuite, je veux savoir s’ils forment un carré.
MarshalSHI
5
En particulier si les points sont représentés sous forme de nombres à virgule flottante, il est utile d’inclure une notion de "tolérance" dans l’une des comparaisons suggérées ci-dessous. Les vérifications d'égalité exactes peuvent échouer pour les résultats des opérations en virgule flottante, même si nous les considérions comme "suffisamment proches".
Stephan A. Terre
Cela sent comme une question de devoirs. Non pas que quelque chose ne va pas avec ça. : / whathaveyoutried.com
Jim G.

Réponses:

65

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!

Illustration des règles carrées

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.

Joel Brown
la source
19
Vous pouvez court-circuiter ce processus sans vous soucier de la façon dont les points sont ordonnés en mesurant la distance qui les sépare et en gardant une trace du nombre de distances uniques que vous trouvez. Une fois que vous dépassez deux (Joël x et z ), le chiffre n'est plus un carré.
Blrfl
3
Une autre optimisation consisterait à comparer les distances au carré au lieu des distances.
vaughandroid
4
@Blrfl: Votre test ne fonctionne pas. Soit ABCD un diamant avec AB = BC = CD = DA = 1, AC = 1 aussi (diagonale courte), puis AD ~ 1,7 (longue diagonale) / Vous n’avez que deux longueurs x et z, mais le chiffre n’est pas un carré .
MSalters
2
@JoelBrown: Il est possible de créer une forme de trapèze avec les diagonales AC = BD = x, les côtés AB = BC = AD = z et le dernier côté CD = y! = Z.
Bart van Ingen Schenau
2
Assez juste, notez cependant que OP a dit explicitement 2 dimensions.
Joel Brown
24

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.

bleu étoile
la source
Une des deux bonnes réponses. Ne pas utiliser sqrtsauf si crucial! Vous n'avez pas besoin de dégrader les calculs entiers en FP ... sans parler de la détérioration de la précision du calcul en FP.
K.Steff
THX. un bon.
MarshalSHI
Maintenant c'est la bonne façon de le faire. La multiplication n'est en effet pas nécessaire ici.
VENEZ DU
Comment trouvez-vous si 2 vecteurs sont perpendiculaires l'un à l'autre sans leur produit scalaire impliquant une multiplication?
Pavan Manjunath
1
(x, y) tourné d'un angle droit est (-y, x) ou (y, -x), selon que vous faites pivoter dans le sens positif ou négatif, respectivement.
starblue
17

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.

Elian Ebbing
la source
2
Ouais. C’est aussi le plus compréhensible et probablement le plus facile à mettre en œuvre.
Eric G
Cela ressemble à une égalité vectorielle de segments. Quelqu'un peut-il s'il vous plaît élaborer ou prouver pourquoi cela fonctionne?
vCillusion
Il échoue spécifiquement pour le cas (0,0), (2,1), (3, -1), (1, -2) - carré non aligné à l'axe
vCillusion
1
Cela fonctionne pour ce cas. Le point central est (1,5, -0,5), le premier point est (0, 0) et trois autres points sont (1,5, -0,5) + (1,5, -0,5) = (3, -1); (1.5, -0.5) + (0.5, 1.5) = (2, 1) et (1.5, -0.5) - (0.5, 1.5) = (1, -2), ce qui signifie que c'est un carré. La preuve est .. symétrie?
aragaer
1
La "solution de distance" a besoin de racines carrées, mais il y a la "solution de distance carrée", qui n'en a pas besoin. Le vôtre sera peut-être encore plus efficace ...
mercredi
5

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.

Pas un carré ...

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:

Et ce n'est pas un carré, aussi ...

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.

woliveirajr
la source
Non, son algorithme dit que les 2 arêtes de distances x ne partagent pas un point. mais vous partagez simplement C. Donc, supposons que AC soit x, alors BD devrait être un autre x au lieu de votre BC.
MarshalSHI
3

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

Mark Salzer
la source
1
Je pense qu'un rectangle peut également satisfaire vos conditions.
MarshalSHI
Non, la première condition n'est pas remplie par les vecteurs orthogonaux, mais de longueur égale.
Mark Salzer
1
Oui, le premier me manque. Mais les 4 points ne sont pas commandés. Donc, nous avons besoin de plus d’étapes, je pense, pour pouvoir confirmer.
MarshalSHI
Oui ... si aucune idée plus intelligente ne se pose, il faudrait boucler. Je pense qu’il faut une boucle extérieure pour calculer w, x, y, z à partir de chaque ordre possible de a, b, c, d et d’une boucle intérieure pour chaque ordre possible du tuple w, x, y, z.
Mark Salzer
2

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

Max
la source
Bonne idée, mais vous devez toujours vérifier que le 4ème sommet est à la bonne distance des autres points. Vous vérifiez seulement que c'est sur la diagonale.
starblue
@starblue droit! Sinon, il peut former un cerf-volant. Mis à jour.
Max
2

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.

GlenPeterson
la source
2

entrez la description de l'image ici

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

Réactionnel
la source
1

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.

bad_keypoints
la source
1
Vous pouvez résumer l'algorithme ici. Vous vous connectez à un autre site SE, ce qui est légèrement mieux que de pointer vers un autre site, mais nous voulons que la réponse soit affichée sur cette page, où la question est posée. Maintenant, les gens doivent cliquer à nouveau pour savoir quelle pourrait être la réponse.
Martijn Pieters
0

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.

Ana Nimbus
la source
0

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

gnasher729
la source
-3

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

singh13
la source