¿Cuál es el algoritmo que utiliza Shapely para comprobar si dos polígonos se cruzan?

Question

¿Cuál es el algoritmo que Shapely se utiliza para comprobar si dos polígonos se cruzan?

from shapely.geometry import Polygon
p1 = Polygon([(0,0), (3,0), (3,1), (1,1), (1,2), (3,2), (3,3), (0,3)])
p2 = Polygon([(4,0), (5,0), (5,1.5), (2,1.5), (2,1.2), (4,1.2)])
print(p1.intersects(p2))

Había leído el código fuente de Shapely pero no encontré la implementación.

Answer 1

Una rápida búsqueda en el Base de código de Shapely lleva a impl.py que:

"""Implementación de la capa intermedia entre Shapely y GEOS Se trata de la capa número 2 de la lista siguiente.

1. objetos geométricos: la API OO de Python.
2. mapa de implementación: una abstracción que permite diferentes backends.
3. backend: objetos invocables que toman objetos geométricos Shapely como argumentos y, con GEOS como backend, los traducen a estructuras de datos C.
4. Biblioteca GEOS: algoritmos implementados en C++. Shapely 1.2 incluye un backend GEOS y es el por defecto. """

Así que el siguiente lugar para buscar es GEOS y Geometry.ccp y es intersection método. Se trata de una envoltura para HeuristicOverlay que llama OverlayNGRobust::overlay que es donde empezamos a ver referencias a STC , donde el Documentos de la API estado:

El algoritmo ingenuo obvio para la detección de intersecciones (comparando cada segmento con todos los demás) tiene un rendimiento inaceptablemente lento. Existe una amplia literatura de algoritmos más rápidos para la detección de intersección. Desafortunadamente, muchos de ellos implican una complejidad de código sustancial. complejidad del código. El STC intenta equilibrar la simplicidad del código con las ganancias de rendimiento. rendimiento. Utiliza algunas técnicas sencillas para conseguir un aumento sustancial del rendimiento para los tipos comunes de datos de entrada.

Después de hurgar un poco más en el código del STC, llegamos a RelateComputer que calcula el IntersectionMatrix entre dos geometrías (que incluye la intersección).

Si se profundiza más, habrá que esperar a que el Dr. JTS responda.