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.
Aún puede usar Bentley-Ottmann. –
Gracias Bart. Podrías explicar por favor? ¿No encontrará puntos de intersección que sean puntos de conexión de la misma polilínea? – Sam
sí, siempre que encuentre intersecciones, compruebe si se trata de una intersección "real" de dos segmentos, o un punto de dos segmentos conectados que pertenecen a la misma polilínea. –