Discussion :

[sapin]

Bonjour,

je suis à la recherche d'un algorithme ou d'une bibliothèque qui est capable de prendre une polyligne en entrée, et de la transformer en suite de segment, arc de cercle et clothoide.

Est ce que quelqu'un a déjà eu à faire à ce problème ?

Merci pour votre aide.

[Zavonen]

de prendre une polyligne en entrée, et de la transformer en suite de segment,

Pour çà, de mon point de vue, il n'y a rien à faire. une polyligne selon wiki c'est la même chose qu'une ligne brisée en maths, donc exactement une suite de segments.
Transformer un segment en arc de cercle, il y a une infinité de manières de le faire.
Même chose pour une clothoïde.
Par ailleurs quels segments doivent être transformés en quoi? Quel est le critère de choix?
Il semble que ton problème gagnerait à être précisé.

[sapin]

Je suis d'accord pour l'histoire des segments. Une polyline peut être vu comme une suite de segment. A la place, je resterai sur le terme de droite comme dans le titre.

Le but est de transformer cette suite de segment en un ensemble de droite, clotho et arc de cercle assurant une continuité et lissant le résultat.

L'idéal serai que ces "primitives" passe par le plus de point de la polyline possible.

J'utilise actuellement une méthode de transformation prend un nuage de point en entrée, qui utilise la "régression linéaire" (m'en demandé pas plus sur ce point la ), et ressort une liste de droite, clotho, arc de cercle.

Le but de ce poste est de savoir si il existe d'autre méthode, traitant directement une polyline et non pas un nuage de point.

J'espère avoir été plus claire. Si le point : polyline vers droite, arc de cercle, clotho n'est pas assez claire, je pourrai faire un dessin rapide pour mieux l'illustrer.

Merci pour la réponse.

[FR119492]

Salut!
Si tu nous expliquais le contexte, ça faciliterait beaucoup la résolution de ton problème.
Jean-Marc Blanc

[Zavonen]

assurant une continuité et lissant le résultat.

C'est une précision supplémentaire (et importante), mais l'ensemble des solutions reste infini, même avec ces contraintes
Oui tu ferais mieux de poster une image.

[sapin]

voici l'exemple.

Si tu nous expliquais le contexte, ça faciliterait beaucoup la résolution de ton problème.

Rien de spécial, je veut juste transformer une poly en suite de primitives cité ci dans les postes précédents.
Ou alors, je n'ai pas compris ta question.

[FR119492]

Salut!
Pour une route, le tracé "optimal" consiste en la mise bout à bout de segments de droites, d'arcs de cercles et de clothoïdes. J'avais cru comprendre que c'était cela que tu cherchais et je souhaitais que tu me le confirmes.
Jean-Marc Blanc

[Zavonen]

Je vois bien mais en fonction de quoi les TROIS derniers segments ont été transformés en UN arc de cercle, plutôt qu'en deux ou trois arcs ou une clothoïde. Bref, il y a toujours une logique qui m'échappe.

[sapin]

Salut!
Pour une route, le tracé "optimal" consiste en la mise bout à bout de segments de droites, d'arcs de cercles et de clothoïdes. J'avais cru comprendre que c'était cela que tu cherchais et je souhaitais que tu me le confirmes.
Jean-Marc Blanc

C'est bien ce que je cherche, oui.

mais en fonction de quoi les TROIS derniers segments ont été transformés en UN arc de cercle, plutôt qu'en deux ou trois arcs ou une clothoïde

J'ai dessiner ça d'instinct, parce qu'il me semblé que ça correspondrai le mieux à ma polyline.

Je n'ai pas plus de critière, je n'en ai pas identifié. Comme je le disait dans mon premier post, je cherche a savoir si il existe deja un outil/biblio/algo qui traite ce cas. Pas à creer un algorythme car je n'ai pas identifié les limites et les critères du problèmes.

[pseudocode]

Je n'ai pas plus de critière, je n'en ai pas identifié. Comme je le disait dans mon premier post, je cherche a savoir si il existe deja un outil/biblio/algo qui traite ce cas. Pas à creer un algorythme car je n'ai pas identifié les limites et les critères du problèmes.

Il y des librairies de vectorisation (genre AutoTrace ou PoTrace), mais je pense qu'elles créeront plutôt des courbes de Bezier que des clothoïdes.

[sapin]

Merci, je ne connaissait pas ces librairies.

Mais effectivement, c'est dommage si la notion de "type de primitives" n'apparait pas (ce qui est logique si vu la transformation en courbe de bezier).

[souviron34]

une approche possible serait de faire une série de transformées de Hough sur l'image, pour isoler lignes, arcs, etc etc.

Ensuite, prendre la liste des objets trouvés, et tenter de minimiser les distances et le nombre simultanément (ce qui résoudrait le problème 2 ou 3 arcs).

[sapin]

Je ne connaissais pas la transformer de Hough. Je vais me renseigner dessus. Merci pour cette piste.

[FR119492]

Salut!

C'est bien ce que je cherche, oui.

Alors, tu aurais dû nous le dire dès ton premier message.

D'autre part, tu aurais pu commencer par chercher sous fr.wikipedia.org/wiki/Tracé_en_plan_d'une_route.
Jean-Marc Blanc

[sapin]

D'autre part, tu aurais pu commencer par chercher sous fr.wikipedia.org/wiki/Tracé_en_plan_d'une_route.

Je ne cherche pas des informations sur : Comment tracé une route. mais bien sur comment transformer une polyline ou une suite de points en droite, arc de cercle ou clothoide.

