Discussion :

[Sango64]

Bonjour tout le monde, j'explique le contexte :

Nous avons initialement une liste de points (en orange) qui forment une droite que l'on va appeler trace. En chacun de ces points, on calcule l’orthogonale. Les deux points de l’orthogonale qui sont à une distance N du point, vont nous permettre de construire notre géométrie (une bande) :



Nous avons donc une liste de sommets (de 1 à 16) qui vont former la bande. Grâce à ces sommets, on va obtenir des triangles que l'on va pouvoir dessiner. ( [1-2-3], [2-3-4] ... [14-15-16]).
J'utilise un triangle strip pour dessiner cette bande.

Le problème de chevauchement se produit lorsque la trace forme une courbe :



Dans ce dessin le trait noir du centre représente la trace. Les deux traits rouges sont la forme que l’on veut obtenir. En vert on peut voir les orthogonales. On remarque qu’elles se croisent (cercle orange).

J'aimerai éviter que les orthogonales se croisent car cela donne un effet indésirable quand je dessine mes triangles.
Dans le cas réel, il y a beaucoup plus de points que sur les images et la distance N est très grande.

Une solution que j'avais envisagé est de regarder si les orthogonales se croisent mais le coup des calculs est très important car pratiquement toutes les orthogonales se croisent lorqu'on approche d'une courbe.

Avez vous des idées, sur un algorithme me permettant d'éviter ces intersections d'orthogonales tout en gardant la forme de la bande optimale ?

Si vous avez des questions ou si je n'ai pas été clair dites le moi

J'ai déjà lu les topics suivant :
http://www.developpez.net/forums/d53...point-segment/
http://www.developpez.net/forums/d75...trigonometrie/

[pseudocode]

J'ai déjà lu les topics suivant :
http://www.developpez.net/forums/d53...point-segment/
http://www.developpez.net/forums/d75...trigonometrie/

Le deuxième topic ne te convient pas ?

[Sango64]

Bais pas entièrement je pense à moins que j'ai mal compris le topic ...

Voici peut être un schéma relevant mieux mon soucis :



Le cercle bleu représente toutes les intersections qui se passent. Ces intersections provoquent un chevauchement de triangles.

J'aimerai éviter toutes ces intersections. Sachant que ces orthogonales peuvent être encore plus grandes.

Je ne peux pas enlever les points dès que je détecte une intersection d'orthogonales car cela va rendre la bande différente de la trace.

[FR119492]

Salut!

J'aimerai éviter que les orthogonales se croisent

C'est tout simplement impossible et il n'y a pas d'algorithmes pour résoudre les problèmes impossibles. Ce que je te suggère, c'est de prendre une largeur variable, fonction du rayon de courbure de ta trace.
Jean-Marc Blanc

[Sango64]

Il y a t'il alors une autre méthode afin de calculer la bande sans passer par des orthogonales ?

Je n'ai la main sur la largeur de la bande, ce n'est pas moi qui la choisit.

[souviron34]

je l'ai expliqué dans le post cité...

• Prendre 3 points par sommet, sur chaque bande.
• A chaque angle, on ne garde qu'un seul point pour l'intérieur de l'angle et les 3 pour l'extérieur.
• Calculer les orthogonales
• A chaque fois vérifier si il y a inversion (tes croisements)
• Eventuellement repasser les points "intérieurs" pour vérifier si ils ne sont pas éliminés (et à ce compte-là re-calculer les intersections de chaque côté).

[Jean Dumoncel]

Salut,

Il y a t'il alors une autre méthode afin de calculer la bande sans passer par des orthogonales ?

Justement la méthode du deuxième topic me parait judicieuse dans ton cas, non? puisque tu pars bien d'une ligne brisée...

[Sango64]

Je suis vraiment désolé, je n'avais pas vu la seconde page du second topic que j'ai mis en lien hypertexte

Je reprends ce que vous avez dit :

En fait, l'idée de départ était d'avoir 3 points à chaque sommets : 1 se projette sur la médiatrice, les autres sont les projections perpendiculaires sur les directions des segments adjacents.. En regardant les inversions (échange) entre ces 2 points, on élimine les croisements dûs à un angle trop aigu pour la distance..

je l'ai expliqué dans le post cité...

* Prendre 3 points par sommet, sur chaque bande.
* A chaque angle, on ne garde qu'un seul point pour l'intérieur de l'angle et les 3 pour l'extérieur.
* Calculer les orthogonales
* A chaque fois vérifier si il y a inversion (tes croisements)
* Eventuellement repasser les points "intérieurs" pour vérifier si ils ne sont pas éliminés (et à ce compte-là re-calculer les intersections de chaque côté).

Prendre 3 points par sommet, sur chaque bande.

Donc ma liste de points de ma trace je prends à chaque fois le point P et P-1 et P+1.

A chaque angle, on ne garde qu'un seul point pour l'intérieur de l'angle et les 3 pour l'extérieur.

là j'ai pas tout compris ... On obtient une droite avec les 3 points et à partir de ça, on calcule l'angle de l'orthogonale ? Avec une méthode ArcTan c'est bien ça ? ou pas du tout ...

Calculer les orthogonales

A partir de l'angle et de la distance à la trace, je peux calculer les points extérieur et intérieur à la bande.

A chaque fois vérifier si il y a inversion (tes croisements)

Une fois que j'ai le point intérieur et extérieur vérifier si l'orthogonale courante ne se croise pas avec l'orthogonale précédente calculée.

Merci beaucoup pour tes précisions et aux personnes qui participent à ce topic

[souviron34]

il me semble que j'avais mis quelque part la partie détaillant..

En gros, voilà..

On démarre avec ça :

---------***-------------***------

----------*----------------*-------

---------***-------------***------

puis, si il y a un angle :

[Sango64]

Ok merci du complément d'information, ça devient plus clair

Si je reprend ton schéma miniaturisé, on a la trace de départ au centre, il y a 4 points que je vais nommer P1/P2/P3/P4.

Pour savoir de quel côté on va prendre 3 points ou 1 point, il faut connaitre l'angle de P1P2P3. On calcule cet angle avec le théorème d'Al-Kashi.
Si cet angle est aigu alors on ne prendra qu'un seul point en bas et 3 vers le haut. Si l'angle est obtus c'est le contraire.

Pour calculer les points de la bande (haut et bas) :
- on prend la médiatrice du segment P1-P3 et on a nos premiers points (bas et haut).
- on calcule l'orthogonale du segment P1-P2 passant par P2 et on a notre premier point de la bande haute
- on calcule l'orthogonale du segment P2-P3 passant par P2 et on a notre troisième point de la bande haute

Et on fait ces calculs pour chaque couple de trois points P(i-1)/P(i)/P(i+1) ; i = 1..(nombre de points - 2)

Avec la largeur de la bande que l'on va me donner, il est obligatoire que j'ai des croisements comme dans le schéma que j'ai mis dans mon post précédent.

Voici deux nouveaux schémas avec ce que tu m'as dit :



Désolé pour les grosses images mais je sais pas comment les miniaturiser ...

Maintenant il me reste à éliminer les points des croisements. Dans le cas du schéma de droite, il suffit d'enlever les points C4 et C12.
Je ne comprends pas ton principe d'inversion ni d'angle trop aigu par rapport à la distance pour supprimer les points

[souviron34]

avec le théorème d'Al-Kashi

Connais pas....

Simplement le théorème de Thalès suffit...

Je ne comprends pas ton principe d'inversion ni d'angle trop aigu par rapport à la distance pour supprimer les points

Bah, pour l'inversion c'est juste un autre moyen de regarder l'angle... Si à chaque sommet tu calcules les 6 points, quand il y en a 2 dont les positions relatives par rapoort au sommet s'inversent, alors on les supprime (angle aigu).

Maintenant, pour l'angle aigu, il suffit de regarder sur ta figure...

• Figure de gauche : on voit bien que le point le plus en bas à gauche, provenant de P3, ne satisfait pas la condition de distance par rapport à P0-P1.
  
  
• Figure de droite : on voit bien que le point central provenant de P2 en bas fait éliminer de facto les points provenant de P1 et P3. La vraie distance passera donc par le point provenant de P2 et l'intersection des segments calculés soit pas ces points, soit par les points encore précédents..

Comme je l'avais montré dans la figure à la fin du 2ième lien cité..

[Sango64]

Citation:
Envoyé par Sango64 Voir le message
avec le théorème d'Al-Kashi
Connais pas....

Simplement le théorème de Thalès suffit...

