Bertrand Lenoir-Welter wrote:
Est ce que ce genre de contour te conviendrait ?
http://users.skynet.be/candide/contour.htm
Si oui, je posterais l'algo ici.
Ah oui, c'est tout à fait ça, même si je suppose qu'il y a un
paramètre pour accepter ou non les points "rentrants". Je suis
preneur de l'algo.
Alors, voici l'algorithme que j'utilise. Il est très simple et
ne nécessite pas de calculs mathématiques complexes.
Je ne sais pas si l'enveloppe qu'il calcule est la "meilleure",
pour autant que cela ait un sens, ce dont je doute. On peut en effet
imaginer des tas de façons de faire.
Bref, voici le principe:
Le nombre de points est : NB_POINTS
On suppose que ces points sont décrits par une structure du type:
Public Type Point
x As Single
y As Single
End Type
Les points sont disponibles dans un tableau : p()
Le premier point est à l'indice 1, le dernier à l'indice NB_POINTS.
Ceci posé, voici l'algorithme:
1) Trier le tableau, selon les x. On dispose à la fin du tri d'un tableau
trié contenant les points ordonnés selon leurs abscisses croissantes
2) On part du premier point (celui à l'indice 1 dans le tableau trié)
Par définition, il appartient au contour
3) Le point suivant est le prochain dans le tableau dont l'ordonnée est
supérieure au point courant.
4) si on en trouve un, ça devient un point du contour. Il devient aussi
le point courant, et on repart au point 3)
5) sinon, on parcourt tous les points suivants le point courant et on garde
celui pour lequel la différence d'ordonnée est la plus petite. Il devient le
point courant. Et on repart au point 3), jusqu'à avoir atteint l'indice
NB_POINTS
Ensuite, on refait exactement la même chose, dans une seconde boucle, mais
en
parcourant cette fois le tableau de NB_POINTS à 1, et en inversant les
critères.
Voici une implémentation sommaire en Basic, celle qui a servi à produire
les dessins du Post précédents.
Les lignes Debug.Print XXXX donnent les indices du contour, dans l'ordre.
Il suffit de stocker ces indices de points dans le tableau trié pour
obtenir l'enveloppe.
'-----------------------------------------------------------
Private Sub Enveloppe()
Dim i As Long, j As Long, idx As Long
Dim p1 As Point, p2 As Point, p3 As Point
Dim found As Boolean
Dim best As Long
Dim MinDeltaY As Single
' Tri du tableau
Call BubbleSort(p, 1, NB_POINTS)
' Par définition, on garde le premier point
p1 = p(1)
Debug.Print 1;
' Premier parcours, de droite à gauche, en descendant
For i = 1 To NB_POINTS
found = False
Do While (i + idx) <= NB_POINTS
p2 = p(i + idx)
If p2.y < p1.y Then ' au dessous ?
' Trouvé !
Debug.Print i + idx;
p1 = p2
i = i + idx
idx = 0
found = True
' sort et passe au suivant
Exit Do
End If
' sinon continue
idx = idx + 1
Loop
' Si pas trouvé, il faut continuer en "remontant"
' On garde le meilleur suivant, à savoir celui pour
' laquelle la différence des ordonnées est la plus petite
If Not found Then
' find best deltaY
MinDeltaY = 1000000# ' ici on prend un grand nombre, plus
grand
' que la différence max des ordonnées.
best = -1
For j = i To NB_POINTS
p3 = p(j)
If (p3.y - p1.y) < MinDeltaY Then
MinDeltaY = (p3.y - p1.y)
best = j
End If
Next j
If best > 0 Then ' test par sécurité
' Trouvé !
Debug.Print best;
p1 = p(best)
i = best
idx = 0
End If
End If
Next i
' La seconde boucle est identique, mais dans l'autre sens:
' De gauche à droite, vers le haut
idx = 0
p1 = p(NB_POINTS)
For i = NB_POINTS - 1 To 1 Step -1
found = False
Do While (i + idx) >= 1
p2 = p(i + idx)
If p2.y > p1.y Then ' au dessus ?
' Trouvé !
Debug.Print i + idx;
p1 = p2
i = i + idx
idx = 0
found = True
Exit Do
End If
idx = idx - 1
Loop
If Not found Then
' find best deltaY
MinDeltaY = 1000000#
best = -1
For j = i + 1 To 1 Step -1
p3 = p(j)
If (p1.y - p3.y) < MinDeltaY Then
MinDeltaY = (p1.y - p3.y)
best = j
End If
Next j
If best > 0 Then
' Trouvé !
Debug.Print best;
p1 = p(best)
i = best - 1
idx = 0
End If
End If
Next i
End Sub
'-----------------------------------------------------------
Voila, je pense que c'est très compréhensible, j'ai la flemme
de le traduire en C proprement, mais c'est trivial.
Ce petit algo fonctionne très bien, sans devoir sortir l'artillerie
lourde que sont Delaunay et autres méthodes plus adaptées pour faire
de la MNT qu'un simple tracé de contour :-)
Tu trouveras sur ce lien le code source du programme de test, le programme
de test lui même (un exécutable Windows) et quelques screenshots:
http://users.skynet.be/candide/contour2.htm
Espérant que cela t'aide.
Bien cordialement;
--
Jean-marc Noury (jean_marc_n2)
FAQ VB:
http://faq.vb.free.fr/
mailto: remove '_no_spam_' ; _no_spam_jean_marc_n2@yahoo.fr
