4点から領域を作る その2 ～蝶型、V字型編～

#はじめに
この記事は [その1] (https://qiita.com/tf_okrt/items/f108e8459f860dbfaf96) の記事の内容を前提としています。
まだ [その1] (https://qiita.com/tf_okrt/items/f108e8459f860dbfaf96) の記事を読んでない場合はそちらをご覧ください。

#前提条件

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

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

#今回の内容
今回は上記の条件で得られる図形 ABCD のうち、蝶型とV字型の判別について取り上げます。

例：蝶型

例：V字型

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

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

#領域判定のおさらい

その1ではある2点を構成される直線から見た他の2点が同じ領域にあるかどうかを判定する式を用いて四角形となる条件を判定しました。

例：直線 $ AB $ から見た点 $ C, D $ に対する判定

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

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$ についても計算を行う形となります。

#点の位置関係による考え方

その1の記事では $ V_{AB} = AB_{C}AB_{D} $ の値がプラスになる場合とマイナスになる場合で得られる図形を羅列し、そこから更に $ V_{BC}, V_{CD}, V_{DA} $ についても同様に計算して四角形となる条件を導き出しました。

今回は考え方を拡張し、点 $A, B, C$ が同一直線上に存在しないように配置した上で、最後の点 $ D $ を他の2点からなる直線上に存在しないように配置することで出来上がる図形について考えます。

点 $ D $ が存在することが可能な領域を他の2点が作る直線で分割すると以下の図のようになります。

上記で示した7つの領域に関して、それぞれ点 $ D $ を置いた場合に得られる図形と $ V_{AB}, V_{BC}, V_{CD}, V_{DA} $ について計算すると以下の様な結果となります。

領域番号	図形	$ V_{AB} $	$ V_{BC} $	$ V_{CD} $	$ V_{DA} $
1	V字型	-	+	+	-
2	蝶型	-	+	-	+
3	V字型	+	+	-	-
4	四角形	+	+	+	+
5	V字型	-	-	+	+
6	蝶型	+	-	+	-
7	V字型	+	-	-	+

結果の精査

その1では結果として、$ V_{DA} $ を除いた $ V_{AB}, V_{BC}, V_{CD} $ の3つの値の正負で判定が行えました。
上記の結果を見ると、領域間で $ V_{AB}, V_{BC}, V_{CD} $ の3つの正負のパターンが同じになることが無いので、蝶型やV字型の判定においても $ V_{AB}, V_{BC}, V_{CD} $ の3つの値で判定を行うことが可能であることが分かります。

ここで上記の結果から不要な領域番号と $ V_{DA} $ を除外し、行の並びを同じ図形が並ぶように置き換えると以下の様になります。

図形	$ V_{AB} $	$ V_{BC} $	$ V_{CD} $
四角形	+	+	+
蝶型	-	+	-
蝶型	+	-	+
V字型	-	+	+
V字型	-	-	+
V字型	+	+	-
V字型	+	-	-

上記の結果から実直に $ V_{AB}, V_{BC}, V_{CD} $ の正負のパターン分けで図形を分類しようとすると最大3回の判定が必要になります。
そこで、更に少ない回数で図形の判定を行えるようにするため、$ V_{AB}, V_{BC}, V_{CD} $ の互いの積についても正負を計算します。

図形	$ V_{AB} $	$ V_{BC} $	$ V_{CD} $	$ V_{AB}V_{BC} $	$ V_{BC}V_{CD} $	$ V_{AB}V_{CD} $
四角形	+	+	+	+	+	+
蝶型	-	+	-	-	-	+
蝶型	+	-	+	-	-	+
V字型	-	+	+	-	+	-
V字型	-	-	+	+	-	-
V字型	+	+	-	+	-	-
V字型	+	-	-	-	+	-

図形の分類と $ V_{AB}, V_{BC}, V_{CD} $ の互いの積に注目すると、以下の条件分岐で判定を行えることが分かります。

if(Vab * Vcd < 0) {
    return 'V字型';
} else if(Vab * Vbc < 0) {
    return '蝶型'; 
} else {
    return '四角形';
}

これにより、その1と同じ $ V_{AB}, V_{BC}, V_{CD} $ を用いて最大2回の判定で四角形、蝶型、V字型の分類ができるようになりました。

#今後の予定

今回は四角形、蝶型、V字型について取りあげましたが、次回の その3 ではいよいよ前提条件の一つである「3点以上が同一直線上に並ばない」を撤廃し、4点を自由に置いた場合の図形について検証します。