Estoy tratando de implementar el algoritmo Bentley-Ottmann en Java, pero estoy atascado en la implementación de la operación de intercambio (ver: Bentley-Ottmann en Wikipedia ) que se necesita al procesar puntos de intersección.
Si estoy entendiendo el algoritmo correctamente, hay 3 tipos diferentes de puntos de evento:
(Estoy omitiendo muchos detalles ya que no son muy relevantes aquí)
Estoy usando un TreeMap como mi estructura de datos para almacenar mis segmentos. No creo que haya una operación de swap para TreeMaps que te permita simplemente intercambiar dos elementos, así que ahí es donde estoy atascado.
Esto surge mucho cuando las personas intentan implementar Bentley-Ottmann. Consulte, por ejemplo, Implementación del algoritmo Bentley-Ottmann con un árbol AVL .
tl; dr: no puede usar implementaciones estándar de árboles binarios autoequilibrados como TreeMap para la estructura de estado en Bentley-Ottmann.
Cuando la mayoría de la gente usa un árbol binario balanceado como un árbol AVL o un árbol rojo-negro, se combina con un orden inmutable sobre los elementos del árbol. 3 siempre es mayor que 2. Nunca habrá necesidad de intercambiarlos. Pero con Bentley-Ottmann, el ordenamiento es una función del punto de barrido, lo que significa que el algoritmo debe participar directamente con el árbol en el reordenamiento de los elementos. En algunos árboles, es posible piratear un comparador mutable, pero incluso entonces, la única forma de convencer al árbol de que reconsidere su orden es eliminar el elemento, actualizar el comparador y volver a insertar el elemento, que es mucho, mucho más lento. de lo que debería ser.
Además, el uso de una estructura de árbol independiente (extrusiva) hace que sea más difícil lograr una implementación óptima debido a la frecuencia con la que accede directamente a los elementos del árbol. Cuando termina un segmento de línea, desea ir directamente al nodo de ese segmento en el árbol en O (1), no serpentear a lo largo del árbol en O (log n). Eso significa que la estructura de su segmento debe cumplir una función doble como un nodo de árbol, no tener alguna forma de navegar hasta el nodo de árbol.
Entonces, las buenas noticias: ¡usted puede implementar su propio árbol binario balanceado! Diviértete. ;-) Si no has implementado uno antes, te sugiero un árbol AA . Pero si está buscando un desafío mayor y le gustaría una estructura más exótica que tiende a ser una combinación perfecta para los patrones de acceso normales de Bentley-Ottmann, pruebe un Treap .
Mirando en la otra dirección, si desea que algo funcione rápidamente y no le importan los límites asintóticos técnicos, considere usar una lista vinculada para su estructura de estado, ubicando los nodos mediante un escaneo lineal en lugar de un recorrido de árbol. En mi experiencia, el tiempo para ubicar los nodos de estado rara vez es el cuello de botella de un sistema que involucra a Bentley-Ottmann, y si solo está trabajando con cientos o miles de segmentos, las búsquedas logarítmicas de un árbol binario no serán significativas.