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

10

Esta es una pregunta simple y bastante común que ya se ha formulado para diferentes propósitos (vea este enlace y esto también , por ejemplo), aquí, sin embargo, no estamos buscando un paquete de software sino algoritmos que podríamos intentar implementar, digamos en Python .

Entonces, como se muestra a continuación, se asigna un conjunto de líneas (ya están recortadas, por cierto).
Algoritmos / ideas para generar polígonos (como se muestran los rojos) ?

ingrese la descripción de la imagen aquí

algorithm polygonize geometry-conversion Desarrollador
fuente
¿Se conoce el límite cuadrado externo, o también eso, para leerlo desde las líneas de entrada?
Devdatta Tengshe

Respuestas:

5

Bueno, ponemos una respuesta aquí que no es una respuesta completa a nuestra pregunta, es decir, la pregunta permanecerá " abierta para responder ". Sin embargo, es una solución para el problema en la pregunta. Aquí está el truco que usamos:

Primero veamos los resultados :
ingrese la descripción de la imagen aquí

Entonces, las líneas dadas en los leftpolígonos construidos que se muestran en el middle. Son polígonos reales como se muestra en right;)

Para el algoritmo que se proporciona a continuación, utilizamos el Shapelypaquete en Python .

  • líneas ==> MultiLineString {:: M}
  • agregue un pequeño buffer, diga eps{:: MB}
  • region ==> Polygon {:: P} (región aquí es un cuadrado)
  • P.difference(MB) {polígonos resultantes}

Tenga en cuenta que su funcionamiento es silencioso y rápido. Sin embargo, el punto que falta es que el algoritmo no es un método original para construir polígonos a partir de líneas . Sin embargo, funcionó perfectamente para el problema que teníamos en nuestras manos.

Desarrollador
fuente
4

JTS Topology Suite tiene una clase Polygonizer, que prácticamente hace esto.

Puede echar un vistazo al código fuente, disponible aquí , y convertirlo a Python.

Devdatta Tengshe
fuente
Como dice la descripción del código, no funcionará según lo esperado por el autor de la pregunta: "los bordes deben estar correctamente anidados; es decir, solo deben encontrarse en sus puntos finales. El Polygonizer se ejecutará en una entrada anulada incorrectamente pero no formará polígonos a partir de bordes sin nudos "
Pablo
1
Hay una operación dentro de JTS para dividir correctamente las líneas en los vértices. Tal vez el OP también podría ver eso.
Devdatta Tengshe
3

Puede echar un vistazo al paquete Python Shapely, particularmente polygonize ()

Dave
fuente
Una nota rápida que poligonaliza en Shapely ( from shapely.ops import polygonize) usa GEOS.Polygonize de GEOS . Entonces este es un enlace donde hay un enlace a un enlace ...: |
Desarrollador
Nuestras pruebas con polygonizeno tuvieron éxito en absoluto. Sin embargo, gracias por recordarnos Shapelycon qué podríamos encontrar una solución (un truco, en realidad) publicado como respuesta.
Desarrollador
2

Aquí hay otra solución que podríamos encontrar.

Usando DCELpodemos hacer bloques de tocar líneas.

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

Una etapa de preprocesamiento con la que se encuentran todas las intersecciones entre líneas. Luego, en consecuencia, todas las líneas se dividen en segmentos en los puntos de interacción. Una lista de puntos de intersección y una lista de bordes asociados son los necesarios para DCEL.

Desarrollador
fuente
Como este método es una solución original y ofrece un rendimiento mucho mejor en comparación con el otro método en el que differencese utiliza la operación.
Desarrollador