Trie liste de point3D - minimiser deplacement

**TiTiSeb** · 14/03/2007, 14h39

Bonjour,

Je demande vote aide car je lutte sur un algo de trie. je pose le probleme.

j'ai une liste d'element à 3 valeurs (X, Y et Z). j'aimerai trié cette liste de facon à ce que les elements soit "géographiquement le plus pret". avec comme priorité l'axe X puis l'axe Y puis Z.

"géographiquement le plus pret" signifie que les points sont triés comme si on voulait minimiser l'espace entre deux points consécutifs. en minimisant le deplacement sur l'axe X puis l'axe Y et finalement l'axe Z qui est le moins contraint en deplacement.

la deuxième contrainte est qu'on veut minimiser le nombre de deplacement entre deux points.

le point initiale est fixé avant le trie.

Petit exemple:
- liste des points à ranger:
(0,0,1)(0,1,0)(0,1,1)(1,0,0)(1,0,1)(1,1,0)(1,1,1) soit les coins d'un cube.

bien entendu la liste peut être passée dans le n'importe quelle ordre.

- point original :
(0,0,0)

la liste rangée serai :
(0,0,0)(0,0,1)(0,1,1)(0,1,0)(1,1,0)(1,1,1)(1,0,1)(1,0,0)

Merci d'avance à ceux interessés pour resoudre mon case tête.
TiTi.

**souviron34** · 14/03/2007, 15h07

avec un cube il y a plusieurs manières

en partant de l'origine, tu as 3 directions équivalentes.

Si par contre tu as des vrais points 3D, alors là c'est différent.

