Bertrand Lenoir-Welter wrote:
> Bonjour
>
> Petite question de géométrie : je cherche un algorithme ou une piste
> de travail pour tracer le contour délimitant un groupe de points dans
> un plan. Chaque point a une coordonnée (X,Y) et l'on considère qu'ils
> sont relativement groupés, mais ne sont pas dans une matrice
> cartésienne bien ordonnée. En plus, le contour peut avoir des
> concavités.
> Pour le moment, je choisis le premier point comme étant celui de plus
> grande coordonnée X, et ensuite... ensuite je sèche.

Hello,

Est ce que ce genre de contour te conviendrait ?
http://users.skynet.be/candide/contour.htm

Si oui, je posterais l'algo ici.

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

"Bertrand Lenoir-Welter" <bertrand-dot-2008-at-galaad-dot-net> wrote in
message news:48163649$0$898$ba4acef3***news.orange.fr...
>> 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.

Non, pas de paramètres, tout est automatique.
Et le tout n'utilise que des additions et des soustractions et
une ou 2 comparaisons: pas de calcul d'angles, pas de trigo, etc.

Le tout tient en 20 lignes de code et est très rapide
(plus ou moins 4 millisecondes pour un semi de 1000 points).

Je posterais l'algo ce soir car j'ai écrit ça hier soir à la
maison et ne l'ai pas pris avec moi au boulot.

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

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

"Bertrand Lenoir-Welter" <bertrand-dot-2008-at-galaad-dot-net> wrote in
message news:48182e7d$0$877$ba4acef3***news.orange.fr...
> Merci Jean-Marc pour ce code. J'avoue que je ne suis pas très calé en
> Basic mais ça devrait pouvoir se convertir sans trop de difficultés dans
> un langage plus Civilisé (avec un grand C).

C'est sur! Si j'ai 5 minutes, je ferais la conversion
en C, avec par exemple comme interface:
Paramètre IN: un tableau de points (préalablement triés).
En retour, un tableau d'indices représentant les indices
des points retenus pour le contour.

Ca ressemblera à ça:



#include<stdio.h>
#include<stdlib.h>


typedef struct _pt
{
double x;
double y;
}TPoint;

void sort_with_x(TPoint *t, long nb)
{
/* code de tri */
}

void calc_contour(TPoint *t, long nb_points, long *contour)
{
/* calculer les indices et mettre dans contour */
/* mettre -1 après le dernier indice pour indiquer
la fin du tableau */
}

int main(void)
{
long nb_points = 0L;
TPoint *t = NULL;
long *contour = NULL;
long idx = 0L;

/* définir le nombre de points, par exemple 100 */
nb_points = 100L;

/* allouer tableau */
t = (TPoint*) malloc( sizeof(struct _pt) * (nb_points+1) );

/* remplir tabbleau */
t[0].x = 123.456; t[0].y = 78.94;
t[1].x = 987.654; t[2].y = 21.54;
/* etc. */

/* trier tableau */
sort_with_x(t, nb_points);

/* Calcul du contour */

/* préallouer le tableau d'indices pour le contour,
au maximum il y aura nb_points */

contour = malloc( sizeof(long) * (nb_points+1) );

calc_contour(t, nb_points, contour);

idx = 0;
while( contour[idx] != -1 )
{
printf("pt%ld Indice = %ld - x=%f, y=%f\n",
idx, contour[idx], t[contour[idx]].x, t[contour[idx]].y);
idx++;
}


return 0;
}

Voila, ça compile et tout et tout.

Il n'y a plus qu'à remplir les trous :-)

--
Jean-marc Noury (jean_marc_n2)
FAQ VB: http://faq.vb.free.fr/
mailto: remove '_no_spam_' ; _no_spam_jean_marc_n2***yahoo.fr

"Jean-Marc Bourguet" <jm***bourguet.org> wrote in message
newsxbprs7wwga.fsf***news.bourguet.org...
> "Jean-marc" <jm***nowhere.invalid> writes:
>
>> 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 :-)
>
> Mais il a des caracteristiques peut-etre indesirables.

