encontrar si 4 puntos en un plano forman un rectángulo?

9 minutos de lectura

avatar de usuario
pete

¿Puede alguien mostrarme en pseudocódigo de estilo C cómo escribir una función (representar los puntos como quieras) que devuelva verdadero si 4 puntos (argumentos de la función) forman un rectángulo y falso de lo contrario?

Se me ocurrió una solución que primero intenta encontrar 2 pares distintos de puntos con el mismo valor de x, luego hace esto para el eje y. Pero el código es bastante largo. Solo curiosidad por ver qué se les ocurre a los demás.

  • ¿Se te ocurrió la solución? ¿Dónde está? Puede mostrarlo aquí y podemos ayudarlo a hacerlo más corto y más limpio.

    – Milan Babuškov

    20 de febrero de 2010 a las 19:05

  • Interesante pregunta. Noté que su solución solo funcionará si el rectángulo es paralelo al eje.

    – Christian Madsen

    20 de febrero de 2010 a las 19:09

  • Gman – sí en cualquier orden. Milán: esto me lo pidieron durante una entrevista, así que no tengo mi código (no necesariamente necesito ver el código… ¡un algoritmo también sería genial!). Christian: buen punto sobre que tiene que ser paralelo al eje.

    – pete

    20 de febrero de 2010 a las 19:11

avatar de usuario
Cuajada

  • encuentre el centro de masa de los puntos de esquina: cx=(x1+x2+x3+x4)/4, cy=(y1+y2+y3+y4)/4
  • probar si el cuadrado de las distancias desde el centro de masa hasta 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, las pruebas de igualdad de dos números de coma flotante a y b deben realizarse con una precisión finita: p. ej., abs(ab) < 1E-6)

  • Esta es una solución inteligente. Básicamente, encuentra el círculo circunscrito del “rectángulo” y verifica que las cuatro esquinas estén sobre él.

    – rlbond

    20 de febrero de 2010 a las 23:03

  • Esto es MUY ineficiente. Usa el método del producto escalar proporcionado por Vlad. Las raíces cuadradas necesitan cientos de ciclos de reloj. Además, el método del producto escalar es más estable numéricamente.

    – Axel Gneiting

    20 de febrero de 2010 a las 23:33


  • @Axel & @Curd: ¿Se editó la solución desde su publicación original? No veo raíces cuadradas. Estoy asumiendo sqr(x) == x*x lo que significa ddi es en realidad el cuadrado de la distancia desde cx para xi. Esto debería ser bastante rápido.

    – Brett Pontarelli

    21 de febrero de 2010 a las 4:46

  • Bien, entonces necesito disculparme. Pensé que sqr significa raíz cuadrada.

    – Axel Gneiting

    21 de febrero de 2010 a las 17:46

  • Algunas consideraciones sobre el rendimiento: esta solución requiere 20 sumas/restas/divisiones por constantes 4 y 8 multiplicaciones. Incluso podría optimizarse para descartar los cálculos de distancia cuadrada restantes si la primera o la segunda comparación fallan. Entonces, los números anteriores son el peor de los casos. Incluso este peor caso es tan bueno como el mejor caso y 3 veces mejor que el peor caso de la solución de Vlad.

    – Cuajada

    21 de febrero de 2010 a las 22:21


avatar de usuario
Vlad

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

  • @Larry: tu prueba es solo por ser un paralelogramo

    – Vlad

    20 de febrero de 2010 a las 19:15

  • @Larry: ahora es correcto verificar las diagonales, pero su prueba requiere tomar 6 raíces cuadradas.

    – Vlad

    20 de febrero de 2010 a las 19:22

  • @Timmy: en ese caso, hay que hacer una verificación más complicada: if (IsOrthogonal(a, b, c)) return IsRectangle(a, b, c, d); else if (IsOrthogonal(a, b, d)) return IsRectangle(a, b, d, c); else return false;

    – Vlad

    20 de febrero de 2010 a las 19:28

  • Modifiqué la respuesta en consecuencia.

    – Vlad

    20 de febrero de 2010 a las 19:32

  • IsOrthogonal( (10,9), (15,9), (15,6) ) = 0 o Falso. (15-10)*(15-15)+(9-9)*(9-6)=0. Hay un ! ¿desaparecido?

    – Harvey

    20 de febrero de 2010 a las 19:47


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 poco de magia.

Propiedades del rectángulo en juego

  1. Los lados opuestos y las diagonales de un rectángulo tienen la misma longitud.
  2. Si la longitud de la diagonal de un rectángulo es sqrt(2) por cualquiera de sus longitudes, entonces el rectángulo es un cuadrado.

