Discussion :

[Poupi0]

Bonjour d'abord, premier message sur developpez.com (que je lis depuis un moment déjà), et merci à tous les contributeurs du site pour toutes les infos qu'on peut trouver ici

Sans plus tarder, rentrons dans le vif du sujet.
Voilà le problème :
J'ai deux points dans l'espace, chaque point possède un vecteur associé. Le but est de relier ces deux points par des segments à angle droit, le premier et le dernier segment devant être orienté en fonction du vecteur associé aux points.
Contrainte supplémentaire, ces points peuvent se trouver sur un volume, volume qui doit être évité lors du calcul des segments.

Je cherche donc un algo (une base du moins) qui soit capable de trouver ces points. Je pense m'orienter vers quelque chose avec A*, mais j'aimerais avoir votre avis avant de me lancer dans l'implémentation.

En pièce jointe un exemple de ce que l'algo doit donner. Le volume (les cubes) ne sont pas assez grand ici, il faut imaginer qu'ils peuvent être bien plus gros que le segment créé.

[pseudocode]

Le but est de relier ces deux points par des segments à angle droit

Je ne comprend pas bien la notion de "segments à angle droit".

[Poupi0]

Si on ramène le problème en 2D, la polyligne reliant mes deux points change de 'direction' pour qu'entre le segment précédent et le segment à créer il y ait un angle de 90 degrés.
(je ne sais pas si je me fais bien comprendre, mais c'est pas super évident à expliquer avec des mots )

[pseudocode]

C'est relier deux points par le plus court chemin EN SUIVANT UNE GRILLE ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
+--+--+--+--+--+
|  |  |  |  |  |
+--+--+--####--+
|  |  |  |  #  |
+--##########--+
|  #  |  |  |  |
+--####--+--+--+
|  |  |  |  |  |
+--+--+--+--+--+

[Poupi0]

Non pas forcément en suivant une grille (si par grille tu entends que les points à relier peuvent être placés uniquement toutes les X unités).

[Zavonen]

Appelle A le point de départ (vecteur associé u)
Soit B le point d'arrivée (vecteur associé v).
Soit w le produit vectoriel de u et v
On cherche les points M et N tels que M et N tels que AM // u, MN //w et NB//v.
On cherche donc a et b tels que AM=au BN=bv
Le système à poser est donc:
coquille:-au+AB(=)bv=cw 3 équations du premier degré à trois inconnues (a,b,c).
correctif -au+AB+bv=cw
C'est pour une figure avec 4 points, si tu en veux 5: construis C tel que AC est orthogonal à u, associe à C n'importe quel vecteur k orthogonal à AC et réitère le processus précédent avec le couple ((C,k),(B,v))

[pseudocode]

Non pas forcément en suivant une grille (si par grille tu entends que les points à relier peuvent être placés uniquement toutes les X unités).

Hum... tu cherches a relier deux points par une structure quelconque qui est constitué de ligne et de coudes à 90° ?

Un peu comme l'économiseur d'écran 'Pipes' :

[ijk-ref]

Le plus simple à mon avis est d'utiliser une sorte de "répartiteur de fumées".

J'explique vite fait en 2D :

l'espace est représenté par une grille (une matrice 2D)

Tu sélectionnes l'un des points qui sera l'origine et tu places "0" dedans

Ensuite tu sélectionnes ses 4 voisins (haut, bas, droite et gauche) (s'ils existent) et tu places "1" dedans.

Et tu recommences l'opération avec les voisins de ses nouveaux points en plaçant "2". Bien sûr tu ne touchent pas aux points déjà initialisés ni ceux impossible représentant un mur ou un solide.

Voilà tu itères l'opération en plaçant ensuite "3", "4", "5", etc... jusqu'à ce que tu rencontres le point d'arrivé B.

A partir de là c'est extrêmement simple de recréer le chemin jusqu'à l'origine. En partant de B, il suffit de choisir le voisin qui a la plus petite valeur... et comme ça jusqu'à attendre le point A de valeur "0"

Note : t'as dit que tu ne voulais pas de grille... et bien tu en auras une quand même - à toi de choisir sa résolution !

[Poupi0]

pseudocode > oui c'est bien ça le principe

ijk-ref > hum, je ne pense pas que ce soit le plus adapté pour mon problème. L'algo va en effet me trouver le chemin entre les deux points mais il ne va pas tenir compte du nombre de 'coudes' créés, nombre que j'aimerais le plus optimal possible.

[ijk-ref]

hum, je ne pense pas que ce soit le plus adapté pour mon problème. L'algo va en effet me trouver le chemin entre les deux points mais il ne va pas tenir compte du nombre de 'coudes' créés, nombre que j'aimerais le plus optimal possible.

Je trouve que cela reste une bonne base. Reste à toi de le modifier pour en optimiser le nombre de coudes.

[souviron34]

1. Calculer la normale au premier point
2. Trouver quel côté de la normale est le plus proche de l'autre point
3. Faire la même chose pour l'autre point.
4. Prendre 10% de la distance entre les 2 points
5. Poser un point sur la bon côté de la normale du premier point
6. Poser un point sur le bon côté de la normale du second point
7. Poser un point à l'intersection du prolongement d'un des côtés et de la normale à l'autre

[Poupi0]

Merci à tous pour vos réponses, j'essaye d'implémenter ça dès que j'ai un peu de temps et je vous fais un retour