Generar polígonos a partir de un conjunto de líneas de intersección

Question

Este es un simple y muy común la pregunta que ya ha sido pedido para diferentes fines (ver este enlace y este también, por ejemplo), aquí, sin embargo, que estamos buscando no es un paquete de software , pero los algoritmos que podríamos tratar de implementar decir en Python.

Así, como se muestra a continuación un conjunto de líneas se asignan (son ya recortado, por CIERTO).
Algoritmos/ideas para generar polígonos (como el rojo que se muestra)?

Answer 1

Bien, vamos a poner aquí una respuesta que no es una respuesta completa a nuestra pregunta, que es, la pregunta será "abierto para responder". Sin embargo, es una solución para el problema en cuestión. Aquí está el truco que hemos utilizado:

Primero vamos a ver los resultados:

Así que las líneas dadas en la left construido polígonos se muestra en la middle. Son reales los polígonos, como se muestra en la right;)

Para el algoritmo dado a continuación se utilizó Shapely de paquetes en Python.

• líneas ==> MultiLineString {:: M}
• añadir una pequeña buffer, dicen eps {:: MB}
• región ==> Polygon {:: P} (región aquí es un cuadrado)
• P.difference(MB) {resultante polígonos}

Nota que es bastante rápida en la operación. Sin embargo, el punto que falta es que el algoritmo no es un método original para la construcción de polígonos a partir de líneas. Sin embargo, funcionó a la perfección para el problema que hemos tenido en nuestras manos.

Answer 2

STC Topología Suite tiene una Polygonizer clase, lo que casi hace esto.

Usted puede mirar el código fuente, disponible aquí, y convertir en Python.

Answer 3

Usted puede tomar un vistazo a la de Python bien formada paquete, particularmente polygonize()

Answer 4

Aquí hay otra solución que podemos encontrar.

El uso de DCELnos puede hacer que los bloques de tocar las líneas.

Para Python no es un paquete {aquí}. Es una pequeña aplicación con algunos errores. Sin embargo, con un poco de esfuerzo se puede utilizar para este problema. También tenga en cuenta las siguientes etapas:

Un pre-procesamiento de la etapa con la que todas las intersecciones entre las líneas se encuentran. A continuación, en consecuencia, todas las líneas se dividen en segmentos en los puntos de interacción de los. Una lista de puntos de intersección y una lista de los bordes son aquellos necesarios para DCEL.