Calcul du rectangle de délimitation à un angle d'un polygone

Question

J'ai besoin de déterminer le rectangle de délimitation d'un polygone à un angle arbitraire. Cette image illustre ce que je dois faire:

alt text http://kevlar.net/RotatedBoundingRectangle.png

Le rectangle rose est ce que je dois déterminer à différents angles pour les polygones simples 2d.

Toutes les solutions sont très appréciées!

Edit:

Merci pour les réponses, je l'ai eu de travail une fois que je suis les points centraux correct. Vous êtes géniaux les gars!

Answer 1

Pour obtenir un cadre de délimitation avec un certain angle, faites pivoter le polygone dans le sens contraire. Ensuite, vous pouvez utiliser les coordonnées min/max x/y pour obtenir une boîte englobante simple et la faire pivoter selon l'angle pour obtenir votre résultat final. De votre commentaire, il semble que vous ayez des problèmes pour obtenir le point central du polygone. Le centre d'un polygone doit être la moyenne des sommes de coordonnées de chaque point. Donc, pour les points P1, ..., PN, calculer:

xsum = p1.x + ... + pn.x; 
ysum = p1.y + ... + pn.y; 
xcenter = xsum/n; 
ycenter = ysum/n; 

Pour que cela soit complète, j'ajoute aussi quelques formules pour la rotation en cause. Pour faire pivoter un point (x, y) autour d'un point central (cx, cy), procédez comme suit:

// Translate center to (0,0) 
xt = x - cx; 
yt = y - cy; 
// Rotate by angle alpha (make sure to convert alpha to radians if needed) 
xr = xt * cos(alpha) - yt * sin(alpha); 
yr = xt * sin(alpha) + yt * cos(alpha); 
// Translate back to (cx, cy) 
result.x = xr + cx; 
result.y = yr + cx; 

Answer 2

J'interprétation votre question signifie « Pour un polygone 2D donné, comment calculez-vous la la position d'un rectangle de délimitation pour lequel l'angle d'orientation est prédéterminé? " Et je le ferais en tournant le polygone contre l'angle d'orientation, puis utiliser une simple recherche de ses points maximum et minimum dans les deux directions cardinales en utilisant n'importe quel algorithme de recherche est approprié pour la structure les points du polygone sont stocké. (En termes simples, vous devez trouver les valeurs X les plus élevées et les plus basses, et les valeurs Y les plus élevées et les plus basses.)

Ensuite, les minima et les maxima définissent votre rectangle.

Vous pouvez faire la même chose sans faire d'abord pivoter le polygone, mais votre recherche de points minimum et maximum doit être plus sophistiquée.

Answer 3

Pour obtenir le plus petit rectangle, vous devez obtenir le bon angle. Cela peut s'accomplir par un algorithme utilisé dans la détection de collision: les boîtes de délimitation orientées. Les étapes de base:

Obtenir tous les sommets cordinates
Construire une matrice de covariance
Trouver les valeurs propres
projet tous les sommets dans l'espace
Trouver des valeurs propres max et min dans chaque espace de valeurs propres.

Pour plus d'informations que google OBB « Détection de colision »

Ps: Si vous projetez seulement tous les sommets et de trouver un maximum et minimum que vous faites AABB (axe boîte englobante aligné). C'est plus facile et nécessite moins d'effort de calcul, mais ne garantit pas la boîte minimale.

Answer 4

Pour obtenir un rectangle avec une zone minimale entourant un polygone, vous pouvez utiliser l'algorithme a rotating calipers. L'idée clé est que (contrairement à votre exemple d'image, donc je suppose que vous n'avez pas réellement besoin d'une zone minimale?), Un tel rectangle minimal est colinéaire avec au moins un bord de (la coque convexe) du polygone .