第33回 プログラミングについて 『ポリゴンの話3』

『ポリゴンの話3』

　「点がポリゴンの中にあるか否か」。これを調べるのもアルゴリズム的には簡単なのですが、実際のプログラムとなると結構厄介な問題なのです。まず下の図を見て下さい。

　　・ーーーー・　　　ｐ２
　　｜　　　　｜　　ｘ
　　・ーー・　｜
　　　　　｜　・ーーーーー・
　　　　　｜　　　　　　　｜
　　・ーー・　　　　　　　｜
　　｜　　ｐ１　　・ーーー・
　　｜　ｘ　　　　｜
　　｜　　　　　　｜
　　・ーーーーーー・

人間はｐ１がポリゴンの中にあって、ｐ２は外側にあるとすぐに分かります。やはり人間には不思議な能力がありますね。これをプログラムで判定するにはまずｐ１、ｐ２からＸ軸に垂直な線を引いてみます。

　　　　｜　　　　　｜
　　・ー＋ーー・　　｜ｐ２
　　｜　｜　　｜　　ｘ
　　・ー＋・　｜　　｜
　　　　｜｜　・ーー＋ーー・
　　　　｜｜　　　　｜　　｜
　　・ー＋・　　　　｜　　｜
　　｜　｜ｐ１　　・＋ーー・
　　｜　ｘ　　　　｜｜
　　｜　｜　　　　｜｜
　　・ー＋ーーーー・｜
　　　　｜　　　　　｜

ｐ１から引いた線がポリゴンと交差する点の数は４個あり、ｐ１より上には３個、下には１個です。ｐ２では全部で２個で上には０個下には２個です。これで検討がついたと思いますが、点から上または下に引いた線とポリゴンとの交点の数が奇数のときには内側、偶数のときには外側と判断することができます。

　ここまでは簡単な話です。むずかしいのは交点を求める線をどうやって決めるかなのです。下の図を見て下さい。

　　８　　　　７
　　・ーーーー・　　ｐ２
　　｜　 １０ ｜　ｘ
　９・ーー・　｜
　　　　　｜　・ーーーーー・５
　　　　　｜　６　　　　　｜
　　　ｐ１｜　　　　　　　｜
　　ｘ　　・１１　・ーーー・４
　　　　／　　　　｜３
　　　／　　　　　｜
　　・ーーーーーー・
　　１　　　　　　２

　ｐ１から垂線を引いたとき、辺１ー２、辺７ー８、辺９ー１０、辺１１ー１との交点はそれぞれの辺の末端に一致するので交点があるとすると、ｐ１よりも上にある交点の数は偶数、また下にある交点も偶数ですので、ｐ１は外側にあることになります。同じようにｐ２について見てみると、辺１ー２、辺３ー４、辺５ー６とで交点があります。
ｐ２よりも上にある交点の数は０個、下にあるのは３個で奇数ですから内側か外側かは判定できません。
　また、辺の末端に交点があるときにはそれを交点とは認めないとしても、ｐ１に対しては上も下も０個で、ｐ２に対しては上が０個、下が１個とこれも矛盾してしまいます。

一体何が間違っているのでしょうか？

　大きな間違いはないのすが、交点を求めるときに単純に直線と直線の交点を求めてしまったことが原因なのです。ここがポリゴン（折れ線のときにも言えますが）を処理する上で重要な性質なのです。
　交点を求める際に、交点が辺の端になるとき（端に近いとき）には特別な考慮をしなければならないのです。

　ｐ１を通る垂線との交点を求めるときをまず考えてみましょう。
最初に垂線は辺１ー２と交差しますが、このとき頂点１のＸ座標がｐ１のＸ座標と同じですので、交点は辺の端になります。このときには垂線に対する辺１１ー１と辺１ー２の関係を考慮しなければならないのです。その関係を抜き出してみましょう。

　　　ｐ１
　　ｘ　　・１１
　　｜　／
　　｜／
　　・ーーーーーー・
　　１　　　　　　２

　　（関係１）

このような関係のときには交点を求めないか、交点を求めるか（辺１１ー１と辺１ー２に対しそれぞれ１つずつ交点があるのでこの角の部分では交点が２個）のどちらかにします。

　次にｐ１の垂線と辺８ー７も同様に交点が辺の端にありますので、これもその部分を抜き出してみましょう。

　　８　　　　７
　　・ーーーー・
　　｜
　９・
　　｜
　　｜
　　｜ｐ１
　　ｘ

