Comprueba la colinealidad entre cuatro puntos que supuestamente construyen un cuadrilátero

Question

Digamos que obtenemos cuatro puntos 2D (llamémoslos $p1$ , $p2$ , $p3$ y $p4$ ) de algún sitio y queremos construir un cuadrilátero (no importa si convexo o no). ¿Cuál es la comprobación óptima de colinealidad para asegurarnos de que realmente es posible definir un cuadrilátero utilizando estos cuatro puntos?

Hasta ahora he estado comprobando utilizando el producto cruzado (como se ve aquí ) para las siguientes tripletas: $collinear(p1, p2, p3)$ , $collinear(p2, p3, p4)$ y $collinear(p3, p4, p1)$ . Si alguno de estos tres $collinear(.,.,.)$ devoluciones de cheques $true$ los puntos no pueden utilizarse para definir un cuadrilátero. ¿Es esto suficiente o tengo que añadir algo más? Ten en cuenta que también compruebo la igualdad entre los cuatro puntos.

Utilizo el siguiente código (en Python 3) para comprobar la colinealidad entre 3 puntos:

Nota: También utilizo $z$ que en mi caso es igual a 0.

@staticmethod
def collinear(p1, p2, p3):
    '''
    Checks if three given points are collinear using cross product
    '''
    # http://www.ambrsoft.com/TrigoCalc/Line3D/LineColinear.htm
    c1 = (p2.y - p1.y)*(p3.z - p1.z) - (p3.y - p1.y)*(p2.z - p1.z)
    c2 = (p3.x - p1.x)*(p2.z - p1.z) - (p2.x - p1.x)*(p3.z - p1.z)
    c3 = (p2.x - p1.x)*(p3.y - p1.y) - (p3.x - p1.x)*(p2.y - p1.y)

    from math import isclose
    return isclose(c1, 0, abs_tol=0.00000001) and isclose(c2, 0, abs_tol=0.00000001) and isclose(c3, 0, abs_tol=0.00000001)

También estoy portando mi código a C++ y encontré un buen artículo sobre colinealidad en Mathworld Wolfram :

bool Triangle::collinear(QVector2D v1, QVector2D v2, QVector2D v3)
{
    return closeEqual((v1.x()*(v2.y() - v3.y()) + v2.x()*(v3.y() - v1.y()) + v3.x()*(v1.y() - v2.y())), 0.0, FUZZY_FACTOR);
}

Answer 1

¿Cuál es la comprobación óptima de la colinealidad para asegurarse de que realmente es posible definir un cuadrilátero utilizando estos cuatro puntos?

No sé si óptimo pero el análogo 2D del producto cruzado (la prueba que OP está utilizando) es probablemente la comprobación más sencilla y robusta de implementar para el cálculo numérico. En detalle, si $\epsilon$ es el mayor valor positivo que se considera cero ( máquina epsilon ), entonces los tres puntos $(x_a, y_a)$ , $(x_b, y_b)$ y $(x_c, y_c)$ son colineales si y sólo si $$\lvert (x_b - x_a)(y_c - y_a) - (x_c - x_a)(y_b - y_a) \rvert \le \epsilon$$ Desde el punto de vista computacional, esto "cuesta" dos multiplicaciones, cinco sustracciones y dos comparaciones o una comparación y una función de valor absoluto; no es mucho.

Si ya se conocen las distancias euclidianas entre los puntos, entonces desigualdad triangular podría utilizarse. Sin embargo, la operación de raíz cuadrada suele ser mucho más costosa ("lenta") computacionalmente que la multiplicación, y la desigualdad no se cumple para longitudes al cuadrado, por lo que no resulta muy atractiva para este caso concreto, en el que sólo conocemos las coordenadas de los puntos.

[¿Son suficientes mis cheques o tengo que añadir algo más?

Hay cuatro formas de elegir tres de los cuatro artículos únicos (véase coeficiente binomial en Wikipedia): $$4 \text{ choose } 3 = \binom{4}{3} = 4$$ Esto significa que si tienes cuatro puntos, necesitas cuatro pruebas para verificar que no hay tres de ellos colineales.

En otras palabras, comprobar collinear(p1,p2,p3) , collinear(p2,p3,p4) y collinear(p1,p3,p4) no es suficiente -- no se da el caso de que los puntos 1,2 y 4 sean colineales -- y también hay que comprobar si collinear(p1,p2,p4) .

La prueba mencionada anteriormente también detectará el caso en que dos o más puntos se encuentren en las mismas coordenadas, por lo que no es necesario comprobar la igualdad.

He aquí un ejemplo de la prueba en pseudocódigo. Devuelve Verdadero si al menos tres de los cuatro puntos son colineales:

Function Collinear3of4(p1, p2, p3, p4, eps=0.0000005):
    # (p1, p2, p3) are collinear if and only if
    #     abs( (p2.x-p1.x)*(p3.y-p1.y) - 
    #          (p3.x-p1.x)*(p2.y-p1.y) ) <= eps 
    (x12, y12) = (p2.x - p1.x, p2.y - p1.y)
    (x13, y13) = (p3.x - p1.x, p3.y - p1.y)
    (x14, y14) = (p4.x - p1.x, p4.y - p1.y)
    (x23, y23) = (p3.x - p2.x, p3.y - p2.y)
    (x24, y24) = (p4.x - p2.x, p4.y - p2.y)
    # Test each unique triplet.
    # 4 choose 3 = 4 triplets: 123, 124, 134, 234
    Return ( (Abs(x12*y13-x13*y12) < eps) Or
             (Abs(x12*y14-x14*y12) < eps) Or
             (Abs(x13*y14-x14*y13) < eps) Or
             (Abs(x23*y24-x24*y23) < eps) )

En C, las variables temporales podrían/deberían considerarse una optimización prematura, ya que el compilador debería ser capaz de realizar las optimizaciones correspondientes de forma automática. En Python, el acceso a miembros es más lento que el acceso a variables locales y la documentación recomienda usar variables temporales en lugar de accesos repetidos a miembros, por lo que las variables temporales están justificadas -- no para reducir el número de restas, sino para usar variables locales en lugar de accesos a miembros. En C++, las variables temporales están justificadas si los miembros son funciones (como en los tipos puntuales de Qt); de lo contrario, la optimización es prematura. (En realidad, los compiladores de C++ deberían ser capaces de optimizar incluso las llamadas a funciones miembro, si son getters puros).

De hecho, personalmente sólo aceptaría una versión de la función si tiene comentarios que dejen claras las matemáticas que implementa, y, si utiliza alguna, las variables temporales están bien nombradas .

Si las variables temporales se denominaran, por ejemplo xA , yA y así sucesivamente, sería casi imposible saber si la parte matemática es correcta o no. Con estos nombres, se puede comprobar fácilmente si los cuatro conjuntos (123, 124, 134, 234) están cubiertos.

Todo esto nos remite a óptimo Ya ves. Valoro la robustez y la mantenibilidad: No quiero, ni intento nunca, recordar ningún detalle del código que escribí hace un año, un mes o incluso una semana. Quiero que el código me diga lo que hace, y que los comentarios me digan por qué lo hace, y cuál es el propósito del código.

(No, mis comentarios no son ni de lejos tan buenos como me gustaría, y es una de las cosas en las que tengo que trabajar yo mismo).