¿Encontrar la línea central del túnel?

19

Tengo algunos archivos de mapa que consisten en 'polilíneas' (cada línea es solo una lista de vértices) que representan túneles, y quiero tratar de encontrar la 'línea central' del túnel (que se muestra, aproximadamente, en rojo a continuación).

texto alternativo

He tenido cierto éxito en el pasado usando la triangulación de Delaunay, pero me gustaría evitar ese método ya que (en general) no permite la modificación fácil / frecuente de los datos de mi mapa.

¿Alguna idea sobre cómo podría hacer esto?

Estoy trabajando en C ++ bastante crudo.

geometry algorithm polyline-creation skeleton sje397
fuente
gis.stackexchange.com/q/177/162 también se ocupa de lo que está buscando: algoritmos de esqueletización .
julien
3
Creo que el enlace cruzado con SO es relevante ya que también hay respuestas allí stackoverflow.com/questions/3983613/find-tunnel-center-line
Dr. belisarius
@julien: Ya vinculaste eso en tu respuesta. Lo leí, pero no responde mi pregunta específica (que, para reformular, es: 'Ya sé cómo encontrar el MAT, pero me pregunto si alguien conoce un algoritmo que no sea Delaunay [es decir, no una lib - el problema no es mi codificación;)] que es eficiente para cambios localizados '). Hubo una respuesta en SO que tampoco respondió, pero tomó mucho esfuerzo y me dio mucho en qué pensar, así que le he otorgado el cheque a ese tipo hasta que aparezca algo mejor. Ninguna de las respuestas a continuación son tan buenas (que bien puede ser mi culpa).
sje397

Respuestas:

6

Has dibujado una buena aproximación a la Transformación del Eje Medial. La triangulación de Delaunay de hecho ofrece un buen enfoque. (El principal desafío es que partes de la MAT son piezas de parábolas, no solo segmentos de línea).

Me he encontrado con referencias al código de trabajo (generalmente en C / C ++, según recuerdo) en la literatura académica. Realice una búsqueda en Google Académico y busque documentos más antiguos (los más nuevos parecen centrarse en cálculos 3D).

whuber
fuente
Tengo un código de trabajo, usando Delaunay. Realmente estoy preguntando si hay otras formas.
sje397
1
@ sje397 En primer lugar, Delaunay solo resuelve aproximadamente el problema, por lo que solo por esa razón puede valer la pena investigar un mejor código. Segundo, de hecho hay otras formas. Puedo resumir dos brevemente: (1) buscar el MAT mediante amortiguadores internos y (2) realizar un análisis del terreno en la cuadrícula de distancia euclidiana de las polilíneas. Tampoco mencioné porque ambos son mucho más ineficientes y producen resultados más pobres. Es concebible que el segundo método sea susceptible de una solución dinámica razonablemente rápida.
whuber
4

Podría valer la pena mirar en "esqueletos poligonales".

Hay algunos ejemplos de fuentes de C ++ en http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Straight_skeleton_2/Chapter_main.html

bajo oscuro
fuente
Gracias poco oscuro. Buscaré más en CGAL. Pero el requisito de que el recálculo no sea costoso cuando cambian los datos de mi mapa es la dificultad.
sje397
CGAL es bastante rápido: un cálculo sobre la marcha debería ser posible. De lo contrario, podría echar un vistazo a las llamadas 'estructuras de datos cinéticos': cgal.org/Manual/3.3/doc_html/cgal_manual/…
julien
El "esqueleto" es otro término para el MAT. La búsqueda de "transformación del eje medial" ha dado más y mejores resultados que las búsquedas en "esqueleto" en mi experiencia.
whuber
"esqueleto" parece más genérico - MAT es solo un algoritmo específico para esqueleto, ¿verdad? Lo que sea, no es el tema ...!
julien
La licencia para CGAL parece restrictiva (es decir, costosa, este es un software comercial).
sje397