algorithm - Algoritmo Bentley-Ottmann en Haskell?

computational-geometry (1)

Así que he estado escribiendo una biblioteca de geometría computacional en Haskell porque no pude encontrar una en Hackage, y pensé que sería divertido de todos modos. Sin embargo, he estado estancado durante casi una semana en un algoritmo en particular que parece que no puedo obtener una buena forma de ''haskell''. Ese algoritmo es el algoritmo de Bentley-Ottmann para encontrar las intersecciones en un conjunto de segmentos de línea. Si está familiarizado con el algoritmo, puede saltar al último párrafo para pedir :)

La forma en que elijo implementar esta función es como una función que toma una lista de segmentos de línea y devuelve una lista de puntos y los segmentos de línea que se cruzan en ese punto. Esto nos permite tratar el caso en el que varios segmentos se cruzan en el mismo punto.

bentleyOttmann :: [Segment] -> [(Point, [Segment])]

El algoritmo es un algoritmo de línea de barrido. Imaginamos una línea que barre el avión, haciendo un trabajo algorítmico en varios puntos pares. Los puntos de evento en el algoritmo de Bentley-Ottmann son:

El punto final inicial de un segmento de línea.
El punto final final de un segmento de línea.
El punto de intersección de un grupo de segmentos.

Tenga en cuenta que un punto de evento se puede asociar con más de un segmento de línea en más de una forma. Para hacer un seguimiento de qué segmentos corresponden a qué puntos finales, uso un mapa del paquete de contenedores. Las claves de este mapa son puntos, y los valores son listas de segmentos, etiquetados por si comienzan en ese punto, terminan en ese punto o se cruzan en ese punto.

La línea de barrido determina el orden de los puntos. Imagine una línea vertical que barre el avión, deteniéndose en los puntos de evento para poder trabajar. Los puntos de evento se ordenan primero por su valor de x, y los puntos más pequeños se procesan primero. Genéricamente, esto es todo lo que necesitamos. En casos degenerados, los puntos de evento pueden tener la misma coordenada x. También ordenamos por sus coordenadas y, los puntos de evento con coordenadas y más pequeñas se procesan primero si hay un empate de coordenadas x.

Entonces, la estructura que uso, naturalmente, es una cola de prioridad. El que yo uso es del paquete de montones de Hackage.

¿Cuál es el trabajo que hacemos en cada punto de evento? Bueno, primero verificamos qué segmentos están asociados al punto del evento. Si hay más de uno, es un punto de intersección. Podemos agregarlo a la lista de intersecciones que hemos encontrado hasta ahora.

Aquí viene la parte difícil. Mientras recorremos el avión, hacemos un seguimiento de un conjunto de segmentos, ordenados con respecto al punto donde se cruzan con la línea de barrido . Cuando procesamos un punto de evento, primero eliminamos todos los segmentos que terminaron en ese punto de evento. Luego, todos los segmentos que se intersecaron en ese punto se invierten en orden . Finalmente, agregamos segmentos que comienzan en ese punto de evento al conjunto ordenado. Tenga en cuenta que, dado que todos estos segmentos se cruzan en el punto del evento, tienen que ser ordenados con respecto a una línea de barrido que está levemente perturbada.

En cada punto de evento, debemos agregar cualquier punto de evento nuevo, intersecciones nuevas que ocurran. Como hacemos un seguimiento del orden relativo de los segmentos que intersectan la línea de barrido, hacemos una de dos cosas:

Si intercambiamos dos segmentos o agregamos un nuevo segmento, encontramos el segmento modificado más bajo (con respecto a la línea de barrido), el segmento modificado superior, y los probamos para las intersecciones con sus vecinos inmediatos no modificados.
Si no intercambiamos ni añadimos nuevos segmentos, al menos eliminamos un segmento, lo que hace que sus antiguos vecinos ahora sean adyacentes. Probamos sus nuevos vecinos para la intersección.

Esta es la clave del algoritmo de Bentley-Ottmann, mientras recorremos el avión, solo probamos nuevos segmentos candidatos con sus vecinos. Esto significa que superamos el ingenuo algoritmo O (n ^ 2) cuando hay relativamente pocas intersecciones.

Mi problema (finalmente, lamento que esto sea tan largo) es esto: no tengo idea de cómo implementar esta lógica de ordenamiento. No puedo usar Data.Set porque el orden cambia a medida que barremos. Estoy tratando de implementar mi propia estructura de datos para hacer un seguimiento de la información, pero es sucio, con errores, probablemente ineficiente, ¡y también feo! Odio el código feo

Sé que Haskell tiene que ver con el código bonito. También creo que si no puedo implementar un algoritmo de una manera bonita, significa que realmente no lo entiendo. ¿Alguien puede darme una idea de cómo implementar este algoritmo?

Editar: ahora tengo una implementación ''operativa''. Intenté que funcionara con entrada genérica, así como con segmentos múltiples que se cruzan en el mismo punto y segmentos verticales. Parece que funciona en esas entradas con las pruebas insignificantes que hice. No funciona cuando los segmentos se superponen. No sé cómo lidiar con eso todavía. Agradecería la opinión sobre cómo acomodarlos. Actualmente, mi estructura de línea de barrido los sigue en el mismo nodo, pero solo usará uno de ellos en las pruebas de intersección, y puede dar resultados inconsistentes.

Uso Data.Set para mi cola de eventos, Data.Map para búsqueda y una implementación de árboles rojo-negro con cremalleras que basé en Okasaki en su libro. Si mi fragmento no tiene suficiente contexto, puedo agregar más.

Agradecería consejos sobre la reestructuración de la implementación así que es ... menos feo. No puedo decir qué tan correcto es y me pone nervioso.

El código se puede encontrar en hpaste aquí

El orden si los segmentos cambian solo en los puntos de intersección, y solo para los segmentos que se cruzan en el punto dado. Esto se puede implementar eliminando los segmentos que se cruzan e insertándolos de nuevo.

La función de ordenamiento es por coordenada y , cuando y s son iguales, por la pendiente. Los segmentos que se cruzan se insertarán en el orden correcto. A medida que el barrido progresa, las coordenadas y reales de las intersecciones de los segmentos de la línea de barrido cambiarán. No importa ya que el orden seguirá siendo el mismo (hasta que intercambiemos, es decir, eliminemos e insertemos nuevamente, intersectando segmentos). La coordenada y real no necesita almacenarse de todos modos. Debería calcularse dinámicamente para cualquier posición dada de la línea de barrido, a medida que insertemos o eliminemos segmentos.

La estructura de datos en cuestión no debe llamarse Set , es un Map o, más precisamente, un Mapa Ordenado. La operación de encontrar vecinos de un elemento dado es esencial aquí.