Orienter des points

Aide à la résolution d'exercices ou de problèmes de niveau Supérieur.

Modérateur: gdm_aidesco

Règles du forum
Merci d'éviter le style SMS dans vos messages et de penser à utiliser la fonction Recherche avant de poster un message. Pour joindre des fichiers à vos messages, consulter ce sujet.
> Penser à utiliser le mode LaTeX (voir ici) afin de rendre vos formules plus lisibles.
> Ne poster qu'un exercice (ou problème) par sujet et indiquer son niveau précis dans le titre du message.

Orienter des points

Messagepar FiReTiTi » Jeudi 07 Septembre 2006, 08:42

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 trigo ou non).

Est ce que quelqu'un aurait une idée ???
FiReTiTi
Hecto-utilisateur
 
Messages: 63
Inscription: Mercredi 26 Juillet 2006, 12:49
Localisation: Portland, OR, USA
Statut actuel: Actif et salarié

Publicité

Messagepar nirosis » Jeudi 07 Septembre 2006, 09:25

Oui pourquoi pas. Ca dépend ce que tu veux faire après.
Si tes points sont sur un cercle, tu devrais peut-être commencer par une regression non-linéaire afin de trouver effectivement quel est ce cercle.
Après tu dois avoir aussi le centre de ce cercle.
Donc il devrait être facile de les classer dans le sens trigo.
nirosis
Administrateur
 
Messages: 1806
Inscription: Samedi 28 Mai 2005, 13:48
Localisation: Orsay, France
Statut actuel: Actif et salarié | Maître de conférence

Re: Orienter des points

Messagepar FiReTiTi » Jeudi 07 Septembre 2006, 09:28

Bonjour,

FiReTiTi a écrit: - Ces points sont plus ou moins disposés sur un cercle appartenant au plan.


C'était juste pour donner une idée de la disposition. Ils ne sont pas exactement sur un cercle. Sinon le problème serait facile...
FiReTiTi
FiReTiTi
Hecto-utilisateur
 
Messages: 63
Inscription: Mercredi 26 Juillet 2006, 12:49
Localisation: Portland, OR, USA
Statut actuel: Actif et salarié

Messagepar rebouxo » Jeudi 07 Septembre 2006, 11:09

Tu veux les parcourir en formant un quadrilatère convexe (non croisé).
Cherche du côté de l'enveloppe convexe de points. Il me semble qu'il existe un algorithme permettant de construire l'enveloppe convexes de $n$ points.

Olivier
rebouxo
Modérateur
 
Messages: 6961
Inscription: Mercredi 15 Février 2006, 13:18
Localisation: le havre
Statut actuel: Actif et salarié | Enseignant

Messagepar nirosis » Jeudi 07 Septembre 2006, 11:43

Quand je dis "sont sur un cercle", j'entendais "plus ou moins" comme tu l'as précisé.
C'est pour ça que je parle de regression ;)

Vois du coté de la proposition de rebouxo aussi. Matlab fait peut-être ce genre de chose.
nirosis
Administrateur
 
Messages: 1806
Inscription: Samedi 28 Mai 2005, 13:48
Localisation: Orsay, France
Statut actuel: Actif et salarié | Maître de conférence

Messagepar FiReTiTi » Jeudi 07 Septembre 2006, 11:57

Bonjour,

