¿encuentra si 4 puntos en un plano forman un rectángulo?

¿Alguien puede mostrarme en pseudocódigo de estilo C cómo escribir una función (representar los puntos como quiera) que devuelve verdadero si 4 puntos (args a la función) forman un rectángulo y de lo contrario es falso?

Se me ocurrió una solución que primero trata de encontrar 2 pares distintos de puntos con el mismo valor x, y luego hace esto para el eje y. Pero el código es bastante largo. Solo curiosidad por ver lo que otros piensan.

  • encuentre el centro de masa de los puntos de esquina: cx = (x1 + x2 + x3 + x4) / 4, cy = (y1 + y2 + y3 + y4) / 4
  • prueba si el cuadrado de distancias desde el centro de masa a las 4 esquinas es igual
bool isRectangle(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) { double cx,cy; double dd1,dd2,dd3,dd4; cx=(x1+x2+x3+x4)/4; cy=(y1+y2+y3+y4)/4; dd1=sqr(cx-x1)+sqr(cy-y1); dd2=sqr(cx-x2)+sqr(cy-y2); dd3=sqr(cx-x3)+sqr(cy-y3); dd4=sqr(cx-x4)+sqr(cy-y4); return dd1==dd2 && dd1==dd3 && dd1==dd4; } 

(Por supuesto, en la práctica, la prueba para la igualdad de dos números en coma flotante a y b debe hacerse con precisión finita, por ejemplo, abs (ab) <1E-6)

 struct point { int x, y; } // tests if angle abc is a right angle int IsOrthogonal(point a, point b, point c) { return (bx - ax) * (bx - cx) + (by - ay) * (by - cy) == 0; } int IsRectangle(point a, point b, point c, point d) { return IsOrthogonal(a, b, c) && IsOrthogonal(b, c, d) && IsOrthogonal(c, d, a); } 

Si el pedido no se conoce de antemano, necesitamos una verificación un poco más complicada:

 int IsRectangleAnyOrder(point a, point b, point c, point d) { return IsRectangle(a, b, c, d) || IsRectangle(b, c, a, d) || IsRectangle(c, a, b, d); } 
  • traduce el cuadrilátero para que uno de sus vértices ahora se encuentre en el origen
  • los tres puntos restantes forman tres vectores del origen
  • uno de ellos debe representar la diagonal
  • los otros dos deben representar los lados
  • por la regla del paralelogramo si los lados forman la diagonal, tenemos un paralelogramo
  • si los lados forman un ángulo recto, es un paralelogramo con un ángulo recto
  • los angularjs opuestos de un paralelogramo son iguales
  • angularjs consecutivos de un paralelogramo son suplementarios
  • por lo tanto, todos los angularjs son angularjs rectos
  • es un rectángulo
  • sin embargo, es mucho más conciso en el código 🙂

     static bool IsRectangle( int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) { x2 -= x1; x3 -= x1; x4 -= x1; y2 -= y1; y3 -= y1; y4 -= y1; return (x2 + x3 == x4 && y2 + y3 == y4 && x2 * x3 == -y2 * y3) || (x2 + x4 == x3 && y2 + y4 == y3 && x2 * x4 == -y2 * y4) || (x3 + x4 == x2 && y3 + y4 == y2 && x3 * x4 == -y3 * y4); } 
  • (Si desea que funcione con valores de coma flotante, no reemplace ciegamente las declaraciones int en los encabezados. Es una mala práctica. Están ahí por una razón. Siempre se debe trabajar con un límite superior en el error cuando se comparan resultados de puntos flotantes)

La distancia de un punto a los otros 3 debe formar un triángulo rectángulo:

 |  / / |
 |  / / |
 |  / / |
 | / ___ / ___ |
 d1 = sqrt( (x2-x1)^2 + (y2-y1)^2 ) d2 = sqrt( (x3-x1)^2 + (y3-y1)^2 ) d3 = sqrt( (x4-x1)^2 + (y4-y1)^2 ) if d1^2 == d2^2 + d3^2 then it's a rectangle 

Simplificando:

 d1 = (x2-x1)^2 + (y2-y1)^2 d2 = (x3-x1)^2 + (y3-y1)^2 d3 = (x4-x1)^2 + (y4-y1)^2 if d1 == d2+d3 or d2 == d1+d3 or d3 == d1+d2 then return true 

Si los puntos son A, B, C y D y conoce el orden, entonces calcula los vectores:

x = BA, y = CB, z = DC y w = AD

Luego tome los productos de puntos (x punto y), (y punto z), (z punto w) y (w punto x). Si son todos cero, entonces tienes un rectángulo.

