Discussion :

[fleurdelys77]

Bonjour tout le monde,

J'ai un ensemble de points avec les coordonnées (x,y,z) et qui se trouvent sur un même plan.
La question :
je veux calculer le minimum bounding rectangle de cette ensemble de point
c-a-d les quatre points qui déterminent se rectangle.

Merci d'avance

[pseudocode]

ton rectangle doit être aligné sur quelque chose (axes, repères), ou alors tu cherches le plus petit rectangle quel que soit son orientation ?

[fleurdelys77]

mes point se trouve sur le même plan (un plan quelconque dans l'espace 3D que j'ai à priori son équation )

[pseudocode]

ça a un rapport avec ma question ?

[fleurdelys77]

hihi désolé j'ai passé toute la journée à chercher la solution,
je suis tellement fatigué,que je n'ai pas bien lu votre question
oui c'est le plus petit rectangle quel que soit son orientation

[pseudocode]

Dans ce cas, la méthode consiste a tracer l'enveloppe convexe (2D) du nuage de points, puis de calculer toutes les bounding-box comportant un segment de l'enveloppe, et de garder la plus petite. C'est l'algo "rotating calipers".

Pour faire tout cela, je suggère de passer en 2D en projetant les points dans un repère cartésien quelconque du plan.

[fleurdelys77]

merci pseudocode pour votre réponse rapide je vous en suis très reconnaissante
mais est ce que vous pouvez me donner plus de précision surtout sur commet
"passer en 2D en projetant les points dans un repère cartésien quelconque du plan ".

merci encore

[pseudocode]

merci pseudocode pour votre réponse rapide je vous en suis très reconnaissante
mais est ce que vous pouvez me donner plus de précision surtout sur commet
"passer en 2D en projetant les points dans un repère cartésien quelconque du plan ".

merci encore

Et bien il s'agit de créer une base (deux vecteurs unitaires orthogonaux) dans le plan, puis d'exprimer les coordonnées des points dans cette base.

Par exemple, on prend deux points A, B quelconques dans la liste => on obtient un vecteur AB que l'on normalise => vecteur U.
On prend le vecteur N normal au plan (obtenu depuis l'equation du plan)
On calcule le vecteur V = U x N (produit vectoriel)
Et voila, on a une base (U,V)

Pour projeter un point P dans la base, on calcule le produit scalaire de AP avec les vecteurs U, V de la base. Les coordonnées de P dans la base U,V sont (i,j) avec i = AP.U et j = AP.V (produit scalaire)

[fleurdelys77]

Merci pour le détail