merci pour ces réponses... mais :
- l'enveloppe convexe en 3D est un peu ennuyeuse, surtout qu'il faudra que je fasse un changement de repère par rapport au plan si je veux me ramener au cas 2D.
- j'ai déjà programmé l'enveloppe convexe et mon algorithme ne me donne pas l'orientation.
- je dois programmer en C cette méthode, donc pas de matlab :(
FiReTiTi
FiReTiTi
Hecto-utilisateur
 
Messages: 63
Inscription: Mercredi 26 Juillet 2006, 12:49
Localisation: Portland, OR, USA
Statut actuel: Actif et salarié

Messagepar rebouxo » Jeudi 07 Septembre 2006, 12:03

Si tu sais que tes points sont sur un plan tu te remets en 2D non ?

Si tu veux juste parcourir tes points tu n'as pas besoin d'orientation !
Olivier
rebouxo
Modérateur
 
Messages: 6961
Inscription: Mercredi 15 Février 2006, 13:18
Localisation: le havre
Statut actuel: Actif et salarié | Enseignant

Messagepar Arnaud » Jeudi 07 Septembre 2006, 12:03

Qu'est ce que tu entends exactement par "trier" ?

Je ne suis pas sûr d'avoir bien compris, mais si on connait le centre de ce cercle ne pourrait-on pas imaginer des cercles concentriques de même centre.
On classerait par rayon, puis par angle si deux points sont sur un même cercle ( il faut se fixer une origine dans ce cas ).
Arnaud

Un peu d'info - Pyromaths
LaTeX - Exemples de formules LaTeX

Pas d'aide en MP (non plus)
Arnaud
Modérateur
 
Messages: 7115
Inscription: Lundi 28 Août 2006, 12:18
Localisation: Allemagne
Statut actuel: Actif et salarié | Enseignant

Messagepar FiReTiTi » Vendredi 08 Septembre 2006, 14:44

Bonjour,

mettons tous le monde d'accord avec une 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
FiReTiTi
Hecto-utilisateur
 
Messages: 63
Inscription: Mercredi 26 Juillet 2006, 12:49
Localisation: Portland, OR, USA
Statut actuel: Actif et salarié

Messagepar nirosis » Vendredi 08 Septembre 2006, 15:51

Perso, c'est pas plus clair pour moi :?
nirosis
Administrateur
 
Messages: 1806
Inscription: Samedi 28 Mai 2005, 13:48
Localisation: Orsay, France
Statut actuel: Actif et salarié | Maître de conférence

Messagepar rebouxo » Vendredi 08 Septembre 2006, 16:26

FiReTiTi a écrit:Bonjour,

mettons tous le monde d'accord avec une bonne solution :
- On choisit deux points.

jusque là ça va.
FiReTiTi a écrit:- On fait passer un plan par ces deux points, de telle sorte que ce nouveau plan est orthogonal au plan contenant les deux points.

Lequel ? Par deux points dans l'espace il passe une infinité de plans.
FiReTiTi a écrit:- 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...

Voui
Et sinon, que fais-tu ? tu changes de points et tu recommences ?
A line is a point that went for a walk. Paul Klee
Par solidarité, pas de MP
rebouxo
Modérateur
 
Messages: 6961
Inscription: Mercredi 15 Février 2006, 13:18
Localisation: le havre
Statut actuel: Actif et salarié | Enseignant

Messagepar MB » Samedi 09 Septembre 2006, 11:10

rebouxo a écrit:
FiReTiTi a écrit:- On fait passer un plan par ces deux points, de telle sorte que ce nouveau plan est orthogonal au plan contenant les deux points.


Lequel ? Par deux points dans l'espace il passe une infinité de plans.


Je pense qu'il veut prendre un plan passant par les deux points et orthogonal au plan contenant l'ensemble des points.

rebouxo a écrit:Et sinon, que fais-tu ? tu changes de points et tu recommences ?


Oui je pense. Ca ressemble plus ou moins à l'algorithme basique de détermination d'une enveloppe convexe (avec un plan à la place d'une droite). C'est donc en $O(n^3)$ il me semble. J'ai vu ici qu'on pouvait faire du $O(n \, ln(n))$.
MB
Administrateur
 
Messages: 6892
Inscription: Samedi 28 Mai 2005, 13:23
Localisation: Créteil
Statut actuel: Actif et salarié | Enseignant

Messagepar FiReTiTi » Lundi 11 Septembre 2006, 08:58

Bonjour,

c'est exactement ce que vient de marquer MB.

Pour ce qui est de la complexité, ce n'est pas un problème car je n'ai que cinq ou six points. De plus, cette opération arrive TRES rarement.
FiReTiTi
FiReTiTi
Hecto-utilisateur
 
Messages: 63
Inscription: Mercredi 26 Juillet 2006, 12:49
Localisation: Portland, OR, USA
Statut actuel: Actif et salarié


Retourner vers Exercices et problèmes : Supérieur

 


  • Articles en relation
    Réponses
    Vus
    Dernier message

Qui est en ligne

Utilisateurs parcourant ce forum: Google [Bot], Magpie [Crawler] et 4 invités