C'est très possible :-)

> Par exemple, le contour trouve n'est pas le meme apres une rotation.

C'est exact. C'est une caractéristique qui pour ma part (pour mon usage)
n'est pas indésirable.

Le point fort de cet algo, c'est son efficacité et sa simplicité de mise
en oeuvre: pas de fonctions trigonométriques, pas de géométrie compliquée,
par de transformations en ccordonnées polaires, pas de tests de verticalité
et autres joyeusetés géométriques, etc.

Tout dépend donc de l'usage, comme toujours.

--
Jean-marc Noury (jean_marc_n2)
FAQ VB: http://faq.vb.free.fr/
mailto: remove '_no_spam_' ; _no_spam_jean_marc_n2***yahoo.fr

Bertrand Lenoir-Welter wrote:
>> Mais il a des caracteristiques peut-etre indesirables. Par exemple,
>> le contour trouve n'est pas le meme apres une rotation.
>
> Ah... Effectivement ça risque de poser problème. Mais bon, c'est
> toujours bon d'essayer pour avancer vers la solution.


En fait je corrige. Après quelques tests, il s'avère que le
contour est bien le même après une rotation, quelle que soit
la rotation.
Les indices des points sont évidemment différents, puisque on doit
recalculer un tableau trié.
Mais si on affiche les coordonnées des points retenus pour le contour,
on constatera aisément que les points de contours sont les mêmes, quelle
que soit la rotation (j'ai testé avec des rotations de 90, 180, 270 et 45).
Je suppose que c'est vrai en général.

La caractéristique indésirable n'existe donc pas :-)

--
Jean-marc Noury (jean_marc_n2)
mailto: remove '_no_spam_' ; _no_spam_jean_marc_n2***yahoo.fr

Bertrand Lenoir-Welter wrote:
> Merci Jean-Marc pour ce code. J'avoue que je ne suis pas très calé en
> Basic mais ça devrait pouvoir se convertir sans trop de difficultés
> dans un langage plus Civilisé (avec un grand C).

Hello,

Je ne sais pas si tu as fait la traduction.
Moi je l'ai fait pour le principe.

Voici donc la version (C)ivilisée de la chose :

http://users.skynet.be/candide/contour_c.html

A+

--
Jean-marc Noury (jean_marc_n2)
mailto: remove '_no_spam_' ; _no_spam_jean_marc_n2***yahoo.fr

"Jean-Marc Bourguet" <jm***bourguet.org> a écrit dans le message de news:
pxb8wyjl7pu.fsf***news.bourguet.org...
> "Jean-marc" <jm***nowhere.invalid> writes:
>
>> Bertrand Lenoir-Welter wrote:
>> >> Mais il a des caracteristiques peut-etre indesirables. Par exemple,
>> >> le contour trouve n'est pas le meme apres une rotation.
>> >
>> > Ah... Effectivement ça risque de poser problème. Mais bon, c'est
>> > toujours bon d'essayer pour avancer vers la solution.
>>
>>
>> En fait je corrige. Après quelques tests, il s'avère que le
>> contour est bien le même après une rotation, quelle que soit
>> la rotation.
>
> J'aimerais bien une preuve plutot que des tests. Par exemple sur
> (0, 2) (1, 1.25) (2, 0) (4, 2) (2, 4)
> a lire ton algo j'ai l'impression qu'il va passer dans les cinq points
> tandis que si tu fait une rotation de 45 degres, il ne va prendre que
> les 4 sommets du carre.
pour être honnête, cet algo basé sur des tris en fonction des axes
principaux n'a guère de chance de faire mieux que de 'rogner autour des
coins'. du coup les rotations de 90° ont de forte chance de produire le même
résultat "by design"... mais les rotations aléatoires (en particulier celle
qui ne sont pas les angles habituels basés sur des multiples de 15° .
Le test de base d'un algorithm de ce genre est de fournir les mêmes données
après qu'elles ont subi une rotation de X degrés (étapes de 1 en 1 de 0 à
359), et de vérifier que les points de contour sont toujours les mêmes à la
rotation près.
Un algorithme à base de coordonnées polaires aurait plus de chance de
'tomber en marche'... mais bien sûr tout ce qui compte est d'avoir un
critère exprimé en terme d'angle et/ou de distance (ce qui revient à dire
aussi produit vectoriel et/ou cartésien), pas en fonction d'une projection
sur un ou N axes [N fini].