poco de magia

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

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

  • buena idea pero posiblemente poco práctica si necesita probar la igualdad con una pequeña tolerancia para tener en cuenta la precisión de la flotación. probablemente también valga la pena agregar que el truco xor funciona porque xor es conmutativo y asociativo

    – Ed Bordin

    3 de abril de 2019 a las 0:23


  • 4.b. ¿Por qué no comprobar si las 4 distancias son iguales?

    – diegoide

    11 de agosto de 2019 a las 1:37

  • trasladar el cuadrilátero para que uno de sus vértices ahora se encuentre en el origen
  • los tres puntos restantes forman tres vectores desde el origen
  • uno de ellos debe representar la diagonal
  • los otros dos deben representar los lados
  • por el regla del paralelogramo si los lados forman la diagonal tenemos un paralelogramo
  • si los lados forman un angulo recto, es un paralelogramo con un angulo recto
  • los ángulos opuestos de un paralelogramo son iguales
  • los angulos consecutivos de un paralelogramo son suplementarios
  • por lo tanto todos los angulos son angulos rectos
  • es un rectángulo
  • aunque 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 punto flotante, por favor, no reemplace ciegamente el En t declaraciones en los encabezados. Es una mala práctica. Están ahí por una razón. Siempre se debe trabajar con algún límite superior en el error al comparar resultados de punto flotante).

avatar de usuario
Carlos Gutiérrez

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

  • @andras: probé algunos paralelogramos y todos se evaluaron como falsos. ¿Estás pensando en un caso en particular?

    – Carlos Gutiérrez

    21 de febrero de 2010 a las 21:48


  • Supongamos que tenemos puntos x1=3, y1=3; x2=0, y2=0; x3=6, y3=0; x4=9, y4=3; Ahora d1 = 18; d2 = 18; d3 = 36; Aunque se está haciendo tarde. 🙂 ¿Podría comprobarlo?

    –Andras Vass

    21 de febrero de 2010 a las 22:35

  • @andras: tiene razón, parece que la prueba debe repetirse usando 3 de los puntos como punto de inicio.

    – Carlos Gutiérrez

    21 de febrero de 2010 a las 23:09

  • por favor, haz algo al respecto entonces.

    –Andras Vass

    28 de febrero de 2010 a las 0:13

  • esto está mal, la última línea debe ser d1^2 == d2^2+d3^2 o d2^2 == d1^2 + d3^2 o d3^2 == d1^2 + d2 ^2

    – Masud Darzi

    23 de enero de 2021 a las 6:55

avatar de usuario
Axel Gneiting

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 toma los productos punto (x punto y), (y punto z), (z punto w) y (w punto x). Si todos son cero, entonces tienes un rectángulo.

  • @andras: probé algunos paralelogramos y todos se evaluaron como falsos. ¿Estás pensando en un caso en particular?

    – Carlos Gutiérrez

    21 de febrero de 2010 a las 21:48


  • Supongamos que tenemos puntos x1=3, y1=3; x2=0, y2=0; x3=6, y3=0; x4=9, y4=3; Ahora d1 = 18; d2 = 18; d3 = 36; Aunque se está haciendo tarde. 🙂 ¿Podría comprobarlo?

    –Andras Vass

    21 de febrero de 2010 a las 22:35

  • @andras: tiene razón, parece que la prueba debe repetirse usando 3 de los puntos como punto de inicio.

    – Carlos Gutiérrez

    21 de febrero de 2010 a las 23:09

  • por favor, haz algo al respecto entonces.

    –Andras Vass

    28 de febrero de 2010 a las 0:13

  • esto está mal, la última línea debe ser d1^2 == d2^2+d3^2 o d2^2 == d1^2 + d3^2 o d3^2 == d1^2 + d2 ^2

    – Masud Darzi

    23 de enero de 2021 a las 6:55

avatar de usuario
manufactura1

Sabemos que dos rectas rectas son perpendiculares si el producto de sus pendientes es -1, dado que se da un plano podemos encontrar las pendientes de tres rectas consecutivas y luego multiplicarlas para comprobar si realmente son 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 pendiente de m(L1)*m(L2)=-1 y m(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;
}

  • Creo que esto es computacionalmente el más eficiente.

    – milesmiau

    21 de febrero de 2010 a las 7:50

  • También debe verificar m4, de lo contrario, puede terminar con un trapezoide.

    –Andras Vass

    21 de febrero de 2010 a las 11:56

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad