¿Cómo verificar si 4 puntos forman un cuadrado?

Suponga que tengo 4 puntos (son de 2 dimensiones), que son diferentes entre sí, y quiero saber si forman un cuadrado. ¿Cómo hacerlo? (deje que el proceso sea lo más simple posible)

Suponiendo que su cuadrado pueda rotarse contra cualquier sistema de coordenadas que tenga en su lugar, no puede confiar en que haya una repetición de los valores X e Y en sus cuatro puntos.

Lo que puede hacer es calcular las distancias entre cada uno de los cuatro puntos. Si encuentra que lo siguiente es cierto, tiene un cuadrado:

1. Hay dos puntos, digamos A y C, que son la distancia x entre sí, y otros dos puntos, digamos B y D, que también son la distancia x entre sí.

2. Cada punto {A, B, C, D} está a la misma distancia de los dos puntos que no están x . es decir: si A está x lejos de C, entonces estará z lejos de B y D.

Por cierto, la distancia z tendrá que ser SQRT (( x ^ 2) / 2), pero no necesita confirmar esto. Si las condiciones 1 y 2 son verdaderas, entonces tienes un cuadrado. NOTA: Algunas personas están preocupadas por la ineficiencia de la raíz cuadrada. No dije que debías hacer este cálculo, ¡solo dije que si lo hicieras obtendrías un resultado predecible!

El mínimo trabajo que necesitaría hacer sería elegir un punto, decir A y calcular la distancia a cada uno de los otros tres puntos. Si puede encontrar que A es x desde un punto y z desde otros dos puntos, entonces solo necesita verificar esos otros dos puntos uno contra el otro. Si también son x entre sí, entonces tienes un cuadrado. es decir:

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

Como AB = AD, verifique BD:

• BD = x

Solo para estar seguro, debe verificar los otros lados: BC y CD.

• BC = z
• CD = z

Como AC = BD y como AB = AD = BC = CD, este es, por lo tanto, un cuadrado.

En el camino, si encuentra más de dos distancias de borde distintas, la figura no puede ser un cuadrado, por lo que puede dejar de mirar.

Implementación de ejemplo de trabajo

He creado un ejemplo de trabajo en jsfiddle (ver aquí ). En mi explicación del algoritmo, utilizo los puntos arbitrarios A, B, C y D. Esos puntos arbitrarios están en cierto orden por el simple hecho de caminar por el ejemplo. El algoritmo funciona incluso si los puntos están en un orden diferente, sin embargo, el ejemplo no necesariamente funciona si esos puntos están en un orden diferente.

Gracias a: meshuai, Blrfl, MSalters y Bart van Ingen Schenau por sus útiles comentarios para mejorar esta respuesta.

Elige tres de los cuatro puntos.

Averigua si es un triángulo isósceles recto comprobando si uno de los tres vectores entre puntos es igual a otro girado 90 grados.

Si es así, calcule el cuarto punto mediante la suma de vectores y compárelo con el cuarto punto dado.

Tenga en cuenta que esto no requiere raíces cuadradas caras, ni siquiera la multiplicación.

Creo que la solución más fácil es la siguiente:

• Primero, calcule el centro de los 4 puntos: center = (A + B + C + D)/4

• Luego calcula el vector A - center. Deja que esto seav := (x,y)

• Deje v2ser el vector vgirado 90 grados:v2 := (-y, x)

• Ahora los otros puntos deberían ser center - v, center + v2y center - v2.

La ventaja de esta solución es que no tiene que usar raíces cuadradas en absoluto.

Lo siento pero algunas respuestas no aplican.

Para el caso, mide 3 bordes (digamos AB, AC y AD) para encontrar que dos tienen el mismo tamaño (digamos AC y AD) y uno es más grande (digamos AB). Luego medirías el CD para ver si es del mismo tamaño de AB, y descubrirás que lo es. En lugar de un cuadrado, podría tener la imagen a continuación, y eso la convierte en una solución incorrecta.

Luego intente alguna otra solución: mida todas las distancias al menos una vez: AB, AC, AD, BC, BD, CD. Entonces descubres que 4 de ellos son iguales, y los otros 2 también son iguales entre sí. Pero podría tener una imagen como la siguiente:

Entonces, esas respuestas no son correctas, a pesar de los altos votos que recibieron.

Una posible solución: si las dos medidas iguales no conectan el mismo punto. Entonces: si AB y CD son de la misma longitud, todas las otras combinaciones (AC, AD, BC, BD) también son iguales, tienes un cuadrado. Si tiene el mismo punto haciendo la mayor longitud (AB y AC es la mayor, y todas las demás son iguales), tiene una de las imágenes de arriba.

