Heurístico para ordenar puntos

[swapd0]

Llevo unos dias un poco espesos y no doy con la tecla.

Tengo un conjunto de puntos sin ordenar, y necesito ordenarlos para formar una polilinea con ellos. En la siguiente captura se pueden ver los puntos y una ordenacion por ángulo (arriba) y otra por mi algoritmo abajo.

44215

El problema viene cuando le meto un ejemplo mas "real", sacando los puntos de secciones de nubes de puntos hechas por esferas que sale esta mierda, incluso hay veces que no saca ni un solo circulo y se para antes.
44216

El algoritmo mio funciona asi:
- Se quitan los puntos repetidos (dan muchos problemas)
- Se calcula el diagrama de voronoi con los puntos
- Calculo un grafo usando el diagrama de voronoi donde tendre de cada punto aristas con la distancia a los puntos vecinos.
- Busco la arista mas corta y la meto en la solución
- Cojo los extremos de la solución y cojo entre los vértices adyacentes (a la cabeza y la cola) con el que este mas cerca y tenga que girar menos según la dirección que lleve. Marco este vértice como usado.
- Repito hasta que no encuentro un vértice adyacente libre

Alguna idea para mejorarlo, ¿y para que no se pase al circulo vecino? Puede que sea mejor primero separar los puntos en grupos y despues ordenarlos porque de esa forma va bien (como en la primera captura), ¿alguna idea de como separar los grupos?.

-----Actualizado-----

Creo que se como separar los grupos, mañana probare a ver que sale. Por hoy ya he tenido bastantes quebraderos de cabeza.

[Jurk]

Si es con circulos... Para ponernos en situacion....

Prueba a tener los datos del paso anterior (variacion de orientacion y valor de avance). Si la linea anterior ha sido de longitud dos, y la variacion de la orientacion ha sido de 3° y se ha quedado orientado a 150°, prueba aver si hay un punto cerca de dos unidades de distancia en la direccion de 153.

Para no salir de la circunferencia, la variacion de orientacion no debe cambiar de signo. Y al loro con las variaciones muy bruscas de angulo por culpa de funciones trigonometricas , porque puede pasar de +179° a -176° de orientacion, creando una variacion de angulo de -355° que deberia equivaler a 5° en realidad,

[swapd0]

Los circulos es otro caso de prueba, en verdad los datos pueden tener cualquier forma.

Estoy probando a separar primero los puntos en grupos, coloreando el grafo y despues unir los puntos que tengan el mismo color hasta recorrer todos los colores.

[Jurk]

Espero no estar diciendo lo mismo q tu...

Si la polilinea tiene que ser cerrada, podrias intentar rellenar la figura con dos colores tipo cubo de pintura de los programas de edicion de imagenes. Si solo hay un color try again, pero solo serviria para una polilinea

[swapd0]

Pero el problema es sacar la polilinea de los puntos.

He hecho la parte de colorear y por ahora sale peor porque crea demasiados grupos, salen entre 8 y 15 grupos con las polineas irregulares cuando deberían salir un solo grupo por cada polilinea (el ejemplo de arriba son varios conjuntos de pruebas puestos uno al lado del otro, el de los círculos es un solo conjunto de puntos).

[Jurk]

Siguiendo con mi idea del cubo de pintura....... Cada tramo de la polilinea tiene que estar rodeado por dos colores distintos...

[swapd0]

Cada tramo de una misma polilinea tiene que tener el mismo color para saber que son del mismo grupo, si tienen colores distintos los considerara como de otra polilinea y terminaría con un monton de aristas/polilineas pequeñas.

Puede que tenga que usar el algoritmo de k-mean...

PD: coloreo los vértices no las aristas, lo que quiero es que en caso de que los puntos no formen una sola figura y formen varias, estas me lleguen separados por colores para que al crear la polilinea no salte de una figura a otra. El algoritmo de ordenacion con una sola figura parece que va bien.

[swapd0]

Coloreando los puntos del grafo buscando los k vecinos no se salta a otros circulos (he probado con 5), ahora solo hay que hacer que no cree tramos tan pequeños (buscando mas puntos vecinos) o que los intente unir.

44224

Que asco, un sábado y llevo toda la tarde encerrado.