Bonjour,
voilà mon problème :
- j'ai un plan dont je connais toutes les caractéristiques : coefficients, normale, ...
- j'ai une série de points sur ce plan (je connais les coordonnées 3D).
- Ces points sont plus ou moins disposés sur un cercle appartenant au plan.
Je souhaiterai trier ces points (sens trogo ou non).
Est ce que quelqu'un aurait une idée ???
FiReTiTi
Bonjour,
Il y a pas mal d'arbitraire dans ce problème! Donc pas mal de choix (tant mieux). Voilà comment je ferais, mais c'est une possibilité parmi bien d'autres.
(1) Puisque les points sont sur un pla, autant ne pas s'encombrer avec des coordonnées 3D. Donc projeter les points sur ledit plan (pprojection parallèlement à la normale).
(2) Puisque les points sont "plus ou moins" sur un cercle, il est naturel de prendre leur barycentre comme origine dans le plan. On se retrouve alors avec un ensemble de points 2D, "plus ou moins" répartis sur un cercle centré à l'origine.
(3) Passer ces points en coordonnées polaires et trier suivant leur argument (angle).
Évidemment, le repère du plan est très largement arbitraire, et dépend de la situation du plan dans l'espace. Mais si le but est seulement de "classer" les points par ordre trigonométrique, ça devrait convenir.
Cordialement,
-- françois
Merci,
cette réponse m'a l'air très bien...
FiReTiTi
Bonjour,
Voilà une autre bonne solution :
- On choisit deux points.
- On fait passer un plan par ces deux points, de telle sorte que ce nouveau plan est orthogonal au plan contenant les deux points.
- Ensuite on teste pour savoir si les points restant sont tous du même coté du nouveau plan. C'est facile à l'aide de l'inéquation du plan, en mettant les coordonnées de chaque points dans l'équation du nouveau plan.
- Si tout les signes sont identiques, alors c'est que nos deux points sont côte à côte.
Voilou.....
Merci pour les réponses...
FiReTiTi
Il te faut définir une relation d'ordre, totale ou partielle suivant que tu veux pouvoir trier aussi les éléments équivalents; comme tu parles de points dans un plan, les points "équivalents" sont évidemment ceux de mêmes coordonnées 3D dans le repère considéré; et donc il faut définir une métrique de mesure (ce qui implique le choix d'une origine pour la comparaison, telle que tous les points seront soit égaux à cette origine soit supérieurs).Envoyé par FiReTiTi
Attention au choix de cette métrique: si tu choisis un point du cercle et que tu définis la métrique comme la distance angulaire absolue séparant deux points quelconques, l'égalité de deux angles ne signifie pas que les points sont égaux et il restera à décider du critère de tri pour les deux points à égale distance angulaire de l'origine. Le choix du critère supplémentaire est arbitraire.
Tu peux aussi orienter le cercle, et restreindre la mesure angulaire dans un intervalle semi-ouvert borné (de longueur 2*PI), mais tu te trouveras toujours avec une métrique non continue partout (il restera au moins une discontinuité de ta métrique: deux points peuvent toujours être trouvés avec une distance aussi proche que l'on veut dans l'espace 3D, mais la métrique sur le cercle ne tendra pas vers 0 partout).
Ton problèmes est équivalent à dire: soit deux points distincts sur un cercle, lequel est à droite de l'autre? C'est indécidable sauf si tu apportes une restriction (par exemple en interdisant la traversée de l'arc par un point arbitraire du cercle, et en choisissant l'orientation de l'arc, et en attribuant ce point arbitraire d'un côté ou de l'autre).
en général pour pouvoir trier un ensemble il fauit toujours établir une relation d'ordre total sur cet ensemble et souvent aussi une relation d'équivalence. Si la relation d'équivalence est l'égalité, alors tu as un tri complet et unique de cet ensemble, et si la relation d'ordre total est basée sur une métrique, il est simple d'appliquer tous les algorithmes de tris optimisés; reste ensuite à gérer le cas de la discontinuité de l'ensemble obtenu par cette métrique, car ici tu vas trier un fermé (le cercle) en lui appluqant une transformation vers un espace semi-ouvert (avec la métrique).
Note enfin: un tri n'est pas forcément unidimensionnel; le tri usuel complet consiste à transformer un espace vers une droite par une fonction bijective (elle peut être continue et même dérivable, mais pas forcément inversible par une fonction dérivable ni même continue). Il y a bien des cas où la seule chose qu'on puisse faire c'est obtenir une bijection de l'ensemble vers un espace de moindre dimension, mais pas forcément de dimension 1, et on se contente de trier partiellement par une métrique de distance, pour se retrouver ensuite avec une suite de points dans des classes d'équivalence (relative à la matrique choisie) triées suivant un des axes (ou critère primaire de tri), afin de préserver la continuité de l'ensemble d'origine. mais la discontinuité apparait au sein de chaque classe d'équivalence (dans laquelle on peut utiliser une seconde métrique, utilisable comme clé de tri secondaire)