Deje que los cuatro puntos tengan vectores de coordenadas a, b, c, d.

Entonces llamemos a sus diferencias w = (ad), x = (ba), y = (cb), z = (dc).

Entonces w es ortogonal a a si puede crear w a partir de una rotación de 90 grados. Matemáticamente, la matriz de rotación de 90 grados en 2 espacios es ((0, -1), (1, 0)). Por lo tanto, la condición de si w es un giro de 90 grados resulta en

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

Si esto se cumple, entonces debe verificar que w == -y yx == -z, o

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

Si esas tres relaciones se mantienen, a, b, c, d forman un cuadrado orientado.

Similar a la respuesta de starblue

Elige cualquiera de los cuatro puntos.

Busque un vértice en ángulo recto entre ellos : al verificar si el producto escalar de cualquiera de los dos vectores es cero. Si no se encuentra, no es un cuadrado.

Comprueba si los vértices adyacentes a este ángulo también están en ángulo recto. Si no, no es un cuadrado.

Compruebe si las diagonales son perpendiculares : si el producto escalar de los vectores entre el primer y cuarto vértice y los otros dos vértices (diagonales) es cero, entonces es un cuadrado.

Creo que puedes hacer esto con una simple suma y resta y encontrando min / max. Términos (coincide con el diagrama de otras personas):

• Punto con el valor y más alto => A
• mayor x => B
• menor y => C
• más bajo x => D

Si 4 puntos comparten solo 2 x valores y 2 y valores, tiene un cuadrado de nivel.

De lo contrario, tiene un cuadrado si sus puntos satisfacen lo siguiente:

• Hacha + Cx = Bx + Dx
• Ay + Cy = Por + Dy
• Ay - Cy = Bx - Dx

Explicación: Los segmentos de línea AC y BD deben encontrarse en sus puntos medios. Así (Ax + Cx) / 2 es el punto medio de AC y (Bx + Dx) / 2 es el punto medio de BD. Multiplique cada lado de esta ecuación por 2 para obtener mi primera ecuación. La segunda ecuación es la misma para los valores Y. Las formas de diamante (romboides) satisfarán estas propiedades, por lo que debe verificar que tenga lados iguales, que el ancho sea el mismo que la altura. Esa es la tercera ecuación.

Aquí hay algunas buenas respuestas, pero la pregunta solicitó el enfoque más simple. Pensé un poco en esto y así es como lo haría.

Puedes saber si cuatro puntos representan un cuadrado (incluso si están rotados), pero calculando el promedio de los cuatro puntos.

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

Una vez que tenga el promedio, la distancia entre cada punto y el promedio debería ser la misma para los cuatro puntos.

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

EDITAR:

Mi error. Eso solo te diría si los puntos del formulario estuvieran en un círculo. Si también verifica la distancia entre puntos, entonces debe ser un cuadrado.

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"

Esto supone que los puntos A, B, C, D no se cruzan (ya que tienen un orden de bobinado válido).

esta no es una respuesta de acuerdo con los estándares establecidos, pero espero que esto ayude:

[Copiado del siguiente enlace para que no tenga que abrir el enlace] Python 76 caracteres

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

La función S toma una lista de números complejos como su entrada (A). Si conocemos el centro y una esquina de un cuadrado, podemos reconstruir el cuadrado girando la esquina 90,180 y 270 grados alrededor del punto central (c). En el plano complejo, la rotación de 90 grados sobre el origen se realiza multiplicando el punto por i. Si nuestra forma original y el cuadrado reconstruido tienen los mismos puntos, entonces debe haber sido un cuadrado.

Esto fue tomado de: Determinar si 4 puntos forman un cuadrado

Si le gusta la respuesta, le digo, tómese un momento para agradecerle a la persona o vote por su respuesta en esa página.

Idea básica (esto responde a la pregunta de si estaba aportando algo nuevo, que fue preguntado por el bot cuando hice clic para proporcionar una respuesta):

• un rombo con diagonales iguales es un cuadrado.
• "lo más simple posible" incluye:
  • sin división,
  • sin raíces cuadradas,
  • sin ramificaciones,
  • sin buscar,
  • sin verificación de ángulo o compra,
  • sin vectores,
  • sin transformaciones,
  • sin números complejos,
  • sin funciones multilínea, y
  • sin importar paquetes especiales (use solo cosas integradas).
  • (¡Y sin enredos imperiales!)

Mi solución en R se presenta a continuación. Supongo que hay exactamente cuatro puntos y que, según el enunciado del problema, ya se ha determinado que los puntos son únicos.

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

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

