の境界上のすべての点の陰にある の内部に点が存在する場合、多角形
Pは星型です。このようなすべてのポイントのセットは、 のカーネルと呼ばれます。pPPpP
たとえば、五芒星では、P光源を無限遠と見なすと、 の境界上にあるすべての点の影から中心点に到達できます。スター ポリゴンは必ずしも星形であるとは限りません。
反時計回りの順序で頂点によって指定された n 頂点の星形の多角形が与えられた場合P、線形時間でこの多角形の凸包を計算する方法。
この質問には手がかりがありません。私が考えることができるアルゴリズムは O(n * log(n)) です。この余分な情報の使い方がわかりません。
これは何らかの宿題だと思います。授業で課されているか、自分の勉強のために割り当てられているかに関係なく、ヒントだけを示します。
ここで重要なのは、反時計回りの順序です。より正確には、頂点が一貫した順序になっているという事実です。
3 つの連続する頂点 p 1、p 2および p 3が与えられた場合、次のように定義される 2 つのベクトルを考えてみましょう。
V 1 = (p 1 - p 2 ) および
V 2 = (p 3 - p 2 )。
外積 V 1 x V 2について何がわかっていますか? p 2が多角形の境界上にある場合と中心にある場合、この値はどのように異なるでしょうか? これに対する正解は、頂点を 2 つのクラスに分割する必要があります。これらのクラスは、反時計回りではなく時計回りの順序でどのように異なるでしょうか?