#はじめに
この記事は [その1] (https://qiita.com/tf_okrt/items/f108e8459f860dbfaf96) と [その2] (https://qiita.com/tf_okrt/items/916c763303b043fdd69f) の記事の内容を前提としています。
まだ上記の記事を読んでない場合はそちらをご覧ください。
#前提条件
その2までは
- 4点 A,B,C,D が二次元座標上に入力される
- 連続する3点以上が同一直線上に並ばない
- A -> B -> C -> D -> A と直線で結ぶ
の3つの条件から得られる図形 ABCD の形を点 A, B, C, D の座標から計算した値を用いて判別することでしたが、この記事では、「連続する3点以上が同一直線上に並ばない」を撤廃し、
- 4点 A,B,C,D が二次元座標上に入力される
- A -> B -> C -> D -> A と直線で結ぶ
の2つの条件から得られる図形 ABCD の形を点 A, B, C, D の座標から計算した値を用いて判別することが目的です。
#今回の内容
今回は上記の条件で得られる図形 ABCD のうち、三角形とスリッパ型、および領域とならない直線の判別について取り上げます。
例：三角形
例：スリッパ型
他の図形については過去の記事で取り上げます。
4点から領域を作る その1 ～四角形編～
[4点から領域を作る その2 ～蝶型、V字型編～] (https://qiita.com/tf_okrt/items/916c763303b043fdd69f)
4点から領域を作る その3 ～三角形、スリッパ型、直線編～（この記事）
#領域判定のおさらい
その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$ についても計算を行う形となります。
#連続する3点以上が同一直線上に並ぶとき
連続する3点以上が同一直線上に並ぶ場合、判定式の値がどうなるかを点 $A, B, C$ が同一直線上にある場合の $ V_{AB} $ を例に紐解きます。
その1で触れましたが、直線 $ AB $ の方程式は座標 $ (x_{A}, y_{A}), (x_{B}, y_{B}) $ を用いて以下の様に示されます。
y-y_{A} = \frac{y_{A}-y_{B}}{x_{A}-x_{B}}(x-x_{A})
この直線上に点$ C (x_{C}, y_{C}) $ は存在するため、当然ながら、
y_{C}-y_{A} = \frac{y_{A}-y_{B}}{x_{A}-x_{B}}(x_{C}-x_{A})
の等式が成立します。（この等式を式$A$とします）
ここで、判定式 $ V_{AB} = AB_{C}AB_{D} $ のうち、点$ C $が関与する$ AB_{C} $の式は
AB_{C} = (y_{A}-y_{B})(x_{C}-x_{A})-(x_{A}-x_{B})(y_{C}-y_{A})
であるため、式$A$を基に、$ y_{C}-y_{A} $ の部分に代入すると以下の様に計算できます。
AB_{C} = (y_{A}-y_{B})(x_{C}-x_{A})-(x_{A}-x_{B})\frac{y_{A}-y_{B}}{x_{A}-x_{B}}(x_{C}-x_{A})
= (y_{A}-y_{B})(x_{C}-x_{A})-(y_{A}-y_{B})(x_{C}-x_{A})
= 0
上記の結果により、判定式 $ V_{AB} $ は $ V_{AB} = 0 $ となることが分かります。
この際、直線 $ BC $ 上に点$A$が存在するという形でも考えることができるため、$ V_{BC} = BC_{A}BC_{D} $ においても同様の手順で $ BC_{A} = 0 $ となり、$ V_{BC} = 0 $ も同時に成立することが分かります。
よって、点 $A, B, C$ が同一直線上にある場合、中心の点$B$が関与する$ V_{AB}, V_{BC} $の両方が 0 となります。
#連続する2点が重なるとき
連続する3点以上が同一直線上に並ぶ場合の中でも更に特殊な状況としては、連続する2点が全く同じ座標という状況があります。この場合に判定式の値がどうなるかを点 $B, C$ が同じ座標である場合を例に紐解きます。
図の実例としては以下の通りです。
点 $B, C$ が同じ座標である場合、点 $A, B, C$ が同一直線上に存在し、同時に、点 $ B, C, D$ が同一直線上に存在するため、上記で触れたとおり、$ V_{AB} $と$ V_{CD} $に関しては0になることが分かります。
では、V_{BC} = BC_{A}BC_{D} $ についてどうなるかというと、
BC_{A} = (y_{B}-y_{C})(x_{A}-x_{B})-(x_{B}-x_{C})(y_{A}-y_{B})
BC_{D} = (y_{B}-y_{C})(x_{D}-x_{B})-(x_{B}-x_{C})(y_{D}-y_{B})
であることを念頭に置き、点$B (x_{B}, y_{B}) $と点$C (x_{C}, y_{C}) $が同じ座標である、つまり、$ x_{B} = x_{C} $ かつ $ y_{B} = y_{C} $ であることを考慮すると、
BC_{A} = 0
BC_{D} = 0
となり、$ V_{BC} = 0 $ であることが分かります。
ここまでの内容を踏まえたうえで、2点が重なる場合に得られる図形と $ V_{AB}, V_{BC}, V_{CD}, V_{DA} $ について計算すると以下の様な結果となります。
| 図形 | $ V_{AB} $ | $ V_{BC} $ | $ V_{CD} $ | $ V_{DA} $ |
|---|---|---|---|---|
| 三角形 | + | 0 | 0 | 0 |
| 三角形 | 0 | + | 0 | 0 |
| 三角形 | 0 | 0 | + | 0 |
| 三角形 | 0 | 0 | 0 | + |
#直線上を点を動かす
続いて、2点が重ならないようにしながら連続する3点が同一直線上に存在する場合に得られる図形と $ V_{AB}, V_{BC}, V_{CD}, V_{DA} $ について計算するための方法を考えます。
手法としてはその2で使用した手法を参考に、連続する3点が同一直線上に存在しないように配置した上で、連続する3点のうち両端の2点からなる直線上に最後の点を存在させるように配置することで出来上がる図形について考えます。
例として、点$A, B, C$ が同一直線上に存在しないように配置し、直線$ AC $上で最後の点 $ D $ が存在できる領域については以下の図のようになります。
上記で示した領域に関して、連続する3点の組み合わせ4種類のそれぞれの領域 $1$～$3$ に残りの点を置いた場合の $ V_{AB}, V_{BC}, V_{CD}, V_{DA} $ について計算すると以下の様な結果となります。
| 3点と領域 | 図形 | $ V_{AB} $ | $ V_{BC} $ | $ V_{CD} $ | $ V_{DA} $ |
|---|---|---|---|---|---|
| $ABC_{1}$ | スリッパ型 | - | + | 0 | 0 |
| $ABC_{2}$ | 三角形 | + | + | 0 | 0 |
| $ABC_{3}$ | スリッパ型 | + | - | 0 | 0 |
| $BCD_{1}$ | スリッパ型 | 0 | - | + | 0 |
| $BCD_{2}$ | 三角形 | 0 | + | + | 0 |
| $BCD_{3}$ | スリッパ型 | 0 | + | - | 0 |
| $CDA_{1}$ | スリッパ型 | 0 | 0 | - | + |
| $CDA_{2}$ | 三角形 | 0 | 0 | + | + |
| $CDA_{3}$ | スリッパ型 | 0 | 0 | + | - |
| $DAB_{1}$ | スリッパ型 | + | 0 | 0 | - |
| $DAB_{2}$ | 三角形 | + | 0 | 0 | + |
| $DAB_{3}$ | スリッパ型 | - | 0 | 0 | + |
領域にならない点の配置
ここまでで、2点からなる直線上に関して多くの位置に点を置いた場合を検証してきましたが、ここまでで扱えていない点の配置があります。
その1つが4点全てが同一直線上に存在する場合です。
例図
4点全てが同一直線上に存在する場合、いずれの連続する3点においても同一直線上に存在するため、$ V_{AB}, V_{BC}, V_{CD}, V_{DA} $ の全てが 0 となります。
また、もう1つの配置が、連続しない2点が全く同じ座標の場合です。
例図
左側の配置であれば、点$D, A, B$ が同一直線上に存在することから$ V_{AB}, V_{DA} $が 0 となり、点$B, C, D$ が同一直線上に存在することから$ V_{BC}, V_{CD} $が 0 となるので、$ V_{AB}, V_{BC}, V_{CD}, V_{DA} $ の全てが 0 となります。
右側の配置であれば、点$A, B, C$ が同一直線上に存在することから$ V_{AB}, V_{BC} $が 0 となり、点$C, D, A$ が同一直線上に存在することから$ V_{CD}, V_{DA} $が 0 となるので、同様に$ V_{AB}, V_{BC}, V_{CD}, V_{DA} $ の全てが 0 となります。
上記の内容をまとめると、領域を構成できない直線だけとなる場合は$ V_{AB}, V_{BC}, V_{CD}, V_{DA} $ の全てが 0 となります。
結果の精査
ここまでで触れてきた$ V_{AB}, V_{BC}, V_{CD}, V_{DA} $の符号と得られる図形をまとめて並べると以下の様になります。
| 図形 | $ V_{AB} $ | $ V_{BC} $ | $ V_{CD} $ | $ V_{DA} $ |
|---|---|---|---|---|
| 三角形 | + | 0 | 0 | 0 |
| 三角形 | 0 | + | 0 | 0 |
| 三角形 | 0 | 0 | + | 0 |
| 三角形 | 0 | 0 | 0 | + |
| スリッパ型 | - | + | 0 | 0 |
| 三角形 | + | + | 0 | 0 |
| スリッパ型 | + | - | 0 | 0 |
| スリッパ型 | 0 | - | + | 0 |
| 三角形 | 0 | + | + | 0 |
| スリッパ型 | 0 | + | - | 0 |
| スリッパ型 | 0 | 0 | - | + |
| 三角形 | 0 | 0 | + | + |
| スリッパ型 | 0 | 0 | + | - |
| スリッパ型 | + | 0 | 0 | - |
| 三角形 | + | 0 | 0 | + |
| スリッパ型 | - | 0 | 0 | + |
| 直線 | 0 | 0 | 0 | 0 |
まず、内容を見るとその2までのように$ V_{DA} $を除外して図形の判定を行うことができないことが分かります。
上記の結果から実直に $ V_{AB}, V_{BC}, V_{CD}, V_{DA} $ の+, -, 0のパターン分けで図形を分類しようとすると多くの判定が必要となります。
そこで、その2と同様に更に少ない回数で図形の判定を行えるようにするため、負の値の個数も計測します。
以下の表が、図形毎に並び替え、負の個数の列を追加した結果です。
| 図形 | $ V_{AB} $ | $ V_{BC} $ | $ V_{CD} $ | $ V_{DA} $ | 負の個数 |
|---|---|---|---|---|---|
| 三角形 | + | 0 | 0 | 0 | 0 |
| 三角形 | 0 | + | 0 | 0 | 0 |
| 三角形 | 0 | 0 | + | 0 | 0 |
| 三角形 | 0 | 0 | 0 | + | 0 |
| 三角形 | + | + | 0 | 0 | 0 |
| 三角形 | 0 | + | + | 0 | 0 |
| 三角形 | 0 | 0 | + | + | 0 |
| 三角形 | + | 0 | 0 | + | 0 |
| スリッパ型 | - | + | 0 | 0 | 1 |
| スリッパ型 | + | - | 0 | 0 | 1 |
| スリッパ型 | 0 | - | + | 0 | 1 |
| スリッパ型 | 0 | + | - | 0 | 1 |
| スリッパ型 | 0 | 0 | - | + | 1 |
| スリッパ型 | 0 | 0 | + | - | 1 |
| スリッパ型 | + | 0 | 0 | - | 1 |
| スリッパ型 | - | 0 | 0 | + | 1 |
| 直線 | 0 | 0 | 0 | 0 | 0 |
図形の分類、負の個数、直線は全て0であることに注目すると、以下の条件分岐で判定を行えることが分かります。
if(Vab == 0 && Vbc == 0 && Vcd == 0 && Vda == 0) {
return '直線';
} else if(Vab < 0 || Vbc < 0 || Vcd < 0 || Vda < 0) {
return 'スリッパ型';
} else {
return '三角形';
}
これにより、$ V_{AB}, V_{BC}, V_{CD}, V_{DA} $ を用いて最大2回の判定で三角形、スリッパ型、直線の分類ができるようになりました。
#全体の総まとめ
ここで、その2までの内容と併せて、全体的な図形の判定基準をまとめようと思います。
その2まででは前提条件であった「連続する3点以上が同一直線上に並ばない」という内容から得られる特徴としては以下が挙げられます。
・その2までの判定式で値が0になることはない
・その3で出てくる判定式では、必ず2つ以上が0になる
この特徴を基に考えると、以下の様に判定することができます。
| $ V_{AB}V_{BC}V_{CD} $ の値 | 用いるべき判定基準 |
|---|---|
| ≠0 | その2 |
| =0 | その3 |
よって、上記の判定とこれまでに出てきた判定基準を繋ぎ合わせると以下の様に判定できます。
if(Vab * Vbc * Vcd == 0) {
if(Vab == 0 && Vbc == 0 && Vcd == 0 && Vda == 0) {
return '直線';
} else if(Vab < 0 || Vbc < 0 || Vcd < 0 || Vda < 0) {
return 'スリッパ型';
} else {
return '三角形';
}
} else {
if(Vab * Vcd < 0) {
return 'V字型';
} else if(Vab * Vbc < 0) {
return '蝶型';
} else {
return '四角形';
}
}