La notion de polyline me semble suffisante pour s'abstraire du contexte, c'est pour cela que je ne l'est pas précisé.

Pour recentrer les "recherches", je recherche un outil ou méthode "générale" et non pas une suite de contrainte spécifique au réseau routier.

Merci

[FR119492]

Salut!

La notion de polyline me semble suffisante pour s'abstraire du contexte, c'est pour cela que je ne l'est pas précisé.

Désolé, mais comme je suis un "praticien" du calcul numérique (avec 47 ans d'expérience), la première question que je me pose toujours à propos d'un problème, c'est: "A quoi ça sert?"
Jean-Marc Blanc

[iNaKoll]

Sans vouloir paraître pessimiste, je ne pense pas qu'il existe un outil/bibliothèque permettant de faire ça. C'est tellement spécifique... Ca doit bien exister au fin fond d'un tiroir dans une entreprise quelque part mais ça m'étonnerait que l'on trouve ça sur internet.

Sinon pour moi il y a deux cas différents :
- soit les points/sommets des polylines sont exactes et les segments sont simplement là pour le visuel
- soit ils ne le sont pas et à ce moment là, la polyline minimiserait selon une logique inconnue l'écart entre le tracé réel et l'ensemble de ses segments.

Dans tous les cas, on peut supposer que le processus n'est pas parfaitement réversible.

Dans le premier cas, si les points sont suffisament proches les uns des autres, on peut s'en sortir. En effet, si trois points sont alignés, c'est que le tracé correspondant est un alignement droit. Ainsi on exclue les rayons de courbures inférieurs à la distance maximale entre deux points (il peut y avoir un problème ici, si la polyline est insuffisamment précise).

Si 3 points consécutifs ne sont pas alignés, on est en présence d'un arc de cercle/clothoïde. L'arc de cercle est caractérisé par un rayon de courbure constant. Pour identifier un cercle il suffit de vérifier que celui ci reste constant sur une portion donnée. Trois points suffisent à déterminer entièrement un arc de cercle (et donc son rayon de courbure). Encore une fois, de proche en proche, on est capable d'identifier un arc de cercle.

Les segments qui n'ont pas été identifiés comme étant des aligments droits ou des arcs de cercle sont des arcs de clothoïde.

Une clothoïde est caractérisée par son rayon de courbure initial, son rayon de courbure finale, sa longueur curviligne et une constante (supposée connue pour les tracés de routes). Le rayon de courbure d'une clothoïde (que l'on sait calculer à partir de 3 points de la polyline) varie de manière monotone (toujours croissant ou toujours décroissant). Sur un segment encore inconnu, s'il y a un changement du sens de variation du rayon de courbure, c'est que l'on passe d'un arc de clothoïde à un autre.

Ainsi, tous les segments sont identifiés. Il reste à déterminer une équation pour chaque segment de clothoïde et le tour est joué. Pour chaque arc de clothoïde, on connait le rayon de courbure initial et le rayon de courbure final. Il suffit de connaitre sa longueur pour la déterminer entièrement. On peut procéder par dichotomie, en prenant comme intervalle de recherche initiale la longueur de la polyline et la longueur de la polyline multipliée par 2 (voir 3/2 ou moins encore...). En prenant judicieusement un critère d'évaluation de la solution, ça doit se faire très bien.


Dans le cas où la polyline ne serait pas suffisamment précise, à part une recherche exhaustive avec dichotomie quand c'est possible et un critère d'évaluation de la solution, je ne vois pas. Et même si l'on trouve une solution ce n'est pas dit qu'elle soit proche du tracé initial. On peut peut-être se ramener à l'autre cas en augmentant récursivement le nombre de points de la polyline mais je suis sceptique ^^

[vince74]

Bonjour,
est ce que quelqu'un a trouvé une solution?
si oui, ça m'interresse.

[MABROUKI]

bonjour
Veux-tu damer le pion à P.Beziers?
Connais-tu les courbes splines ou polysplise ou courbes de Pierre de Beziers.
Elles servent à transformer un polyline en courbe spline.
Utilisee courramment dans la DAO (autocad ,bentley et 3ds max).
Un spline se compose de plusieurs de arcs de coubres correspondant aux differents segments du polyline.
Une fois transforme en spline ,on peut ramener le dit spline à un seul arc ou une courbe.
voici ce qu'en dit wikipedia , definition qui fera ton bonheur peut etre :
citation
Étant donnés k points ti appelés nœuds dans un intervalle [a,b] avec
La courbe S .....
est appelée spline de degré n si
.......................
et sa restriction sur chaque sous-intervalle
...................
où Pn est l'ensemble des polynômes de degré n.
En d'autres termes, sur chaque sous-intervalle
............................
S est un polynôme de degré n.

Les (ti, S(ti)) sont appelés points de contrôle.

Exemple
La fonction spline la plus simple est de degré 1, ce qui correspond à un polygone.
La plus couramment utilisée est la spline de degré 3 qui vérifie la propriété suivante :
S''(a) = S''(b) = 0
En dehors de l'intervalle, la courbe est une ligne droite tout en conservant le lissage.

fin de citation
citation en bas de page
Pierre Bézier, dans Courbes et surfaces pour la CFAO, Techniques de l'ingénieur, Mathématiques pour l'ingénieur, précise

« Le mot anglais spline a malencontreusement prévalu, alors qu'il se traduit en français par les substantifs latte ou baguette
fin de citation
Bonne decouverte.......

[souviron34]

de quoi tu parles ???

ça n'est pas ce qu'il demandait...