Pavé minimum (parallélépipède) englobant n points...

Question

Bonjour à tous,

Bon, je suis à la recherche (je suis à la bourre sévère...) d'une fonction sous C++ permettant de calculer le pavé englobant (bounding box) d'un nombre donné de points dont je connais les coordonnées en 3D...

Je suis au bord du suicide...merci à tous en avance.... :) 
a+

cs_djl · Answer

ca sent le partitionnement par arbre octale ;) (c'est ca?)

c'est tres simple, tu as ta bounding box definie par xmin, xmax, ymin, ymax, zmin, zmax et un point x,y,z

il suffit de tester si xmin < x < xmax et ymin < y < ymax et zmin < z < zmax 

enfin c'est comme ca que je ferais

brindillee · Answer

arbre octal ?? connais pas...

et pour l'explication...désolé mais j'ai rien compris...

cs_djl · Answer

non c'est moi, j'ai compris à l'envers

dans ton tableau de points il faut que tu cherche le x minimun et le x maximun, le y minimun et maximun (et pareil pour z)

et ces cordonnées minimales et maximales formeront ta box

brindillee · Answer

je vois ce que tu veux faire...mais ta technique sera dépendante du repère choisi...je recherche personnelement le pavé avec le minimum de volume englobant les points....donc avec une orientation particulière....

je ne sais si j'ai été assez clair ?

cs_djl · Answer

oui, je vois ce que tu veux faire, mais ca à l'air assez complexe

jpthomasset · Answer

Salut,

Ca m'a pas mal intrigué cette histoire et en jettant un oeil sur le net, voila ce que j'ai trouvé :

smallest parallelepiped

Ce n'est pas très intuitif, enfin en tout cas pas pour moi :-)

A+,
JP.

brindillee · Answer

jpthomasset
c exactement ca....je suis en train de lire l'article...
le hic c que sortir une fonction d'un article comme ca c GALERE...voila perso je recherchais une fonction déjà programmé...

merci quand même...a+

Funto66 · Answer

Moi j'utiliserais la méthode de djl mais comme tu dis c'est dépendant d'une orientation; donc à ta place, je ferais l'objet dès le début dans une certaine orientation, puis je créerais la bounding box et ensuite transformations 3D (glRotatef() si t'es sous OpenGL) pour remettre dans le bon sens.
Mais faudra aussi que tu fasses tourner les points qui composent ta bounding box, de façon "software" (pour ça tu peux utiliser matrices ou quaternions).

Je pense que ma réponse t'aidera pas bcp...dsl

---------------------------------------------------------
Patience et longueur de temps font plus que force ni que rage....
Coucous flingueurs 3D : http://www.freewebs.com/cf3d/
Un concours de prog graphique, ça vous dit? c'est sur Coder-Studio : http:

cs_djl · Answer

regarde dans boost, ca y est peut etre

http://www.boost.org/

Rusalie · Answer

Une direction, un sens, les coordonnées d'un point, Ok. Mais les coordonnées des points du volume englobant, avec une direction et un sens par rapport à Quoi ? 
Tous les points ont la même direction et le même sens ? Un volume englobant avec un Sens ? 
Strange thing,  I mean. 

Cupboard expert.

jpthomasset · Answer

D'après ce que j'ai compris, ce que brindillee recherche c'est un parrallelepipede de volume minimal englobant n points données. La question de l'orientation est en faite dictée par la recherche du volume minimum.

Brindillee, 

Est-ce que tu ne peux pas t'arranger pour avoir juste un parrallelepipede, pas forcement de volume minimal ? C'est tout de meme plus simple.
Quel est la finalité de ce programme ?

A+,
JP.

Rusalie · Answer

Ok, Une idée, En partant du volume initial et des six points obtenus du volume obtenu, tu dois pouvoir faire des changements de repère pour déterminer un autre volume, en prenant pour face trois des points,  du premier volume, mais c'est juste un "point" de départ.

Cupboard expert.

Rusalie · Answer

La fonction je ne l'ai pas, mais pour la pondre, tu auras 1,2 ou n points non alignés par face du cube initial, 1 ou deux points permettent de déterminer un axe faire pour pivoter la face  (recherche des points en avant par rapport à la vue externe) et trouver un point supplémentaire (soit un nouveau plan 2d), à partir de celui-ci (si l'on reste sur l'idée le parallélépipède, par rapport au treillis minimal), il faudra rechercher les nouvelles faces perpendiculaires et parallèles (les points les plus externes), ainsi de suite pour les différents points ( du cube initial, et des nouveau cubes déterminés -> récurrence).   
Je pense qu'ainsi le volume cube minimal peut-être trouvé.    

Cupboard expert.

brindillee · Answer

Pour répondre à jpthomasset, mon programme sert à déterminer à partir d'un nombre variant de coins d'un parallélipipède (j'ai les coordonnées en 3D), le parallélipipède optimal....c pour de la reconstruction 3D....

Pavé minimum (parallélépipède) englobant n points...

14 réponses

Votre réponse

Discussions similaires