Cómo determinar si 3 puntos son exactamente colineales en Z^2

Question

Otra pregunta de puntos colineales. El giro de esta es, estoy usando la aritmética de enteros, y estoy buscando exacta collinearity, no es una prueba fuzzy basada en epsilon.

Con ensamblado en línea, puedo conseguir una respuesta exacta: la instrucción x86 multiplican da acceso tanto a las partes alta y baja del producto, los cuales son importantes para calcular el producto vectorial (X - Un) x (B - A); Puedo simplemente O las dos mitades juntas y probar cero. Pero espero que hay una manera de hacerlo en C, que es:

1. desbordamiento a prueba de
2. portátil
3. elegante

más o menos en ese orden. Y, al mismo tiempo, una forma de hacerlo que es/no:

1. incluyen fundición a double
2. implicar el uso de un mayor tipo entero - supongo que ya estoy usando el mayor tipo entero disponible para mi componente de coordenadas tipo
3. produce falsos positivos o falsos negativos.

No estoy preocupado por esta cuestión acerca de si X es más allá del segmento AB ; eso es solo cuatro comparaciones poco interesantes.

Mi situación de pesadilla es que tendré que dividir cada componente de coordenadas en dos mitades, y hacer una multiplicación larga explícitamente, solo para poder seguir todas las mitades altas en los productos parciales. (Y luego tener que hacer complemento con-llevar de forma explícita.)

Answer 1

Después de algunas comparaciones y comprobaciones simples, puede obtener 2 pares de números positivos (x1,y1), (x2,y2), que desea verificar si x1*y2==x2*y1.

Puede usar el algoritmo euclidiano para buscar el GCD de x1 y y1, y dividir ambos por el GCM. Haga lo mismo para (x2,y2).Si obtuviste la misma pareja en ambos casos, ambos vectores tienen la misma dirección.

Answer 2

Si tres puntos (a, b, c) son exactamente colineales entonces la siguiente identidad sostiene:

c = a + (a - b) * scalar 

es decir:

c - a = scalar * (a - b) 

Tome el primer componente de (c-a), divídalo por el primer componente de (a-b), guarde ese valor. Luego repite para cada componente posterior, y si alguno de ellos difiere, los puntos no son colineales.

Si desea evitar el uso total de la división de coma flotante (que sería la forma más fácil de hacerlo), tendrá que almacenar la relación y compararla en su lugar.