多角形の境界矩形を任意の角度で決定する必要があります。この写真は、私が何をする必要があるかを示しています。ポリゴンの角度での境界矩形の計算
alt text http://kevlar.net/RotatedBoundingRectangle.png
ピンクの長方形が、私はシンプルな2Dポリゴンの様々な角度で決定するために必要なものです。
解決策はありますか?
編集:答えを
おかげで、私は中心点が正しい得た後、それが働いて得ました。あなたは素晴らしいです!
多角形の境界矩形を任意の角度で決定する必要があります。この写真は、私が何をする必要があるかを示しています。ポリゴンの角度での境界矩形の計算
alt text http://kevlar.net/RotatedBoundingRectangle.png
ピンクの長方形が、私はシンプルな2Dポリゴンの様々な角度で決定するために必要なものです。
解決策はありますか?
編集:答えを
おかげで、私は中心点が正しい得た後、それが働いて得ました。あなたは素晴らしいです!
ある角度のバウンディングボックスを取得するには、その角度でもう一方の方法でポリゴンを回転させます。次に、最小/最大x/y座標を使用して簡単な境界ボックスを取得し、角度で回転させて最終結果を得ることができます。
あなたのコメントから、多角形の中心点を得ることに問題があるようです。ポリゴンの中心は、各点の座標合計の平均である必要があります。点P1のためだから、...、PNは、計算:
xsum = p1.x + ... + pn.x;
ysum = p1.y + ... + pn.y;
xcenter = xsum/n;
ycenter = ysum/n;
が、これは完全にするために、私も関与回転のためにいくつかの数式を追加します。私は与えられた2次元ポリゴンの」を意味するあなたの質問を解釈しています
// 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;
を、どのように計算します:中心点(CX、CY)の周りの点(x、y)を回転させるには、次の手順を実行します方位角が予め定められている境界矩形の位置?
そして、ポリゴンを回転角度に合わせて回転させ、ポリゴンのポイントが構造に適した検索アルゴリズムを使用して、2つの基本方向の最大値と最小値を簡単に検索します(最大値と最小値、そして最大値と最小値を見つける必要があります)
次に、最小値と最大値が長方形を定義します。
ポリゴンを最初に回転させずに同じことをすることはできますが、最小点と最大点の検索はより洗練されたものでなければなりません。
これは正しいです。 0回転のポリゴンに対して境界ボックスを計算して境界を回転させるべきではありません。これは大きすぎるbboxをもたらすかもしれません。私はAABB(軸が整列している)と仮定しています。 – ralphtheninja
最小の長方形を取得するには、正しい角度を取得する必要があります。これは、衝突検出に使用されるアルゴリズム、すなわち、指向されたバウンディングボックスによって達成することができる。 基本的な手順:
は、すべての頂点を取得
は固有値スペース内のすべての頂点
は、すべての固有値空間で最大と最小を探す固有値
プロジェクトを探す共分散行列
を構築cordinates。
詳細については
だけOBB「colision検出を」Googleの
シモンズ:あなたはちょうどあなたがAABB(軸整列バウンディングボックス)を作っているすべての頂点を投影し、最大と最小を見つけた場合。より簡単で計算の労力は少なくて済みますが、最小限のボックスを保証するものではありません。
ポリゴンを囲む最小限の領域で長方形を取得するには、a rotating calipersアルゴリズムを使用できます。
重要な洞察は、サンプル画像とは異なり、実際に最小限の領域を必要としないと仮定しているからです。そのような最小の矩形は、ポリゴンの(凸包の) 。
"さまざまな角度"とは、境界のある矩形がある角度にあるか、または内部の形状が一定の角度になっていなければならないということですか? – Welbog
ここではいくつかの角度を修正する必要がありますが、複数の解決策があります。 – Glenn
境界矩形の角度は変化します。私はポリゴンを逆方向に回転させ、その周囲に長方形をフィッティングし、長方形のポイントを回転させることを考えましたが、中心点を正しく識別することによって邪魔になると思います。 – kevin42