半平面制約・凸領域の共通部分
概要
向き付き直線の左側を線形不等式とし、平行制約を最強の境界へ集約して凸領域の包含・共通部分を扱う。
考え方
反時計回りの凸多角形の頂点をv_i、辺方向をe_i=v_(i+1)−v_iとする(添字は巡回)。点zが多角形の内部または境界にある必要十分条件は、全辺について cross(e_i,z−v_i)≥0。凸性により辺の左半平面の共通部分がちょうど元の多角形になる。時計回りなら先に頂点列を逆にし、境界を含むかは不等号で固定する。
平行移動t_j後は cross(e_i,z)≥cross(e_i,v_i+t_j) となる。固定iでは左辺が全移動で同じなので、全多角形への包含は cross(e_i,z)≥H_i、H_i=max_j cross(e_i,v_i+t_j) と同値。各辺のH_iを前計算し、各query点についてN本を判定すればよい。全条件を満たす点がなければ共通部分は空だが、包含queryのために交点や共通部分の頂点を構築する必要はない。
集約できるのは同じ向き・同じ尺度の左辺を持つ制約である。逆向きの辺は上限と下限に対応する別条件になる。異なる多角形の一般の半平面共通部分を実際に構築する算法は、角度sortとdeque、平行線・非有界領域の処理を別途要し、この包含判定とは区別する。
成立条件と計算量
N辺、M個の平行移動、Q個の点queryならO(NM+NQ)時間、HのO(N)補助空間。外積は整数座標なら整数で比較できるが、積と差に必要な整数幅を確保する。非凸多角形では全辺の左半平面の共通部分が元の内部とは一致しない。
問題一覧
- ABC251 G「Intersection of Polygons」 公式問題
技能・出典
主題: 半平面制約・凸領域の共通部分(凸多角形を向き付き辺の線形半平面制約へ変換し、平行移動後も左辺が同じ制約を最強の右辺へ集約して共通部分への包含を判定できる。)。主タグ: 半平面制約・凸領域の共通部分
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 黄色(2000–2399)。凸多角形を辺ごとの半平面に変換し、平行移動した全領域への包含を最強の制約で判定する。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 凸境界・半平面制約を扱う。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-half-plane-constraints
半平面制約・凸領域の共通部分
習得する技能
- 凸多角形を向き付き辺の線形半平面制約へ変換し、平行移動後も左辺が同じ制約を最強の右辺へ集約して共通部分への包含を判定できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: 幾何の基本判定と座標変換。
このUnitを直接前提とする単元: なし。
幾何の基本判定・配置・座標変換で得た考え方と実装を再利用し、半平面制約・凸領域の共通部分の発動条件・正当化・境界を重複なく学ぶ。
このUnitでは扱わないもの
- 半平面制約・凸領域の共通部分の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。