　　（関係２）

このようなときには、関係１と同様に交点を求めないか、交点を求めるか（辺７ー８との交点が１個）のどちらかにします。

　このようにして垂線とポリゴンが辺の端で交差するすべてのパターンを考えると、次の図のようになります。

　　１　　｜２　 ３　　　　　 ｜　　３　　　　　　｜
　　・ーー・ーー・　　　　　２・ーー・　　　　　　・３
　　　　　｜　　　　　　　　　｜　　　　　　　　　｜
　　　　　｜　　　　　　　　１・　　　　　１・ーー・２
　　　　　｜　　　　　　　　　｜　　　　　　　　　｜
　　　　　ｘ　　　　　　　　　ｘ　　　　　　　　　ｘ

　　（パターン１）　　　（パターン２）　　　 （パターン３）

　　　　 ｜　　・１　　　　　 ｜
　　　　 ｜　／　　　 １・ーー・２
　　　　 ｜／　　　　　　　 ／｜
　　　 ２・ーー・３　　　 ／　｜
　　　　 ｜　　　　　 ３・　　｜
　　　　 ｘ　　　　　　　　　 ｘ

　　（パターン４）　　　 （パターン５）

　この図で、それぞれのパターンと交点を考えてみましょう。

　　パターン１　交点を１つ求める。
　　パターン２　交点を求めない。
　　パターン３　交点を１つ求める。
　　パターン４　交点を求めない。
　　パターン５　交点を求めない。

　このようにすればいいことになります。要するに、「垂線とポリゴンの辺の交点が辺の第２ポイントになるときには、その辺の第１ポイントのが垂線より左側にあり、第２ポイントが垂線と同じか右側にあるときに交点を求める。」と言うことができます。

　それではこのことを頭に入れておいて次の図を考えてみましょう。

　　　　　　　　　　　　　・１２
　　　　　　　　　　　　／｜
　　　　 １４　　１３ ／　｜
　　　　　・ーーーー・　　｜
　　　　　｜　　　　　ｐ　・１１
　　　　　｜　　　　ｘ　／
　　　　　｜　　　　　／
　　　　　｜　　１０・ーー・９
　　　　　｜　　　　　　　｜
　　　　　｜　　　７・ーー・８
　　　　　｜　　　　｜
　　　　　｜　５　　｜
　　　　　｜　・ーー・６
　　　　　｜　｜
　　　　　｜　｜
　　　　　｜　・ーー・３
　　　　　｜　４　／
　　　　　｜　　／
　　　　　・ー・
　　　　　１　２

　点ｐを通る垂線がポリゴンと交わる部分の交点をリストアップしてみます。

　辺　２ー　３　交点が辺の第２ポイントですのでパターン５になります。これは交点
　　　　　　　　を求めません。

　辺　３ー　４　交点が辺の第１ポイントですので交点は求めません。

　辺　５ー　６　交点が辺の第２ポイントですのでパターン３になります。これは交点
　　　　　　　　を求めます。

　辺　７ー　８　交点が辺の第１ポイントですので交点は求めません。

　辺　９ー１０　交点が辺の第２ポイントですのでパターン４になります。これは交点
　　　　　　　　を求めません。

　辺１０ー１１　交点が辺の第１ポイントですので交点は求めません。

　辺１２ー１３　交点が辺の第２ポイントですのでパターン１になります。これは交点
　　　　　　　　を求めます。

　結果としては、頂点６と頂点１３の位置に交点が求まり、点の上には１つ点の下には１つとなり、点はポリゴンの内側にあることになります。

　ポリゴンにハッチングをかけたり、塗りつぶしを行なうときにも交点を正確に求めなければなりません。そのときにもここで考えたことを考慮する必要があります。ハッチングは塗りつぶしのときには、求められた交点をＸまたはＹの座標値でソートし、奇数番から偶数番の交点に線分をひくことで実現することができます。

　以前ＣＡＤシステムを作ったときにこの問題で苦労したことがありました。最初は単純に交点を求めて点の位置を調べたりハッチングをかけていたのです。自分でテストしている限りでは正常に動作したのですが、実際のデータでは全然駄目でバグのオンパレードとなってしまった経験があります。その当時は参考になる書籍もなかったので、苦労の末にこのような法則を見つけたのです。今ではこのようなことは本屋に行けばすぐに解決してしまうことなのでちょっと拍子抜けしてしまいます。

　それではまた次回。