No he podido encontrar el "nombre" del algoritmo que permitiría convertir líneas en polígonos. Dado que este problema cruza los SIG y los campos de la geometría computacional y la informática. No estoy seguro de qué más agregar a la mezcla. Soy reacio a proporcionar una lista de lo que he buscado, ya que también me gustaría saber qué otras personas considerarían su primera opción de criterio de búsqueda.
El escenario ... Tengo líneas (se necesitan dos puntos para construir una línea) ... cada línea está conectada al menos a otra línea. El espacio intermedio entre las líneas conectadas formaría un polígono. El escenario más simple sería un triángulo ... un rectángulo ... y uno podría ir más allá de las características multisegmentadas.
Perdón por cualquier descripción vaga, pero como dije, no quiero guiar las posibles soluciones por un camino que ya he visitado, ya que estoy interesado tanto en el "primer pensamiento" como en la solución final.
fuente
Respuestas:
¿Quizás "relleno de área"? Mira aquí y aquí .
Editar
Otra posibilidad es la triangulación restringida . (El enlace es a un applet de Java que le permite dibujar un gráfico con el mouse y luego ilustra un algoritmo de barrido plano para triangularlo). El resultado de cualquier triangulación, sin importar cómo se lleve a cabo, puede procesarse fácilmente para cree los polígonos deseados: simplemente combine todos los triángulos vecinos que comparten un borde recién creado.
Ejemplo
Gráfico original:
Gráfico triangulado:
fuente
En la teoría de grafos , esta operación se llama cálculo de caras . Está relacionado con el cálculo del dual de un gráfico dado.
Por ejemplo, en la biblioteca GeOxygène java, un gráfico (llamado CarteTopo ) tiene un método getFaces para recuperar su cara .
Esto se llama poligonalización en JTS
fuente
El software host RepRap convierte una lista de segmentos de línea (en un orden aleatorio desconocido) en una lista de polígonos, que suena similar a lo que está tratando de hacer.
En particular, el algoritmo de "coincidencia final" RepRap maneja un montón de casos patológicos.
Por desgracia, el software RepRap supone que cada esquina tiene un número par de bordes que van hacia ella: 2 líneas que van a una esquina en un objeto normal; 4 líneas que van juntas cuando la esquina de un objeto toca la esquina de otro objeto, etc. No sé lo difícil que sería adaptar este algoritmo para manejar diagramas voronoi, que generalmente tienen 3 bordes que van a cada esquina.
fuente
¿Ha explorado la base de código de GRASS para encontrar una solución a su problema? -> http://old.nabble.com/Polyline-to-Polygon-operation-td20257839.html
fuente
main.cen lav.typefuente, todo lo que sucede es que las características se vuelven a etiquetar como límites: no se produce un procesamiento real. En retrospectiva, esto no es demasiado sorprendente: si (no lo sé con certeza) las características se mantienen con información topológica 2D completa, entonces todo el cálculo para identificar regiones poligonales se ha llevado a cabo automáticamente durante la creación o importación de características y se conserva durante todo todas las operaciones de geoprocesamiento.Hola
No creo que lo que estés buscando sea un algoritmo específico. La tarea puede ser bastante difícil o muy simple dependiendo de su conjunto de datos.
Debe dividir el problema en al menos 2 partes. 1) es más un problema de red, cómo encontrar anillos cerrados de cadenas lineales. 2) expresa la cadena lineal cerrada como un polígono
La segunda parte, que es "convertir líneas a polígonos" depende más del formato que la representación de polígonos / cadenas de líneas. Me refiero a ir de:
LINESTRING (1 1, 2 2)
LINESTRING (2 2, 2 1)
LINESTRING (2 1, 1 1)
a:
POLÍGONO ((1 1,2 2,2 1,1 1))
está convirtiendo la línea en polígono, pero no es de lo que estás hablando, supongo. La parte más difícil es la primera. Si tiene un espagueti de líneas, cómo ordenarlas como cadenas de líneas cerradas.
Supongo que la respuesta a esa pregunta depende mucho del conjunto de datos. Como Kirk pregunta, si las líneas pueden cruzar el problema es mucho más grande. Si sabe que todas las "colecciones de líneas" son parte de una cadena lineal cerrada, se está volviendo más fácil. Luego puedes tomar cualquier línea y caminar por el camino hasta que estés de vuelta nuevamente y luego continuar con el paso dos de arriba.
Mi punto es que la condición del conjunto de datos establece todas las reglas sobre cómo hacerlo. Si desea encontrar todos los polígonos posibles en un espagueti de cadenas lineales, supongo que tendrá que haber muchos algoritmos diferentes involucrados para colocar puntos de vértice en todos los cruces, buscar todas las rutas posibles, etc.
En PostGIS, la función se llama ST_Polygonize. Esa función crea todos los polígonos posibles a partir de las cadenas de líneas que le asigna .
GEOS lo realiza para que pueda encontrar los algoritmos detrás tanto en el código GEOS como en el JTS.
Solo algunos pensamientos
/ Nicklas
fuente
Puede intentar buscar el algoritmo "Forward Star". Me han dicho que es genérico, pero las únicas discusiones al respecto que he leído siempre fueron en referencia a arcgis. Tal vez busque en las referencias citadas en estas notas de conferencia para la estrella delantera.
fuente