en espérant aider
Armel

Armel wrote:
> "Jean-Marc Bourguet" <jm***bourguet.org> a écrit dans le message de
> news: pxb8wyjl7pu.fsf***news.bourguet.org...

Hello,

> pour être honnête, cet algo basé sur des tris en fonction des axes
> principaux n'a guère de chance de faire mieux que de 'rogner autour
> des coins'. du coup les rotations de 90° ont de forte chance de
> produire le même résultat "by design"... mais les rotations
> aléatoires (en particulier celle qui ne sont pas les angles habituels
> basés sur des multiples de 15° .

C'est fort possible :-) En attendant, cet algorithme est efficace, donne
des résultats valables et semble approprié pour la demande initiale.

> Le test de base d'un algorithm de ce genre est de fournir les mêmes
> données après qu'elles ont subi une rotation de X degrés (étapes de 1
> en 1 de 0 à 359), et de vérifier que les points de contour sont
> toujours les mêmes à la rotation près.

Bof. Les specs étaient : "faire le contour d'un nuage de points, avec
éventuellement des concavités". Il n'est pas fait mention d'autres
critères...

> Un algorithme à base de coordonnées polaires aurait plus de chance de
> 'tomber en marche'... mais bien sûr tout ce qui compte est d'avoir un
> critère exprimé en terme d'angle et/ou de distance (ce qui revient à
> dire aussi produit vectoriel et/ou cartésien), pas en fonction d'une
> projection sur un ou N axes [N fini].

Bof aussi. Bien sur qu'on peut faire des choses très compliquées, et se
lancer dans des considérations abstraites sur le bien fondé de telle ou
telle méthode. On peut aussi sans trop se fatiguer lancer au vent des
concepts "... coordonnées polaires ...", "... triangulation de Delaunay
....",
"... produit vectoriel ...", "...projections...", etc.

Je trouve un peu triste que sur ce groupe consacré à l'agorithmique, j'ai
été le seul à proposer un algorithme, accopagné d'une implémentation
portable et 100% fonctionnelle, afin que chacun puisse le tester:
http://users.skynet.be/candide/contour_c.html

