Algoritmo Bentley-Ottmann para dos grupos de segmentos de líneas

Question

El algoritmo Bentley-Ottmann se usa para calcular la intersección de segmentos de línea.

Sin embargo, en lugar de encontrar los puntos de intersección de todas las líneas entre sí, quiero encontrar los puntos de intersección entre dos grupos de líneas. Esto quiere decir que para cada línea en el grupo de línea A, quiero saber los puntos de intersección entre esas líneas y las líneas en el grupo B.

¿Hay alguna manera de extender el Bentley-Ottmann algorithm para esto? Ya tengo implementado el algoritmo Bentley-Ottmann existente (in the library of CGAL), y no estoy dispuesto a modificarlo. Sin embargo, estoy dispuesto a encontrar formas de reutilizarlo y ampliarlo.

Edición: Cualquier otro algoritmo (no necesariamente basado en Bentley-Ottmann) es bienvenido. Sería mejor si esos algoritmos ya están implementados en la biblioteca existente.

Answer 1

Puede encontrar todas las intersecciones entre todas las líneas en A+B, luego eliminar las intersecciones entre líneas en el mismo conjunto. No aumenta mucho la complejidad y esto le permite utilizar la función de biblioteca de CGAL sin modificaciones con solo una función de envoltura simple.

Answer 2

Donde Bentley-Ottman mantiene un árbol de segmentos de línea ordenados por su posición vertical actual, ¿no podría mantener dos árboles, uno para cada grupo A y B? Luego, cuando el algoritmo original comprueba los vecinos por encima y por debajo del punto actual, usted verificaría el vecino A arriba contra el vecino B más abajo, y viceversa.

Esto se basa en una rápida revisión del artículo de Wikipedia; No he escrito mucho código geométrico en la última década.

Answer 3

Agregando esta respuesta para completarla, aunque puede no ser el método más eficiente para 2 dimensiones.

En gráficos 3D es común a 2 árboles KD, que se pueden usar para detectar todos los nodos superpuestos (se puede usar para operaciones booleanas en geometría).

Ejemplo de trabajo (código C). https://developer.blender.org/diffusion/B/browse/master/source/blender/blenlib/intern/BLI_kdopbvh.c;3b4a8f1cfa7339f3db9ddd4a7974b8cc30d7ff0b $ 1089

Si hay muchos segmentos pequeños (como la ruta de una línea dibujada a mano), esto será razonablemente eficiente. Sin embargo, si hay muchos bordes largos (piense en palillos) ... esto funcionará mal, y usted querría dividir los nodos de hoja en el árbol BVH para obtener un mejor rendimiento. Sin embargo, si ese es el caso, probablemente sea mejor usar un método diferente como se sugiere en otras respuestas.

Answer 4

Sí Algoritmo de Bentley-Ottmann se puede ampliar para hacer esto, junto con otros métodos.

En la literatura, la tarea que describió a lo largo de las líneas de que informa intersecciones entre las líneas rojas y azules.

Aquí hay un documento que extiende el barrido B-O a un algoritmo óptimo. http://www.cs.unc.edu/~snoeyink/demos/rbseg/jcdcg25.pdf

No estoy de acuerdo con la afirmación de @ marcog sobre la complejidad. El documento vinculado afirma que el tiempo óptimo de O (n log (n + k)), si filtra las intersecciones, tendrá que realizar un barrido B-O en todas las líneas, y sería ((n + k) log n).

Hay otros algoritmos similares que puedan no requerir complejas estructuras de datos http://www.cs.swarthmore.edu/~adanner/cs97/s08/pdf/palazzi93counting.pdf

Para un menor número de aristas y un menor número de intersecciones entre los bordes, la solución en respuesta fuerza de trabajo de @ marcog así. (Este es un ejemplo de CGAL http://doc.cgal.org/latest/Arrangement_on_surface_2/Arrangement_on_surface_2_2consolidated_curve_data_8cpp-example.html).

Si necesita procesar polígonos complejos (datos GIS, etc.) o la necesidad de un algoritmo general, esta clase de algoritmos podría valer la pena.