Le théorème de Thalès permet de savoir si deux droites sont parallèles ou bien de connaître des distances non ... Il n'y a pas de notions d'angles ...

[Jean Dumoncel]

Je ne me rend pas bien compte du résultat final que tu désires, ni ce que tu veux en faire après d'ailleurs,

mais si c'est juste une bandelette triangulé que tu souhaites,
pourquoi ne pas calculer tous tes points à l'aide de tes orthogonales,
puis de trianguler en travaillant de proche en proche plutôt que de se caler sur l'ordre de tes points?

[Sango64]

Oui ce que je veux au final c'est une bande triangulée autour de ma trace.

Le problème est qu'en calculant les orthogonales, il y en a qui se croisent => des triangles qui se chevauchent.
C'est ce que je veux éviter.

Ce que tu proposes c'est de garder le calcul des orthogonales afin d'obtenir les points de ma bandelette et donc les sommets de mes triangles et de travailler de proche en proche.

Mais tu appels quoi de proche en proche ? Chaque points intérieur et extérieur de mes orthogonales sont associés à un point de la bande.

[Jean Dumoncel]

C'est juste une idée, je sais pas c'est peut-être un peu naïf...

Mais en reprenant ton premier exemple, ça donnerai quelque chose comme ça :



Les points sur les lignes externes sont rangés (de proche en proche car au départ je pensais à un critère de minimisation de distance pour les ranger), puis on triangule en alternant la base des triangles (une fois sur la courbe externe, la suivante sur la courbe interne , et ainsi de suite, ...)

Mais j'ai du mal à savoir si cela pose des problèmes sur des cas plus complexes.

[Graffito]

Bonjour,

La solution que j'ai utilisée pour tracer les périmètres externes/internes à partir de la trace initiale ne passe pas vraiment par des triangles:

• On crée pour chaque segment Pn : Pn+1 le segments "externe" parallèle à une distance D.
• On crée à l'extrémité du segment externe ainsi créé l'arc de cercle de rayon D joignant le segment externe Pn : Pn+1 à Pn+1 : Pn+2 (il n'y aura pas d'arc si les 2 segments se coupent, juste un petit segment entre les 2 extrémités des sements externes).
• On découpe chaque segment et chaque arc en une suite de segments élémentaires dont la longueur est fonction de la précision désirée.
• Au final, on traite l'ensemble des segments élémentaires du "périmétre" externe en éliminant ceux situés à une distance à la courbe initiale inférieure à D
• et ... idem pour le périmètre interne.

[Sango64]

Bonjour tout le monde,

C'est juste une idée, je sais pas c'est peut-être un peu naïf...

Toutes les idées sont bonnes à prendre

Oui j'aimerai que mes triangles soient de la forme dont tu dis. Sauf que malheureusement ce n'est pas si simple que ça ... (du moins pour moi )
Dans une courbe comme celle là je peux avoir plus de 500 points qui ont une distance entre eux de quelques mètres (moins d'une dizaine) et la distance "D" peut être de 400 mètres par exemple.
De plus je n'arrive pas à voir comment tu arrives à trouver les bons points dans ton image.

Un cas plus réel que la figure que tu as reprise est celle là :



Il y a aussi un autre paramètre qui rentre en compte, chaque point possède une altitude et j'aimerai garder le plus de précision possible quant à cette altitude.


Graffito, je vais réfléchir à ta solution cet après midi. Juste une question, tu parles de Pn pour le segment de ma trace initiale et de Pn+1 pour le segment extérieur dans ton premier point. Puis tu reprends Pn pour les segments extérieur dans ton second point. Ce ne sont pas les mêmes Pn ou je me trompe ?
De plus, les segments Pn : Pn+1 et Pn+1 : Pn+2, ne sont pas obligatoirement de même longueur est ce que ça pose problème avec ta solution ?

Merci à tous

[pseudocode]

Juste comme cela, en passant, ca ne serait pas plus simple de faire de la géométrie constructive (2D) en faisant des unions successives de l'enveloppe de chaque segment.

Si on prend l'enveloppe exacte d'un segment (=un stadiums) ca doit être un peu soulant de gérer tous les cas d'intersections/appartenances. Mais si on approxime par un rectangle, ou un polygone, c'est nettement plus simple.

[Graffito]

les segments Pn

"Pn" est un point de la courbe initiale et "Pn : Pn+1" est le segment entre Pn et le point suivant Pn+1.