bonjour
svp aidez moi pour trouvez des algorithmes qui me permettent de calculer le volume d'un objet 3D representé à l'aide d'un nuage de points
le temps presse et moi j'ai rien trouvé
merci d'avance
Version imprimable
bonjour
svp aidez moi pour trouvez des algorithmes qui me permettent de calculer le volume d'un objet 3D representé à l'aide d'un nuage de points
le temps presse et moi j'ai rien trouvé
merci d'avance
Bonjour,
il te faut commencer par calculer l'enveloppe convexe (convex hull) d'un nuage de points. Fais une recherche dans le forum le sujet a déjà été traité plusieurs fois, sinon il y a toujours :google:.
Ensuite, tu pourras calculer le volume en faisant la somme du volume des tétraèdres formés par les triangles de l'enveloppe et le barycentre. Sujet également traité récemment.
Sous quel langage développes tu ?
salut
le problème est que j'ai un nuage de points seulement,j'ai pas une triangulation par exemple
Bonjour,
- Dans ton cas ce n'est pas une triangulation, mais une tétraèdrisation ou au moins une triangulation de la surface.Citation:
Envoyé par minerva
- Commence par calculer l'enveloppe convexe (impossible de faire sans) et tu auras comme résultat les triangles nécessaires.
TOTO
Je pensais que le problème de calcule de l'enveloppe convexe est au moins aussi difficile que la résolution des programmes linéaires en nombres entiers ?:D
Ce n'est absolument pas un problème facile, mais les solutions existent :DCitation:
Envoyé par benDelphic
Il y a tout un tas d'algorithmes existant, dont certains implémentés dans différentes bibliothèques...
JE DEVELOPPE SOUS MATLABCitation:
Envoyé par ToTo13
Salut,
http://www.mathworks.com/matlabcentr...bjectType=FILE
N'hésite pas à faire des recherches sur ce site, un grand nombre d'algorithmes et de solutions y sont implémentés.
A+.
En Fait TOTO avait raison...
Dans ce cas le domaine est borné ainsi que le nombre de points : Algorithme Gift Wrapping ....
Je pense aussi qu'il va falloir calculer l'enveloppe convexe.
Ca se fait par dichotomie:
- envelopper deux tétraèdres
- envelopper deux convexes
- diviser pour réger
Je peux proposer une méthode simple si le nuage est assez dense, c'est à dire si tous les points sont 'assez rapprochés' mais qui plante complètement si le solide est défini par peu de points.
La méthode de l'enveloppe convexe me parait tout à fait inadaptée à des objets naturellement concaves (une banane par exemple).
Bonjour,
L'hypothèse de départ la plus "juste" est de considérer que les points du nuage représentent en fait une probabilité de distribution (à définir en fonction de la distance) autour du point du nuage.
Ainsi un point de l'espace fera partie du volume si la probabilté globale résultant de l'application des probabilités relatives à chaque point du nuage est supérieure à un seuil (à définir).
En faisant le calcul sur l'ensemble des intersections d'un maillage du cube bornant le nuage, on peut mesurer le volume : c'est le volume du mini-cube du maillage x nombre d'intersections faisant partie du volume.
La faisabilité en terme de temps de calcul dépend de la taille du nuage, du nombre de points du nuage et de la précision du maillage : on multiplie le temps par 8 chaque fois que la précision double:(.
C'est exactement ce que je voulais dire !Citation:
En faisant le calcul sur l'ensemble des intersections d'un maillage du cube bornant le nuage, on peut mesurer le volume : c'est le volume du mini-cube du maillage x nombre d'intersections faisant partie du volume.
Ha oui tiens, j'avais pas pensé à la banane, je suis vraiment trop naze en géométrie algorithmique.
En tout cas il y a la méthode discrête (ou approchée), sans doute suffisante, et puis il y a la méthode continue (ou exacte), et pour cette dernière je continue à penser qu'il va falloir un union-find pour ne garder que quelques n tétraèdres parmi les quelques n^4 possibles.
je vais réfléchir à savoir si on peut facilement étendre l'algo que j'ai déjà mentionné plusieurs fois en 2D au 3D..Citation:
Envoyé par Zavonen
En fait, l'idée de base est de partir de l'enveloppe convexe, puis de "rentrer" dans la concavité jusqu'à un ... certain ;) ... point..
Mais si il y a un maillage sous-jacent, la solution de Graffito est parfaite..