Inscription / Connexion Nouveau Sujet
Niveau Maths sup
Partager :

"surface" d un polyhedre convexe

Posté par
Ksilver
10-03-06 à 19:52

Bonsoir tous le monde !

j'ai bessoin d'aide pour trouver une solution algorithmique aux problemes suivant :


j'ai une series de point de l'espace (disont n point noté An ) qui sont les sommet d'un polyhedre qu'on suppose etre "le plus petit ensemble convexe contenant les n point",

on peut donc dire que H (ce polyhedres) est donc l'ensemble des barycentres a coeficiant positif des An (caracterisation du plus petit convexe contenant les An)

mon probleme est de determiner (en un temps raisonable via un algorithme)
1) la liste des arretes exterieur du polyhedres.
2) la liste des faces exterieur.
3) et enfin, generé un "patron" de H.








suivit de quelque debut de solution :


je ne pense pas qu'il soit possible de traiter ce probleme en regardant les longeur des segment et les surface des face... mais si vous avez une idee dans ce sens la sa m'interesse...


1) la liste des arretes exterieur du polyhedres. >>>> je pense que pour cela il
faudrait determiner un moyen pas trop compliqué de determiné si un point donné appartiens ou non a H... a mon avi si on sait faire cela il est facile de voir si un segment donné est a la surface de H ou non.


2) la liste des faces exterieur >>> pour cela la seul idee que j'ai eu est la suivante : on prend trois points aleatoires, on calcule une equation du plan passant par ces tres points (qu'on obtien par un simple produit vectorielle) et on regarde si les autres An sont "au dessu" ou "en dessou" de ce plan. si ils sont tous du meme coté c'est que la face consideré est exterieur. si l'un des An (autre que les 3 considérés) appartiens au plan sa nous informe que la face n'est pas un triangle mais un caré, pentagone ou autre...

en theorie sa permet de lister toute les faces, le probleme c'est le temps de calcule, a chaque fois qu'on prendra 3 sommet, il faudrat en tester n-3, et il faudrat faire sa pour toute les facon de prendre 3 sommet, sa nous fait un temps de calcule en O(n^4) ce qui est assez pitoyable quand meme non ?


3) a mon avi, une fois que le probleme 2 sera resolu celui ci sera un jeu d'enfant...


Merci, deja d'avoir lut jusqu'ici et toute idée et la bien venu



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !