意外と簡単！交差数から見る内外判定
こんにちは。
製造建設ソリューションサービス部の村上です。
突然ですが、以下の図を見たときに赤い点が四角枠の外側にあるか内側にあるか、皆さんは一発で見て分かると思います。
もちろん内側にありますね。
しかしこれをプログラムで処理するときに、赤い点が内側にあるか外側にあるか判別する為にはどうすればよいのか…。
分かる人は多くないと思います。
では実際にどうすれば判別できるのか調べてみますと、結構難しい説明をしているサイトが多々ヒットします。
この内外判定のアルゴリズムについては様々なアルゴリズムが存在しており、使用する状況や求める精度に応じて適切な難易度のアルゴリズムを選択しなければなりません。
そこで今回は、一番簡単で分かりやすい「交差数から見る内外判定」をご紹介したいと思います！
交差数とは
まず始めに、交差数って何だ？と思われたと思います。
ここで言う交差数とは、内側にあるのか外側にあるのか調べたい物体から引いた線が、外側の枠線と交差する回数のことを言います。
今回の場合では、赤い点から引いた線が、四角枠と交差する回数ということになります！
(下図では赤い点から下方向に線を引いていますが、これは上下左右どの方向に引いても問題ありません。)
さて、今回の場合は引いた線が四角枠と1回だけ交差していることが分かります。
では次に、赤い点が四角枠の外側にある場合ではどうでしょうか？
赤い点が四角枠の外側にある場合では、引いた線が四角枠と2回交差していることが分かります。
では、四角枠が複雑な図形の場合はどうでしょうか？
この場合では引いた線が外枠と3回交差していることが分かります。
結論
ここまでの内容をまとめると、以下の定義が考えられます。
- 赤い点が四角枠の内側にある場合、赤い点から引いた線は奇数回だけ四角枠と交差する。
- 赤い点が四角枠の外側にある場合、赤い点から引いた線は偶数回だけ四角枠と交差する。
(交差しない場合も考えられる)
つまり赤い点から引いた線と四角枠の交差回数をみるだけで、赤い点が四角枠の内側にあるのか外側にあるのかは判別可能！ということですね！！
とても簡単に求めることができるということがイメージしていただけたと思います。
応用
今回説明した「交差数から見る内外判定」のアルゴリズムですが、これは一番簡単な内容となっています。
つまり、さらに精度が求められる複雑な内外判定になってくると、このままでは使えないということです。
しかし使えないといっても、このアルゴリズムを全部変えなくてはいけないということではありません！
この考え方は、複雑になっていく内外判定のベースのロジックとして利用することができる考え方です。
ですので、もっと難しい内外判定を行いたい！というときには、このロジックをベースにして、さらに色々な内外判定の条件を考えてみてください。
AutoCADで実装してみた
最後に、今回説明した内外判定のロジックをAutoCADのカスタマイズとして実装してみました。
AutoCADを用いる場合、対象物から引いた線と四角枠の交差回数をカウントしている部分は以下のように実装できます。
public List SearchIntersectPoint(List areaLineList, Line line)
{
// areaLineList:四角枠の線分リスト
// line:対象物から引いた線
// 交差座標の保持
List keepIntersectList = new List();
foreach (Line areaLine in areaLineList)
{
Point3dCollection collection = new Point3dCollection();
areaLine.IntersectWith(line, Intersect.OnBothOperands, collection, IntPtr.Zero, IntPtr.Zero);
// 線分と線分の交点は一つしかありえない
if (0 < collection.Count && keepIntersectList.Contains(collection[0]) == false)
{
keepIntersectList.Add(collection[0]);
}
}
return keepIntersectList;
}
このコードを実装すれば、あとはこの回数が偶数なのか奇数なのかを見るだけです！
難しそうな内容でも、考え方次第では意外と簡単に実装できてしまうことがお分かりいただけたかと思います。
機会があれば、もっと色々な図形処理についてのアルゴリズムを簡単化して考えてみませんか？
▼キャパの公式Twitter・FacebookではITに関する情報を随時更新しています！