Sabemos que dos líneas de estrella son perpendiculares si el producto de sus pendientes es -1, dado que se da un plano, podemos encontrar las pendientes de tres líneas consecutivas y luego multiplicarlas para verificar si son realmente perpendiculares o no. Supongamos que tenemos las líneas L1, L2, L3. Ahora bien, si L1 es perpendicular a L2 y L2 perpendicular a L3, entonces es un rectángulo y una pendiente de m (L1) * m (L2) = – 1 ym (L2) * m (L3) = – 1, entonces implica que es un rectángulo. El código es el siguiente

 bool isRectangle(double x1,double y1, double x2,double y2, double x3,double y3, double x4,double y4){ double m1,m2,m3; m1 = (y2-y1)/(x2-x1); m2 = (y2-y3)/(x2-x3); m3 = (y4-y3)/(x4-x3); if((m1*m2)==-1 && (m2*m3)==-1) return true; else return false; } 

llevando la sugerencia del producto punto un paso más allá, verifica si dos de los vectores hechos por cualquiera de los 3 puntos de los puntos son perpendiculares y luego observa si xey coinciden con el cuarto punto.

Si tienes puntos [Axe, Ay] [Bx, By] [Cx, Cy] [Dx, Dy]

vector v = vector BA u = CA

v (punto) u / | v || u | == cos (theta)

Entonces, si (vu == 0) hay un par de líneas perpendiculares allí.

En realidad, no conozco la progtwigción en C, pero aquí hay una progtwigción “meta” para ti: P

 if (v==[0,0] || u==[0,0] || u==v || D==A) {not a rectangle, not even a quadrilateral} var dot = (v1*u1 + v2*u2); //computes the "top half" of (vu/|v||u|) if (dot == 0) { //potentially a rectangle if true if (Dy==By && Dx==Cx){ is a rectangle } else if (Dx==Bx && Dy==Cy){ is a rectangle } } else {not a rectangle} 

no hay raíces cuadradas en esto, y no hay posibilidad de una división por cero. Noté que la gente menciona estos problemas en publicaciones anteriores, así que pensé en ofrecer una alternativa.

Entonces, computacionalmente, necesita cuatro restas para obtener v y u, dos multiplicaciones, una sum y debe verificar en algún lugar entre 1 y 7 equivalencias.

tal vez estoy inventando esto, pero recuerdo vagamente haber leído en alguna parte que las restas y las multiplicaciones son cálculos “más rápidos”. Supongo que declarar variables / matrices y establecer sus valores también es bastante rápido.

Lo siento, soy bastante nuevo en este tipo de cosas, así que me gustaría recibir algunos comentarios sobre lo que acabo de escribir.

Editar: prueba esto en base a mi comentario a continuación:

 A = [a1,a2]; B = [b1,b2]; C = [c1,c2]; D = [d1,d2]; u = (b1-a1,b2-a2); v = (c1-a1,c2-a2); if ( u==0 || v==0 || A==D || u==v) {!rectangle} // get the obvious out of the way var dot = u1*v1 + u2*v2; var pgram = [a1+u1+v1,a2+u2+v2] if (dot == 0 && pgram == D) {rectangle} // will be true 50% of the time if rectangle else if (pgram == D) { w = [d1-a1,d2-a2]; if (w1*u1 + w2*u2 == 0) {rectangle} //25% chance else if (w1*v1 + w2*v2 == 0) {rectangle} //25% chance else {!rectangle} } else {!rectangle} 
 1. Find all possible distances between given 4 points. (we will have 6 distances) 2. XOR all distances found in step #1 3. If the result after XORing is 0 then given 4 points are definitely vertices of a square or a rectangle otherwise, return false (given 4 points do not form a rectangle). 4. Now, to differentiate between square and rectangle a. Find the largest distance out of 4 distances found in step #1. b. Check if the largest distance / Math.sqrt (2) is equal to any other distance. c. If answer is No, then given four points form a rectangle otherwise they form a square. 

Aquí, estamos usando propiedades geométricas de rectángulo / cuadrado y Bit Magic .

Propiedades de rectángulo en juego

  1. Los lados opuestos y las diagonales de un rectángulo son de igual longitud.
  2. Si la longitud diagonal de un rectángulo es sqrt (2) veces cualquiera de su longitud, entonces el rectángulo es un cuadrado.

Bit Magic

  1. Los números de valor igual a XORing devuelven 0.

Como las distancias entre 4 esquinas de un rectángulo siempre formarán 3 pares, uno para diagonal y dos para cada lado de diferente longitud, XORing todos los valores devolverá 0 para un rectángulo.

¿Qué tal si verificamos esos 4 puntos para formar un paralelogramo primero y luego averiguar si existe un ángulo recto ?
1. verificar el paralelogramo

input 4 points A, B, C, D;

if(A, B, C, D are the same points), exit;// not a rectangle;

else form 3 vectors, AB, AC, AD, verify(AB=AC+AD || AC=AB+AD || AD=AB+AC), \\if one of them satisfied, this is a parallelogram;

2. verificar un ángulo recto

through the last step, we could find which two points are the adjacent points of A;

We need to find out if angle A is a right angle, if it is, then rectangle.

No sabía si existen errores. Por favor averígualo si hay.