Vea los trabajos de Norman Wildberger, especialmente sus videos de YouTube ( Pescado real, números reales, trabajos reales, etc.) y su libro Divine Proportions para una discusión sobre "cuadrante".

xyse refiere a una especie de matriz aceptado por de R plot, pointsy linesfunciones.

La aplicación de as.data.framees un truco para hacer que R haga cosas en columnas.

La optional=Tcláusula elimina los nombres, que de todos modos no se usan.

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

Esta es una función para calcular los cuadrantes entre los puntos especificados, donde el i2argumento especifica pares de puntos . El i2símbolo se refiere a una matriz de índice que tiene una columna por índice y 2 elementos por columna (el mismo tipo de matriz devuelta por la combnfunción).

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

El .whichse presenta como un argumento simplemente para exponerlo formalse intentar comunicar lo que está sucediendo.

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
}

Dije que "simple" no incluía funciones multilínea. Tendrás que disculpar esta función de dos líneas.

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

Tenga en cuenta que las primeras cuatro funciones son útiles por derecho propio, aparte de la pregunta sobre los cuatro puntos.

Suponga cuatro puntos A = (ax, ay), B = (bx, by), C = (cx, cy), D = (dx, dy), y forman los puntos de un cuadrado en orden antihorario. Movimos los puntos para que A esté en (0, 0) restando ax de bx, cx y dx, y restando ay de by, cy y dy, estableciendo ax = ay = 0.

Si los puntos son exactamente las esquinas de un cuadrado en orden antihorario, entonces dados A y B, podemos calcular dónde están C y D: Deberíamos tener (cx, cy) = (bx - by, bx + by) y (dx, dy) = (-by, bx). Entonces calculamos la distancia al cuadrado desde donde están C y D, hasta donde deberían estar: errC = (cx - bx + by) ^ 2 + (cy - bx - by) ^ 2, y errD = (dx + by) ^ 2 + (dy - bx) ^ 2. Agregamos estos y dividimos entre (bx ^ 2 + por ^ 2), dando err = (errC + errD) / (bx ^ 2 + por ^ 2).

El resultado err sería 0 si un cuadrado perfecto, o un número pequeño si es casi un cuadrado, y el número permanecería sin cambios, excepto por errores de redondeo si traducimos, escalamos o giramos los puntos del cuadrado. Entonces podemos usar err para decidir qué tan bueno es un cuadrado que tenemos.

Pero no sabemos el orden de los puntos. B y D deben estar a la misma distancia de A; si multiplicamos esto por la raíz cuadrada de 2, esa debería ser la distancia de A a C. Usamos esto para determinar qué punto es C: Calcular distB = bx ^ 2 + por ^ 2, distD = dx ^ 2 + dy ^ 2. Si distD ≥ 1.5 distB, entonces intercambiamos C y D; si distB ≥ 1.5 distD, intercambiamos C y B. Ahora C tiene razón.

También podemos averiguar qué puntos son B y D: si adivinamos cuál es B y cuál es D, nuestro cálculo coloca a D en el lugar completamente incorrecto, exactamente opuesto a donde está. Entonces, si errD ≥ (bx ^ 2 + por ^ 2), entonces intercambiamos B y D.

Esto organizará B, C y D correctamente si tenemos un cuadrado de hecho o al menos aproximadamente un cuadrado. Pero si ni siquiera tenemos aproximadamente un cuadrado, sabemos que el cálculo del error al final lo mostrará.

Resumen:

1. Resta ax de bx, cx, dx. Resta ay de by, cy, dy.
2. Deje distB = bx ^ 2 + por ^ 2, distD = dx ^ 2 + dy ^ 2.
3. Si distD ≥ 1.5 * distB, intercambie C y D y calcule distD nuevamente.
4. De lo contrario, si distB ≥ 1.5 * distD, intercambie B y C y calcule distB nuevamente.
5. Sea errD = (dx + by) ^ 2 + (dy - bx) ^ 2.
6. Si errD ≥ distB intercambie B y D, intercambie distB y distD, calcule errD nuevamente.
7. Sea errC = (cx - bx + by) ^ 2 + (cy - bx - by) ^ 2.
8. Deje err = (errC + errD) / distB.
9. Decide si tenemos un cuadrado o casi un cuadrado dependiendo del valor de err.

Si conocemos el orden de los puntos, esto obviamente puede simplificarse.

La solución es similar a los medios de pensamiento.

Primer paso:

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

A esta propiedad le sigue el cuadrado porque es cíclico. ahora un círculo para seguir esta propiedad. así que ahora solo revisa

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

if (f==1)
  square
else 
  not square

Aquí AB significa producto de puntos de A y B