Dados N puntos en el plano, ¿qué es un algoritmo eficiente para encontrar todos los conjuntos de 3 o más puntos colineales?

Es una buena pregunta El siguiente algoritmo es solo una idea rápida de la solución. Puede reducir aún más la complejidad utilizando el Principio de Optimidad .

Algoritmo:

Paso 1: Almacene las coordenadas de cada punto.
Almacene las coordenadas de píxeles.

Paso 2: Encuentra y almacena todos los ángulos formados por 3 puntos.
Considere un punto, y luego calcule el ángulo formado por él con otros 2 puntos. Haga esto por (N-1) / 2 veces para todos los N puntos.

Paso 3: Verifique los puntos angulados de 180 grados.
En la lista obtenida del paso 2, encuentre puntos que tengan ángulos de 180 grados.
Para cada punto angulado de 180 grados, verifique los ángulos de sus dos puntos extremos. Si uno o ambos puntos extremos también tienen un ángulo de 180 grados, inclúyalos en la línea (de esta manera también puede observar la longitud de las diferentes líneas).

Su complejidad temporal será O (n2)

Hay dos algoritmos para encontrar todo el conjunto de 3 o más puntos colineales.

1) Fuerza bruta (O (N ^ 3))

2) Algoritmo basado en clasificación más rápida (más eficiente)

Algoritmo para un algoritmo basado en clasificación más rápida

pseudocódigo

Considere inicialmente un conjunto de todos los puntos S = {q1, q2, …… qn}

1) Ordene los puntos S. es decir S = {q2, q1, q4 … qn} orden arbitrario

2) Tomemos el punto q como origen (q ∈ S) … es decir (q = q2);

3) Con respecto a q, encuentre la pendiente de {otros puntos} en el plano 2d.

es decir (otros puntos = {S} -q)

4) Ordenar todos los puntos con la pendiente que hacen con respecto a q

5) si hay más de 2 puntos adyacentes juntos de modo que sus pendientes sean iguales con respecto a q, entonces se dice que los puntos adyacentes son colineales al punto q

6) if (! Todos los puntos q se toman como origen)

{

repita del paso 2 al paso 6 tomando q = siguiente q // es decir q = q1;

}más

{

salida (1);

}

Complejidad = O ( N ^ 2 * log N)

El siguiente código contiene la implementación del algoritmo en java

FastCollinearPoints.java

  import java.lang.reflect.Array;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.List;
 import java.util.Stack;

 / **
  * Creado por bhuvan el 01-10-2015.
  * /
 FastCollinearPoints de clase pública {
     Segmento de línea público [] l;
     FastCollinearPoints (puntos [] puntos) públicos // encuentra todos los segmentos de línea que contienen 4 o más puntos
     {
         List  a = new ArrayList <> ();
         Arrays.sort (puntos);
         for (int i = 0; i  firstslopearray = new ArrayList <> ();
             List  secondslopearray = new ArrayList <> ();
             Punto [] aux = puntos.clone ();
             si (i! = 0)
                 Arrays.sort (aux, 0, i-1, aux [i] .SLOPE_ORDER);


             Arrays.sort (aux, i + 1, aux.length, aux [i] .SLOPE_ORDER);

             para (int o = i + 1; o  temp = new ArrayList <> ();
             int cabeza = 0, cola = 0;
             int k = 0;


           //
           while (head  = 2) {



                   // busca duplicados
                   doble pendiente = aux [i] .slopeTo (aux [i + tail + 1]);
                   if (! firstslopearray.contains (pendiente))
                       a.add (nuevo LineSegment (aux [i], aux [i + tail + 1]));

                   // agregarlo al segmento
               }
               cabeza = cola + 1;
               cola = cabeza;
             }

             }
        l = a.toArray (nuevo LineSegment [a.size ()]);
         }

     public int numberOfSegments () // el número de segmentos de línea
     {
         retorno l.length;
     }
     segmentos de línea públicos [] () // los segmentos de línea
     {
         volver l;
     }
     public static void main (String [] args)
     {
         In in = new In ("rs1423.txt");
         int N = in.readInt ();
         Punto [] puntos = nuevo Punto [N];
         para (int i = 0; i 

La transformación de Hough (una transformación de radón simplificada) es la respuesta. Resuelve este problema particular con la complejidad lineal con respecto al número de puntos en el conjunto. Le permite encontrar todos los conjuntos de 2 o más puntos co-lineales. El artículo de Wikipedia lo explica bien, pero si necesita una mejor explicación, no dude en preguntar.