En gros tu fais l'algorithme du "quick sort"
(voir http://fr.wikipedia.org/wiki/Tri_rapide).

Il faut une fonction de comparaison. Si tu veux trier tel que tu le dis (mais qui n'est pas en distance) , ta fonction sera du style :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
Si X2 < X1
    alors Pt2 avant Pt1
Sinon
    Si X2 > X1
        alors Pt2 après Pt1
    Sinon
        Si Y2 < Y1
             alors Pt2 avant Pt1
        Sinon
             Si Y2 > Y1 
                   alors Pt2 après Pt1
             Sinon
                   Si Z2 < Z1
                        alors Pt2 avant Pt1
                    Sinon
                        Si Z2 > Z1
                            alors Pt2 après Pt1
                         Sinon
                             On ne change rien
                         Fin si
                    Fin si
             Fin si
        Fin si
    Fin si
Fin si

Mais ça ne triera pas en distance !!!

**souviron34** · 14/03/2007, 15h16

Je rajouterais que si c'est vraiment en distance que tu souhaites trier, alors ta fonction de comparaison sera du style :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
dist2 = distance ( Pt2, Ptref)
dist1 = distance ( Pt1, PtRef)
 
Si dist2 < dist1
    alors Pt2 avant Pt1
Sinon
    Si dist2 > dist1
        alors Pt2 après Pt1
    Sinon
        Aucune importance
    Fin si
Fin si

**TiTiSeb** · 14/03/2007, 15h54

FrancisSourd tu as raison c'est un peu le probleme du voyageur du commerce.

En fait ce que je veux faire c'est deplacer une pointe d'instrument dans l'espace. On me donne une liste de point. A moi d'ordonner ses points pour minimiser le deplacement de l'instrument.

le deplacement sur X est plus lent que sur Y et Z.
Je veux favoriser le deplacement sur Z.

si on prend le problème en 2D et que les points sont uniforméments répartie ca donne ce genre de deplacement:
>>>v
v<<<
...
Avec les axe
x-->Z
|
v
X

la liste serai : >>>v <<<v

comment je peux definir ca en algo??

le test du superieur et inferieur sur X, Y et Z ne fonctionne pas car j'aurai la liste suivante:
>>>v v<<<

C'est plus claire comme ca?

La deuxième contrainte c'est que je veux pas si possible me deplacer en diagonale seulement suivant une direction si possible. Bon si on a deux points avec X et Y différent on sera obligé. mais dans la mesure du possible je voudrai faire un seule deplacement X,Y ou Z entre deux points sucessifs de ma liste.
je me deplacement axe par axe donc un deplacement en diagonal et plus long que le deplacement dans un seul axe.

**FrancisSourd** · 14/03/2007, 16h29

Envoyé par <_oodTi96Tiboo_>

le deplacement sur X est plus lent que sur Y et Z.
Je veux favoriser le deplacement sur Z.

Il y a alors une solution optimale qui, à partir de l'origine, va

soit au point de plus petite coordonnée x et parcourt les points dans l'ordre des x croissants
soit au point de plus grande coordonnée x et parcourt les points dans l'ordre des x décroissants

Le choix entre les deux points se fait en fonction de la distance entre l'origine et le point de x min ou max.

Reste à départager les points avec même valeur de x.

Si les temps de déplacement sur Y et Z sont du même ordre de grandeur, le problème est NP complet. Il te faudra donc une heuristique (comme celle du plus proche voisin que j'indiquais dans mon précédent message, mais il y a mieux) pour départager les points qui ont même valeur sur X.

Sinon, si les temps sur Y sont nettement plus grands que ceux sur Z, il faudra, pour les points avec x identique, parcourir les Y dans l'ordre croissant ou décroissant puis, chaque sous-ensemble de points avec même valeur de y est parcouru par z croissant ou décroissant.

Ce problème se résout comme un plus court chemin, et c'est donc polynômial... mais je n'ai pas le temps aujourd'hui de formaliser plus. Si cette piste t'intéresse vraiment, je pourrai détailler un peu plus la semaine prochaine.

si on prend le problème en 2D et que les points sont uniforméments répartie ca donne ce genre de deplacement:
>>>v
v<<<
...
Avec les axe
x-->Z
|
v
X

la liste serai : >>>v <<<v

comment je peux definir ca en algo??

J'avoue que je ne comprends pas >>>v....

**TiTiSeb** · 14/03/2007, 18h59

[QUOTE=<_oodTi96Tiboo_>]

si on prend le problème en 2D et que les points sont uniforméments répartie ca donne ce genre de deplacement:
>>>v
v<<<
...
Avec les axe
x-->Z
|
v
X

la liste serai : >>>v <<<v
[QUOTE]

Soit la liste de point (x,y) suivante:=
(0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3) (3,0) (3,1) (3,2) (3,3)

cette liste serai rangée comme ceci:
(0,0) (0,1) (0,2) (0,3) (1,3) (1,2) (1,1) (1,0) (2,0) (2,1) (2,2) (2,3) (3,3) (3,2) (3,1) (3,0)

pour faire ce mouvement là:
>>>v
v<<<
>>>V

avec
>: avancer suivant y
v: avancer suivant x
<: reculer suivant y

Autement pour ta reponse je suis pas très matheu dans l'ame

et j'ai du mal à comprendre le coup de NP complet entre autre

**FrancisSourd** · 14/03/2007, 21h56

Merci pour ces précisions.

En fait, si un problème est NP-complet, cela signifie qu'il n'y a pas d'algorithme rapide pour le résoudre. En pratique il faut chercher des bonnes solutions (non optimales) au problème (heuristique, recherche locale, métaheuristique...)

En gros, tu pars d'une solution que tu as construit puis tu essaies de l'améliorer en changeant la séquence (inversion de deux points par exemple) jusqu'à ce que tu n'arrive plus à l'améliorer.

Dans ton cas, il me semble que l'on peut quand même avoir un bon algorithme mais cela demande quelques connaissances en théorie des graphes.

**mamelouk** · 14/03/2007, 15h10

salut,

moi je ferais comme ca:
- trier la liste de points selon X
- segmenter cette liste en autant de listes qu'il y a de valeurs de X distinctes
--- trier chacune de ces sous-listes selon Y
--- segmenter chacune de ces liste en autant de listes qu'il y a de valeurs de Y distinctes
----- trier chacune des sous-sous-listes selon Z
--- refusionner les sous-sous-listes
- refusionner les sous-listes

pour la deuxième contrainte j'ai pas compris, et d'ailleurs ton problème m'a l'air assez tordu

c'est quoi ton problème initial ? il y a surement une solution plus simple

a+

**FrancisSourd** · 14/03/2007, 15h16

Un algorithme très simple est de construire la liste de manière itérative. A chaque fois, tu rajoutes le point le plus proche (en utilisant ta définition de la proximité) du point précédemment ajouté.

Cela ne donnes pas une solution optimale pour ton problème tel que tu le définis mais je dois avoir que je ne comprends pas ta deuxième "contrainte".

la deuxième contrainte est qu'on veut minimiser le nombre de deplacement entre deux points.

Est-ce mathématiquement une contrainte ou un objectif? Qu'est-ce que le déplacement entre deux points?

Quand tu dis minimiser le déplacement sur x, est-ce que le coût de déplacement est proportionnel à la longueur du déplacement sur x, ou est-ce plus complexe.
As-tu une formulation mathématique du coût de déplacement?

Le problème est un voyageur de commerce en lui-même. Dans ma compréhension du problème, il est polynomial mais j'attends tes précisions sur l'énoncé pour répondre.

**FrancisSourd** · 20/03/2007, 11h17

Voici qq liens sur le voyageur de commerce

http://fr.wikipedia.org/wiki/Probl%C...ur_de_commerce
http://sbonnevay.free.fr/fr_ing_meta.php
http://www.nottale.net/index.php?project=pvc

**Melem** · 20/03/2007, 12h59

Voici Comment déterminer lequel des points A et B est le plus proche du point C.

Code :

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

1
2
3
4
5
6
7
8
9
10
Fonction PointLePlusProche(POINT A, POINT B, POINT C)
{
    Si d(A, C) < d(B, C) Alors
        C'est A
    Sinon : Si d(A, C) > d(B, C) Alors
        C'est B
    Sinon :
        C'est PointLePlusProcheSelonX(A, B, C)
    Fin Si
}

Code :

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

1
2
3
4
5
6
7
8
9
10
Fonction PointLePlusProcheSelonX(POINT A, POINT B, POINT C)
{
    Si |xA - xC| < |xB - xC| Alors
        C'est A
    Sinon : Si |xA - xC| > |xB - xC| Alors
        C'est B
    Sinon :
         C'est PointLePlusProcheSelonY(A, B, C)
    Fin Si
}

Code :

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

1
2
3
4
5
6
7
8
9
10
Fonction PointLePlusProcheSelonY(POINT A, POINT B, POINT C)
{
    Si |yA - yC| < |yB - yC| Alors
        C'est A
    Sinon : Si |yA - yC| > |yB - yC| Alors
        C'est B
    Sinon :
         C'est PointLePlusProcheSelonZ(A, B, C)
    Fin Si
}

Code :

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

1
2
3
4
5
6
7
8
9
10
Fonction PointLePlusProcheSelonZ(POINT A, POINT B, POINT C)
{
    Si |zA - zC| < |zB - zC| Alors
        C'est A
    Sinon : Si |zA - zC| > |zB - zC| Alors
        C'est B
    Sinon :
         C'est A /* Ou pourquoi pas B? ;) */
    Fin Si
}

Pour parcourir un ensemble de points avec chaque fois un déplacement minimum, en partant d'un point quelconque de départ (qui n'est pas forcément le point O), on parcours les points de proche en proche sans repasser par un même point (autrement dit si A est plus proche que B pourtant on est déja passé par A, alors on passe cette fois ci par B).

**TiTiSeb** · 20/03/2007, 18h25

Melem je suis un peu partie comme tu le decris mais avec cette fonction comme evaluation de la distance entre 2 points.

function Eval (Pt1, Pt2){

abs((Pt2.X - Pt1.X) * Cx) +
abs((Pt2.Y - Pt1.Y) * Cy) +
abs((Pt2.Z - Pt1.Z)* Cz)

}

Cx, Cy et Cz sont des facteur de ponderations pour favoriser un axe plutot qu'un autre. J'ai pris Cx=10000, Cy=100 et Cz=1.

J'ai simplifié le problème en ajoutant les points par plan 2D. ils sont definis par deux pts. On ajoute plan par plan (soit XY, XZ ou YZ).
lors de l'ajoue d'un plan j'ajoute à ma liste les points un par un comme ceci (excusez c'est en Java mais ca se lit bien):

public void Add_planeXY(Point2D Pt0, Point2D Ptf, Point2D Delta, double Z0){

for (double x=Math.min(Pt0.X, Ptf.X); x<=Math.max(Pt0.X, Ptf.X); x+=Math.abs(Delta.X)){

for (double z=Math.min(Pt0.Y, Ptf.Y); z<=Math.max(Pt0.Y, Ptf.Y); z+=Math.abs(Delta.Y)){

List_pts.Add_point(x, Y0, Correction_planarity(z, x, Y0));

}

}

La fonction Add_point parcourt la liste et insert le point si elle trouve que le point et plus proche que sont suivant grace à la fonction d'evaluation.

bon entre deux plans saisis, le deplacement peut être long mais bon je rejete la faute sur l'utilisateur pour qu'il choisisse bien ses plans

Les premiers tests sont ok et la procedure est super rapide.

Si on avait mieux à proposer je suis toujours preneur.

Trie liste de point3D - minimiser deplacement

Algorithmes et structures de données

Vue hybride

Discussions similaires

Partager

Partager