Algorithme de N coordonnées definissant une figure ???? [Résolu]

Signaler
Messages postés
2
Date d'inscription
dimanche 23 octobre 2005
Statut
Membre
Dernière intervention
24 octobre 2005
-
Messages postés
2
Date d'inscription
dimanche 23 octobre 2005
Statut
Membre
Dernière intervention
24 octobre 2005
-
Je suis étudiante (absolument pas en informatique!!!) et dans mon projet de recherche, je dois trouver un moyen de déterminer, sur un plan, l'aire à l'intérieur de laquelle se situent N coordonnées (Xi,Yi). Nous cherchons donc un algorithme qui, étant donné N coordonnées (3 à 10, en général), définir une figure (rectangle ou, de préférence, ellipse) qui englobe toutes les coordonnées et qui soit d'aire minimum.
Merci de votre aide!
Marlène

3 réponses

Messages postés
573
Date d'inscription
samedi 16 novembre 2002
Statut
Membre
Dernière intervention
9 avril 2008
1
Oups j'avais pas lu le début du problème...



Tu determines d'abord les segments qui bordent la surface recherchée:
les segments pour lesquels tous les points sont du même coté.

Tu testes tous les segments possible et tu gardes les segments "bordant" la surface.



Ta surface est forcement concave donc le barycentre des points est dans la surface.

Pour obtenir l'aire de ta surface, tu sommes les aires des triangles
formés par le barycentre et chaque segment (demi produit vectoriel pour
l'aire des triangles).



Attention aux points alignés, d'abord élimine les points situés sur des segments..



Voila voila.



En espérant t'avoir aidé, bonne nuit.



PS: pour la 3D c'est pareil mais avec des faces en guise de segments.
Messages postés
573
Date d'inscription
samedi 16 novembre 2002
Statut
Membre
Dernière intervention
9 avril 2008
1
Tu peux partir du cercle englobant (facile à obtenir).



Puis tu prends des rectangles circonscrits au cercle avec des
orientations différentes et tu fais varier leur dimensions jusqu'à
qu'un des points en sorte.

Tu auras un certain nombre (autant que tu veux en fait) de rectangles
englobant. Tu choisi ensuite celui dont l'aire est minimale.



Idem pour ellipse.



Il y a forcement mieux.
Messages postés
2
Date d'inscription
dimanche 23 octobre 2005
Statut
Membre
Dernière intervention
24 octobre 2005

Merci beaucoup de ton aide, je vais voir ce que l'on peut faire avec tes renseignements.