まえがき
この記事は投稿者(NokonoKotlin)の個人サイトの記事から Qiita 用に移植 & 加筆したものです。 (この文言は記事が剽窃でないことを周知するためのものであり、個人サイトの宣伝ではないことをあらかじめご了承ください。)
注意
この記事は目指せ幾何マスター その 1 (ベクトル、凸包) の続きです。
多角形の面積
多角形の各頂点が与えられるとき、通常は適当な点 $O$ から時計回り (または反時計回り) の順に与えられます。与えられた点の列を $P$ とすると、$P$ において隣接する $2$ 点間、および $P$ の先頭と末尾の点の間に多角形の辺が存在します。逆にこれら以外に辺は存在しません。また $P$ から多角形は一意に定まります。
アルゴリズム
点 $O$ から移動をはじめ、辺に沿って反時計回りに多角形を一周します。すると、再度 $O$ に戻るまでに $|P|$ 回頂点間の移動が行われます。
$|P|$ 回の移動それぞれについて以下を計算し、それらの総和を計算します。ここで、一度の移動の始点と終点をそれぞれ $S , T$ とします。
- $S\rightarrow T$ の移動で線分 $OS$ が通る領域の符号付き面積
計算の様子
この操作で求めた符号付き面積の総和が、多角形の面積です。図を確認すると、符号付き面積の符号によってうまい具合に各領域の面積が重複しないように加算されていることが確認できます。
今回は反時計回りに調べましたが、時計回りに一周すると面積に $-1$ をかけた値になります。
線分の交差
平面座標系上に $2$ つの線分 $P,Q$ があります。$P,Q$ に交点が存在するかを判定し、存在するなら答えてください。
交点が存在するかどうか
判定の方法は様々ですが、今回は直感的にわかりやすい方法で行います。
まず、コーナーケースとして $P,Q$ の傾きが等しい場合を処理します。
この時、$P,Q$ の交点が存在することと以下の $4$ つの条件のいずれかを満たすことは等しいことが言えます。
- 点 $P_A$ が線分 $Q$ 上にある。
- 点 $P_B$ が線分 $Q$ 上にある。
- 点 $Q_A$ が線分 $P$ 上にある。
- 点 $Q_B$ が線分 $P$ 上にある。
点 $p$ が線分 $AB$ 上に存在する条件は、以下の $2$ つです。
- $x,y$ 座標それぞれについて、点 $p$ の座標が点 $A,B$ の座標の小さい方から大きい方までの間である。
- 線分 $Ap$ の傾きと線分 $pB$ の傾きが等しい。
以降、$P,Q$ の傾きは等しくないことを仮定して話します。
突飛かもしれませんが、線分 $Q$ のいずれかの端点 ($Q_A$ とします) が線分 $P$ のいずれかの端点に重なるように $Q$ を平行移動してできる平行四辺形を考えます。
お分かりですか？こうしてできる平行四辺形の辺は、線分$P,Q$ が交点を持つような $Q_B$ の境界となっています。
よって、線分 $P,Q$ が交点を持つ条件は、$Q_B$ が図の平行四辺形 $OSRU$ の内部または周上に存在することです。
ある点が多角形の内部に存在するかどうかは、その点と多角形の各辺によって $3$ 角形を作った時に、それらの $3$ 角形の面積の総和が多角形の面積と等しくなるかどうかを確かめることで判定できます。
面積の比較を行う際は、 $3$ 角形の面積の計算であらかじめ面積を $2$ 倍したものを計算することで誤差をなくすことができます。
これで交点が存在するかどうかの判定はできました。
交点の計算
交点が存在するとわかっているので、線分の式で連立方程式を立てて解けば良いと思われるかもしれません。しかし、線分の傾きが $90$ 度の場合に $0$ 徐算が発生してしまうので場合分けをする必要があります。
はじめに $P,Q$ の傾きが等しいコーナーケースを弾いているので、傾きが $90$ 度の線分が存在したとしても、$P,Q$ のいずれか一方のみです。
$Q$ の傾きが $90$ 度の場合、三角形の辺の比を考えることで、交点の位置ベクトル (座標) を簡単に計算できます。
また、$P$ の傾きが $90$ 度の場合、はじめにあらかじめ $P$ と $Q$ をスワップして考えることで、上記の場合に帰着させましょう。
ここまでくると、残りは $P,Q$ の傾きが互いに異なり、いずれも $90$ 度ではない場合なので、連立方程式を立てて解くことで交点が求まります。
