Algoritmo para encontrar intersecciones entre polilíneas

Question

El algoritmo de Bentley-Ottmann funciona para encontrar intersecciones del conjunto de líneas rectas. Pero tengo mucha polilíneas:

¿Hay una manera de encontrar intersecciones del conjunto de polilíneas?

Estoy averiguando, pero mientras tanto, si alguien puede dar algunos consejos o ideas, sería útil. Gracias por leer. Por cierto, estoy usando WPF/C# y todas las polilíneas son PathGeometry.

Fuente de la imagen: http://www.sitepen.com/blog/wp-content/uploads/2007/07/gfx-curve-1.png

Answer 1

El algoritmo de línea de barrido tiene una teoría bien, pero es difícil de aplicar con firmeza. Necesita tratar segmentos verticales, y puede haber casos en los que más de dos segmentos de línea se cruzan en un solo punto (o incluso comparten un segmento de línea común).

Usaría un R-Tree para almacenar cuadros delimitadores de los segmentos de línea de la polilínea y luego usar el árbol R para encontrar elementos posiblemente intersecantes. Solo estos deben ser probados para la intersección. La ventaja es que puede usar un R-Tree separado para cada polilínea y así evitar la detección de autointersecciones, si es necesario.

Considere usar el kernel de predicados exactos de CGAL para obtener resultados confiables.

Answer 2

Agregando a la sugerencia de Geom (un R-Tree es el camino a seguir), nuevas mejoras de rendimiento se pueden obtener de la siguiente manera:

1. Simplificar la polilínea - El número de puntos en la polilínea se puede reducir manteniendo la forma general de la polilínea. Esto se puede hacer usando un umbral de ángulo y procesando cada punto o usando the Ramer-Douglas-Peucker algorithm. Dependiendo de lo que esté haciendo, es posible que deba realizar un seguimiento de los puntos de la polilínea original utilizados como puntos de inicio/finalización para cada segmento de la polilínea simplificada (los índices de los puntos de la polilínea original deberán almacenarse en algún lugar).)

En this example puede ver cómo se puede reducir el número de puntos de una polilínea. Los puntos rojos indican puntos que no se usaron desde la polilínea original, y los puntos verdes indican puntos que se mantuvieron para construir la polilínea simplificada.

2. Almacene las polilíneas simplificadas en un árbol R, y determine las intersecciones entre cada segmento de cada polilínea (comparar los límites de los segmentos para reducir los cálculos es beneficioso para el rendimiento). Mientras se realiza esto, los viejos índices de los segmentos originales de la polilínea se almacenan como información relacionada con cada intersección detectada, junto con las polilíneas intersecadas (se puede usar algún tipo de identificador). Esto esencialmente le proporciona los límites de inicio y final de cada segmento en las polilíneas originales donde las intersecciones existen entre sí polilíneas.

3. Este paso se realiza solo si la ubicación de la intersección debe coincidir con la ubicación exacta de las intersecciones de las polilíneas originales. Tendrá que volver atrás y usar las polilíneas originales no simplificadas, junto con los datos de la información de intersección obtenida en el paso 2. Cada intersección debe tener un índice de inicio y final asociado, y estos índices se pueden usar para determinar qué específicos segmentos de la polilínea original deben procesarse. Esto le permitirá procesar solo los segmentos necesarios (dados por los índices de inicio y final almacenados con la información de intersección).Una alternativa a esto sería usar el punto en sí y extender un cuadro delimitador hacia afuera, luego procesar segmentos de las polilíneas originales que se cruzan con ese cuadro delimitador (aunque esto probablemente demorará más).

4. Puede ser necesario tener una etapa adicional para comprobar los puntos finales de cada polilínea contra los segmentos de cada otro polilínea, ya que el proceso de simplificación puede noquear algunas intersecciones de punto final. (Esto es generalmente bastante rápido).

Este algoritmo se puede mejorar aún más usando the Bentley-Ottmann algorithm (este es el algoritmo de línea de barrido al que se refería Geom). También tenga en cuenta que dependiendo del algoritmo de simplificación utilizado y de los parámetros utilizados para dichos algoritmos (tolerancia angular, por ejemplo), puede haber una compensación entre el rendimiento y la precisión (algunos resultados de intersección pueden perderse dependiendo de qué tan simples sean las polilíneas).

Obviamente, existen bibliotecas que pueden ser viables, pero si está limitado por los términos de la licencia debido a la empresa para la que trabaja o al producto en el que está trabajando, las bibliotecas de terceros pueden no ser una opción. Además, otras bibliotecas pueden no funcionar tan bien como sea necesario.