Algo k-DOP en 2D

Bonjour,

Je recherche l'algorithme pour générer des k-dop sur des polygons 2D (même 3D je m'adapterai).
J'ai tenté de le coder par moi même mais je dois louper quelque chose : la position de mes plans de coupe ne correspond pas au résultat escompté.

Merci par avance.

A tout hasard je poste mon pseudo-code :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

Pour chaque point Pi du polygon, - j'évalue la normale en Pi : normale(Pi) = normale( [Pi-1; Pi+1] ) Pour chaque plan de coupe S - calcule du produit scalaire : normale(S).normale(Pi) - si ce produit est le min des produits préc. calculés, j'associe ce point à S - si ce produit est le max des produits préc. calculés, j'associe ce point à S Fin Pour Fin Pour   Pour chaque plan j'ai (donc) les deux positions qui vont déterminer les bornes de mon k-dop.

---

Voilà par exemple le résultat que j’obtiens sur un 8-DOP avec une forme relativement complexe :

http://img213.imageshack.us/img213/5452/kdop.png

Les points trouvés répondent bien au critère de l'algo mais ils ne forment pas une boite englobante.
Le polygone doit-il être convexe ?
Comme les seuls exemples que j'ai trouvé sur le net sont très simple, il y a t-il d'autres critères ?