Trouver la ligne médiane du tunnel?

J'ai des fichiers de carte composés de `` polylignes '' (chaque ligne n'est qu'une liste de sommets) représentant des tunnels, et je veux essayer de trouver la `` ligne centrale '' du tunnel (représentée, en gros, en rouge ci-dessous).

texte alternatif

J'ai eu un certain succès dans le passé en utilisant la triangulation de Delaunay, mais j'aimerais éviter cette méthode car elle ne permet pas (en général) de modifier facilement / fréquemment mes données cartographiques.

Avez-vous des idées sur la façon dont je pourrais faire cela?

Je travaille en C ++ assez brut.

geometry algorithm polyline-creation skeleton sje397
la source

gis.stackexchange.com/q/177/162 traite également de ce que vous recherchez: des algorithmes de squelette .

julien

Je pense que le lien croisé avec SO est pertinent car il y a aussi des réponses stackoverflow.com/questions/3983613/find-tunnel-center-line

Dr. belisarius

@julien: Vous avez déjà lié cela dans votre réponse. Je l'ai lu, mais il ne répond pas à ma question spécifique (qui, pour reformuler, est: `` Je sais déjà comment trouver le MAT - mais je me demande si quelqu'un connaît un algorithme non Delaunay [c'est-à-dire pas une lib - le problème n'est pas mon codage;)] qui est efficace pour les changements localisés '). Il y avait une réponse sur SO qui ne répondait pas tout à fait non plus, mais qui a pris beaucoup d'efforts et m'a donné beaucoup de réflexion, j'ai donc accordé le chèque à ce gars jusqu'à ce que quelque chose de mieux arrive. Aucune des réponses ci-dessous n'est aussi bonne (ce qui pourrait bien être de ma faute).

sje397

Réponses:

Vous avez fait une bonne approximation de la transformation de l'axe médian. La triangulation de Delaunay offre en effet une bonne approche. (Le principal défi est que certaines parties du MAT sont des morceaux de paraboles, pas seulement des segments de ligne.)

J'ai parcouru des références au code de travail (généralement en C / C ++ je me souviens) dans la littérature académique. Effectuez une recherche sur Google Scholar et recherchez des articles plus anciens (les plus récents semblent se concentrer sur les calculs 3D).

whuber
la source

J'ai du code de travail, en utilisant Delaunay. Je demande vraiment s'il y a d'autres moyens.

sje397

@ sje397 Tout d'abord, Delaunay ne résout que approximativement le problème, donc pour cette seule raison, il peut être utile de rechercher un meilleur code. Deuxièmement, il existe en effet d'autres moyens. Je peux en décrire brièvement deux: (1) rechercher le MAT au moyen de tampons internes et (2) effectuer une analyse de terrain sur la grille de distance euclidienne des polylignes. Je n'ai pas mentionné non plus car les deux sont beaucoup plus inefficaces et donnent de moins bons résultats. En théorie, la seconde méthode se prête à une solution dynamique relativement rapide.

whuber

Il pourrait être utile de se pencher sur les "squelettes polygonaux".

Il existe un exemple de source C ++ sur http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Straight_skeleton_2/Chapter_main.html

obscur
la source

Merci underdark. J'examinerai plus loin CGAL. Mais l'exigence que le recalcul ne soit pas cher lorsque mes données cartographiques changent est la difficulté.

sje397

CGAL est assez rapide - un calcul à la volée devrait être possible. Sinon, vous pourriez jeter un œil aux soi-disant «structures de données cinétiques»: cgal.org/Manual/3.3/doc_html/cgal_manual/…

julien

Le "squelette" est un autre terme pour le MAT. La recherche de "transformation de l'axe médian" a donné plus de résultats et de meilleurs résultats que les recherches sur "squelette" dans mon expérience.

whuber

"squelette" semble plus générique - MAT n'est qu'un algorithme spécifique pour le squelette, non? Quoi qu'il en soit, ce n'est pas le sujet ...!

julien

La licence pour CGAL semble restrictive (c.-à-d. Cher - il s'agit d'un logiciel commercial).

sje397