これは 2 次元計算幾何学の問題です。
穴のない平面にコンパクトな集合 X があるとします (つまり、単純に接続されています)。w をベクトルとし、X と X+w の交点 (つまり、X を w で変換したもの) を考えます。次のことが当てはまる場合、この交差点は複雑であると言います。
- X は X+w と交差します
- Y を (X 和 X+w) から有界の穴を埋めることによって得られる単結合領域とすると、Y の境界を歩き回ると、循環順序 a、b、c、d で 4 つの点を見つけることができます。 a と c は X 内にあるが X+w 内にはなく、b と d は X+w 内にあるが X 内にはないような境界上。
簡潔にするために、X と X+w の交差が複雑なwの集合を X の凹包と呼びましょう(注: これはアルファ集合とは関係ありません。単なる名前です)。
X が (たとえば) 多角形ディスクである X の凹包を計算するための高速で実用的なアルゴリズムを知りたいです。これを超えて、おそらく別の用語での凹型船体のエレガントな特徴付けに興味があります. 最後に、この問題について議論している文献へのポインタを教えていただければ幸いです。
以下にいくつかの注意事項を示します。
- X の凹包は、X が凸の場合にのみ空になります (したがって名前が付けられています)。これは、X が凸で、X が X+w と交差する場合、Y の境界が正確に 2 つのコンポーネントに分類されるためです。1 つは X にあり、もう 1 つは X+w にあります (逆は、以下のポイント 3 から続きます)。
- 多角形の凹包は、開いた多角形 (つまり、境界が取り除かれたもの) でなければならないため、(たとえば) (開いた) 三角形の有限結合として答えを与えることができます。
- X が凸でない場合、次のように凹包の一部を見つけることができます。L を X のサポート ラインとし、2 つのセット P と Q でギャップ I を介して X と交差します。J が P と Q の間の X の境界のセグメントである場合、I と J の和集合は、X の補数で開いたディスク D を境界付け、p+ が Q に最も近い P の極値である場合、D-p+凹型船体にあります。すべてのサポート ライン上のこのような領域の結合を内側の凹包と呼びます。計算は比較的簡単に思えますが、一般的には凹包よりも小さくする必要があると思います。