4点から領域を作る その1 ～四角形編～

#前提条件

• 4点 A,B,C,D が二次元座標上に入力される
• 連続する3点以上が同一直線上に並ばない
• A -> B -> C -> D -> A と直線で結ぶ

この条件から得られる図形 ABCD の形を点 A, B, C, D の座標から計算した値を用いて判別することが目的です。

#今回の内容
今回は上記の条件で得られる図形 ABCD のうち、標準的な四角形の判別について取り上げます。

例：標準的な四角形

他の図形については別の記事で取り上げます。

4点から領域を作る その1 ～四角形編～（この記事）
4点から領域を作る その2 ～蝶型、V字型編～
[4点から領域を作る その3 ～三角形、スリッパ型、直線編～] (https://qiita.com/tf_okrt/items/80ca63863068f642636f)

#線分交差判定

ここで有用な手法として、線分の交差判定で用いられる、2点から得られる直線に対する他の2点の存在領域の判別手法を用います。

線分交差判定で検索していただければ計算式はわかりますが、概要を以下に記します。

例として、点 $ A(x_{A}, y_{A}) $, 点 $ B(x_{B}, y_{B}) $ の2点からなる直線 $ AB $ が平面を分割することで得られる2領域について、点 $ C(x_{C}, y_{C}) $, 点 $ D(x_{D}, y_{D}) $ の2点が同じ領域に存在するかどうかを判定します。

直線 $ AB $ の方程式は座標 $ (x_{A}, y_{A}), (x_{B}, y_{B}) $ を用いて以下の様に示されます。

y-y_{A} = \frac{y_{A}-y_{B}}{x_{A}-x_{B}}(x-x_{A})

この式を変形すると、以下の通りとなります。

(y_{A}-y_{B})(x-x_{A})-(x_{A}-x_{B})(y-y_{A})=0

ここで得られる $ (y_{A}-y_{B})(x-x_{A})-(x_{A}-x_{B})(y-y_{A}) $ が直線 $ AB $ から得られる2領域のいずれに存在するかの判定式となります。

この判定式にある一方の領域に存在する点の座標を代入すると正の値となり、もう一方の領域に存在する点の座標を代入すると負の値となります。

この事実を利用して、点 $ C $ の座標を代入した値 $ AB_{C} $ を以下のように計算し、

AB_{C} = (y_{A}-y_{B})(x_{C}-x_{A})-(x_{A}-x_{B})(y_{C}-y_{A})

点 $ D $ の座標を代入した値 $ AB_{D} $ を以下のように計算し、

AB_{D} = (y_{A}-y_{B})(x_{D}-x_{A})-(x_{A}-x_{B})(y_{D}-y_{A})

$ V_{AB} = AB_{C}AB_{D} $ の値を計算すると以下の判定が行えます。

$ V_{AB} $	直線 $ AB $ から見た点 $C, D$
+	同じ領域
-	異なる領域

実際に線分交差判定を行う場合は直線 $ CD $ から見た点 $A, B$ についても計算を行う形となります。

#判定式の値と実際の図形

また、先ほど導出した $ V_{AB} = AB_{C}AB_{D} $ の値がプラスになる場合に得られる図形は以下の3つのうちのいずれかです。

また、$ V_{AB} = AB_{C}AB_{D} $ の値がマイナスになる場合に得られる図形は以下の2つのうちのいずれかです。

図形を見てわかる通り、まずは $ V_{AB} = AB_{C}AB_{D} $ の値がプラスにならないことには今回対象としている図形を得ることができないことが分かります。

#得られる図形を判定式で区別

ここで、$ V_{AB} > 0 $ で得られる図形に関して、$ V_{AB} $ だけでなく、$ V_{BC}, V_{CD}, V_{DA} $ についても同様に計算すると以下の様な結果となります。
（上記画像の左から図形1, 図形2, 図形3とします）

図形	$ V_{AB} $	$ V_{BC} $	$ V_{CD} $	$ V_{DA} $
図形1	+	+	+	+
図形2	+	-	+	-
図形3	+	-	-	+

図形3に関しては、類型として∠BCDではなく∠CDAが凹みとなっているパターンもありますが、この場合は以下の結果の通り、$ V_{BC} $ と $ V_{DA} $ の正負が入れ替わる形となります。

図形	$ V_{AB} $	$ V_{BC} $	$ V_{CD} $	$ V_{DA} $
図形3類型	+	+	-	-

上記の結果を基に考えると、今回対象としている図形である図形1は
$ V_{AB}>0 $ かつ $ V_{BC}>0 $ かつ $ V_{CD}>0 $
となればよいことが分かります。

#今後の予定

今回は標準的な四角形について取りあげましたが、次回の その2 では点の位置関係の考え方を拡張し、図形2のような蝶型や図形3のようなV字型に関する検証を行っていきます。

また、その3 では その2 の内容を踏まえて、前提条件の一つである「3点以上が同一直線上に並ばない」を撤廃して4点を自由に置いた場合の図形についても検証します。