Il eût à mon sens été sympathique d'avoir d'autres VRAIES propostions
(c'est à dire un algo et une implémentation portable) afin que l'on
puisse comparer.

Bon week-end!

Cordialement,

--
Jean-marc Noury (jean_marc_n2)
mailto: remove '_no_spam_' ; _no_spam_jean_marc_n2***yahoo.fr

"Jean-marc" <jm***nowhere.invalid> a écrit dans le message de news:
4825512f$0$2945$ba620e4c***news.skynet.be...
> Armel wrote:
>> "Jean-Marc Bourguet" <jm***bourguet.org> a écrit dans le message de
>> news: pxb8wyjl7pu.fsf***news.bourguet.org...
>
> Hello,
>
>> pour être honnête, cet algo basé sur des tris en fonction des axes
>> principaux n'a guère de chance de faire mieux que de 'rogner autour
>> des coins'. du coup les rotations de 90° ont de forte chance de
>> produire le même résultat "by design"... mais les rotations
>> aléatoires (en particulier celle qui ne sont pas les angles habituels
>> basés sur des multiples de 15° .
>
> C'est fort possible :-) En attendant, cet algorithme est efficace, donne
> des résultats valables et semble approprié pour la demande initiale.
>
>> Le test de base d'un algorithm de ce genre est de fournir les mêmes
>> données après qu'elles ont subi une rotation de X degrés (étapes de 1
>> en 1 de 0 à 359), et de vérifier que les points de contour sont
>> toujours les mêmes à la rotation près.
>
> Bof. Les specs étaient : "faire le contour d'un nuage de points, avec
> éventuellement des concavités". Il n'est pas fait mention d'autres
> critères...
>
>> Un algorithme à base de coordonnées polaires aurait plus de chance de
>> 'tomber en marche'... mais bien sûr tout ce qui compte est d'avoir un
>> critère exprimé en terme d'angle et/ou de distance (ce qui revient à
>> dire aussi produit vectoriel et/ou cartésien), pas en fonction d'une
>> projection sur un ou N axes [N fini].
>
> Bof aussi. Bien sur qu'on peut faire des choses très compliquées, et se
> lancer dans des considérations abstraites sur le bien fondé de telle ou
> telle méthode. On peut aussi sans trop se fatiguer lancer au vent des
> concepts "... coordonnées polaires ...", "... triangulation de Delaunay
> ...",
> "... produit vectoriel ...", "...projections...", etc.
>
> Je trouve un peu triste que sur ce groupe consacré à l'agorithmique, j'ai
> été le seul à proposer un algorithme, accopagné d'une implémentation
> portable et 100% fonctionnelle, afin que chacun puisse le tester:
> http://users.skynet.be/candide/contour_c.html
>
> Il eût à mon sens été sympathique d'avoir d'autres VRAIES propostions
> (c'est à dire un algo et une implémentation portable) afin que l'on
> puisse comparer.
ça c'est clair, si j'avais le temps j'en aurais bien proposé un.

par contre, le risque même avec un algo qui marche c'est de ne pas se rendre
compte de ses limites, de ses cas d'utilisation valables et on est alors sur
des bases instables pour les développements utilisant les résultats... et
c'est la course à la catastrophe.

en résumé, votre participation est en pratique bien plus importante que la
mienne c'est sûr, mais elle serait vraiment parfaite si en plus de l'algo
vous pouviez nous dire dans quels cas il ne fonctionne pas (par exemple
quelles cordes du contour ne seront pas sélectionnées pour être retirées,
alors que d'autres similaires près des coins le sont).

> Bon week-end!
>
> Cordialement,
bon week-end à vous aussi

Armel

Armel wrote:
> "Jean-marc" <jm***nowhere.invalid> a écrit dans le message de news:
> 4825512f$0$2945$ba620e4c***news.skynet.be...
>> Armel wrote:
>>> "Jean-Marc Bourguet" <jm***bourguet.org> a écrit dans le message de
>>> news: pxb8wyjl7pu.fsf***news.bourguet.org...

>> Il eût à mon sens été sympathique d'avoir d'autres VRAIES propostions
>> (c'est à dire un algo et une implémentation portable) afin que l'on
>> puisse comparer.
> ça c'est clair, si j'avais le temps j'en aurais bien proposé un.
>
> par contre, le risque même avec un algo qui marche c'est de ne pas se
> rendre compte de ses limites, de ses cas d'utilisation valables et on
> est alors sur des bases instables pour les développements utilisant
> les résultats... et c'est la course à la catastrophe.

C'est tout à fait vrai.

> en résumé, votre participation est en pratique bien plus importante
> que la mienne c'est sûr, mais elle serait vraiment parfaite si en
> plus de l'algo vous pouviez nous dire dans quels cas il ne fonctionne
> pas (par exemple quelles cordes du contour ne seront pas
> sélectionnées pour être retirées, alors que d'autres similaires près
> des coins le sont).

C'est exact aussi, mais je ne cherchais pas la perfection )

Je comptais un peu sur l'initiateur de ce thread pour évaluer
l'algorithme (dont le fonctionnement est somme toute assez simple)
afin de justement en montrer les limites/imperfections, car je suis
sur qu'il en a, c'est une évidence.

En toute honneteté, je n'ai pas le temps (ni l'envie) de me livrer
ici à un exercice accadémique sur cet algo que j'ai imaginé et codé
en 1 heure sur un coin de table : en dehors de mes participations
communautaires, j'ai aussi un vrai boulot qui m'occupe assez bien...

Cordialement;

--
Jean-marc Noury (jean_marc_n2)
mailto: remove '_no_spam_' ; _no_spam_jean_marc_n2***yahoo.fr