2D ポリゴンの頂点が与えられた場合、X軸上のポリゴンの可能な限り最小の投影を見つける必要があります。
ポリゴンを任意の角度で回転させることができます。
最初は、最小のケースとして、ポリゴンの辺の少なくとも 1 つがX軸に揃えられると考えていましたが、これは正しくありません。
多角形は、凹面または凸面にすることができます。
3 に答える
2
コメントに記載されているように、ポリゴンを凸包に置き換えても答えは変わりません。それでは、多角形はすでに凸面であると考えてみましょう。ここで、最小角度を見つけたとします。これは、Y 軸に平行なストリップがボディの境界になっていることを意味します。ポリゴンの側面の 1 つがストリップの境界上にあることが簡単にわかります (そうでない場合は、ストリップの幅を広げずにボディを少し回転させることができます)。
要約すると、アルゴリズムが得られます: 凸包を計算し、次に包の各辺について Y に平行になる角度を選択し、幅をテストします。分を取ります。0
于 2013-11-06T09:09:25.980 に答える
0
X(i, alpha) を、角度 alpha だけ回転した後の頂点 i の X 座標とする。
-PI <= alpha <= PI を常に想定しています。
すべての j について X(i, alpha)>=X(j, alpha) の場合、i=rightmost(alpha) とします。1 つを除くすべての j について X(i, alpha)>=X(j,alpha) の場合、i=second_rightmost(alpha) とします。同様に leftmost() と second_leftmost() を定義します。
次のことを証明しましょう: X(i, alpha) >= X(j, alpha), and X(i, beta) >= X(j, beta), and beta-alpha < PI, then X(i, gamma) >= [alpha, beta] のすべてのガンマに対して X(j, gamma)。実際、X(i, alpha)=x[i]*cos(alpha)-y[i] * sin(alpha) であり、ここで (x[i], y[i]) は頂点 i の初期位置です。したがって、X(i, a) - X(j, a) = c1*cos(a)-c2*sin(a)、c1=x[i]-x[j]、c2=y[i]- y[j]。f(a)=X(i,a)-Y(i,a)とする。関数 f は連続関数で、tan(a)=c1/c2、つまり a=atan2(c1,c2)+PI*n のときに符号が変わります。ベータアルファの場合
これで、次のようになりました。
- rightmost(alpha)=rightmost(beta) かつ beta-alpha < PI の場合、すべての alpha < x < beta について rightmost(x)=rightmost(alpha) です。
- i=rightmost(alpha)=second_rightmost(beta)、j=rightmost(beta)=second_rightmost(alpha)、および beta-alpha < PI の場合、alpha と beta の間のすべての x について、rightnost(x) は i またはj であり、変更点は atan2(y[i]-y[j], x[i]-x[j]) です。
これは、二分探索でどの間隔でどの点が最も右であるかを取得するのに十分です。角度の符号反転により、左端の点間隔が得られます。各点がどの間隔で最も左にあり、各点が最も右にあるかがわかっているため、間隔間の境界で値を計算し、最小のものを選択できます。
于 2013-11-06T09:38:45.000 に答える