rectangulo - problemas de cuadriláteros en el plano coordenado

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

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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 comprobar 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;
}

Answer 4

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 programación en C, pero aquí hay una programació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 (v.u/|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 suma 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}

Answer 5

struct point
{
    int x, y;
}

// tests if angle abc is a right angle
int IsOrthogonal(point a, point b, point c)
{
    return (b.x - a.x) * (b.x - c.x) + (b.y - a.y) * (b.y - c.y) == 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);
}

Answer 6

• 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 ángulos opuestos de un paralelogramo son iguales
• ángulos consecutivos de un paralelogramo son suplementarios
• por lo tanto, todos los ángulos son ángulos 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)

Answer 7

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