計算幾何(4) - やねうらおブログ(移転しました)
問) ある多角形の頂点列 Point[0],Point[1],…,Point[N-1]が与えられたときに、この多角形が凸多角形であるかどうかを判定するアルゴリズムを示せ。 但し、ここで言う凸多角形とはその内角がすべて180゜以下*1とする。 与えられた点を全て内包する最もタイトな(小さな)凸多角形を(点集合の)凸包と呼ぶ。凸包の示す領域とは要するに凸多角形の内側の領域である。凸包は交差判定などがしやすいので計算幾何で頻繁に問題になる。 コンピュータグラフィックスの世界でも、ポリゴンにテクスチャを貼り付けて描画するときにたいていの3Dシステムは転送元テクスチャの領域および転送先スクリーンの領域とは共に与えた頂点集合の凸包に制限される。よって凸包について正しく理解しておくことは非常に重要だ。 答) id:yaneurao:20070118で用意したCCW関数(robustなarg関数)を用いれ
なんとなく判定関数
なんでこれで調べられるかは……ここだと書きにくいんだよな。文中に画像が入れられないから。 というわけで、リストのみ投下してみる。気が向いたら、サイトのProgram Tipsの方に解説付きでうｐする予定。 ソース const double PI = 3.1415926535897932384626433f; inline double ConvertRadian(double Degree) { return Degree * PI / 180; } // 与えられたベクトルを回転させる // Rect &Vector : 回転させるベクトル // double TurnDeg : 回転角 void RotateVector(Rect &Vector, double Theta) { Rect V_dash = { Vector.x * cos(Theta) – Vector.y * s
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
