Encontrando a linha central do túnel?

19

Eu tenho alguns arquivos de mapa que consistem em 'polilinhas' (cada linha é apenas uma lista de vértices) representando túneis e quero tentar encontrar a 'linha central' do túnel (mostrada, aproximadamente, em vermelho abaixo).

texto alternativo

Eu tive algum sucesso no passado usando a triangulação de Delaunay, mas gostaria de evitar esse método, pois ele não permite (em geral) a modificação fácil / frequente dos dados do meu mapa.

Alguma idéia de como eu posso fazer isso?

Estou trabalhando em C ++ bastante bruto.

geometry algorithm polyline-creation skeleton sje397
fonte
O gis.stackexchange.com/q/177/162 também lida com o que você está procurando: algoritmos de esqueletização .
julien
3
Eu acho que a ligação cruzada com SO é relevante uma vez que existem respostas lá também stackoverflow.com/questions/3983613/find-tunnel-center-line
Dr. belisarius
@ Julien: Você já vinculou isso na sua resposta. Eu o li, mas ele não responde à minha pergunta específica (que, para reformular, é: 'Eu já sei como encontrar o MAT - mas estou me perguntando se alguém conhece um algoritmo não-Delaunay [ou seja, não uma lib - o problema não é minha codificação;)] que é eficiente para alterações localizadas '). Havia uma resposta no SO que também não respondia muito, mas exigia muito esforço e me dava muito o que pensar; portanto, eu concedi o cheque a esse cara até que algo melhor surgisse. Nenhuma das respostas abaixo é tão boa (que pode ser minha culpa).
precisa saber é o seguinte

Respostas:

6

Você desenhou uma boa aproximação à Transformação do eixo medial. A triangulação de Delaunay realmente oferece uma boa abordagem. (O principal desafio é que partes do MAT são parábolas, não apenas segmentos de linha.)

Encontrei referências ao código de trabalho (geralmente em C / C ++, lembro-me) na literatura acadêmica. Faça uma pesquisa no Google Scholar e procure por documentos mais antigos (os mais recentes parecem se concentrar nos cálculos 3D).

whuber
fonte
Eu tenho algum código de trabalho, usando Delaunay. Estou realmente perguntando se existem outras maneiras.
precisa saber é o seguinte
1
@ sje397 Em primeiro lugar, o Delaunay resolve apenas aproximadamente o problema; portanto, apenas por esse motivo, pode valer a pena pesquisar um código melhor. Segundo, existem de fato outras maneiras. Eu posso esboçar brevemente dois: (1) procure o MAT por meio de amortecedores internos e (2) realize a análise do terreno na grade de distância euclidiana das polilinhas. Também não mencionei, porque ambos são muito mais ineficientes e produzem resultados piores. É concebível que o segundo método seja passível de uma solução dinâmica razoavelmente rápida.
whuber
4

Pode valer a pena olhar para "esqueletos poligonais".

Há alguns exemplos de fontes C ++ em http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Straight_skeleton_2/Chapter_main.html

underdark
fonte
Obrigado underdark. Vou analisar mais detalhadamente a CGAL. Mas o requisito de que o recálculo não seja caro quando meus dados do mapa são alterados é a dificuldade.
precisa saber é o seguinte
A CGAL é bastante rápida - um cálculo em tempo real deve ser possível. Caso contrário, você pode dar uma olhada nas chamadas 'estruturas de dados cinéticos': cgal.org/Manual/3.3/doc_html/cgal_manual/…
julien
O "esqueleto" é outro termo para o MAT. Procurar por "transformação de eixo medial" produziu mais e melhores resultados do que pesquisas em "esqueleto" na minha experiência.
whuber
"esqueleto" parece mais genérico - MAT é apenas um algoritmo específico para esqueleto, certo? Seja como for, não é o assunto ...!
quer
A licença para CGAL parece restritiva (isto é, caro - este é um software comercial).
sje397