2010/11/09(火) [n年前の日記]
#2 [flash] 点と多角形のアタリ判定でハマリ中
方法としては、点から伸ばしたレイと、多角形を構成している複数の線分が交差する回数を数えて、交差回数が奇数だったら内に、偶数だったら外に点がある、と判断するソレなのだけど。
レイを伸ばす方向を、斜め方向、(画面横幅 x 2, 画面縦幅 x 2) ぐらいにしていた時には正常に判定できているように見えたものの。ふとなんとなく、水平方向にレイを伸ばしてみたところ、多角形を構成する線分の頂点上、つまりは多角形を構成する線分の始点もしくは終点上にレイがある場合は判定に失敗することに気付いた。どうも線分の交差を判定する際に、頂点上で交差する場合は交差しないと判定する作りだったらしい。
であればと、線分の始点もしくは終点上にレイがある場合も交差してると判断するように変更してみたところ、これでも失敗してしまう。考えてみれば、多角形データは頂点を羅列してあるデータだから、例えば線分1の終点と線分2の始点は重なった状態にあるわけで。であるから頂点上にレイが来た時、1本分だけ交差してると判定してほしいところで2本分交差してるとカウントされて、交差回数が1回増えてしまい奇数偶数による判断が間違ってしまうという。
解決策としては、どうせレイを水平方向に伸ばしているのだから、点のy座標(=レイのy座標)と、線分の始点終点のy座標を比較して、yの値が大きいほうは無視してしまう、というやり方がありそう。と思いながら検索していたら、やはりそういう方法で解決しているサンプルを見かけた。そのサンプルを参考にしてどうにか。
他にも、交差していると判断する際に、そこが重なっている頂点上なら特別扱いをしてカウントする、という手もありそうな。あるいは、あらかじめ線分の始点終点に若干の変更を加えておく、という手もあるのかもしれない。そのあたりはちと上手い誤魔化し方(?)が思いつかなかった。今後の課題。
レイを伸ばす方向を、斜め方向、(画面横幅 x 2, 画面縦幅 x 2) ぐらいにしていた時には正常に判定できているように見えたものの。ふとなんとなく、水平方向にレイを伸ばしてみたところ、多角形を構成する線分の頂点上、つまりは多角形を構成する線分の始点もしくは終点上にレイがある場合は判定に失敗することに気付いた。どうも線分の交差を判定する際に、頂点上で交差する場合は交差しないと判定する作りだったらしい。
であればと、線分の始点もしくは終点上にレイがある場合も交差してると判断するように変更してみたところ、これでも失敗してしまう。考えてみれば、多角形データは頂点を羅列してあるデータだから、例えば線分1の終点と線分2の始点は重なった状態にあるわけで。であるから頂点上にレイが来た時、1本分だけ交差してると判定してほしいところで2本分交差してるとカウントされて、交差回数が1回増えてしまい奇数偶数による判断が間違ってしまうという。
解決策としては、どうせレイを水平方向に伸ばしているのだから、点のy座標(=レイのy座標)と、線分の始点終点のy座標を比較して、yの値が大きいほうは無視してしまう、というやり方がありそう。と思いながら検索していたら、やはりそういう方法で解決しているサンプルを見かけた。そのサンプルを参考にしてどうにか。
他にも、交差していると判断する際に、そこが重なっている頂点上なら特別扱いをしてカウントする、という手もありそうな。あるいは、あらかじめ線分の始点終点に若干の変更を加えておく、という手もあるのかもしれない。そのあたりはちと上手い誤魔化し方(?)が思いつかなかった。今後の課題。
◎ 余談。 :
交差回数が奇数か偶数かで内外判定を行う、というやり方は、自分が学生の頃に Oh! X あたりで知ったような記憶が。そこでも、多角形の頂点の扱いをどうするか、とか、水平方向にのみ伸びている線分はどう扱うか等々問題点も紹介されていて。要するに、結構古くから知られている方法のはず。
で。オリジナルは誰がどの時期に考えたのか、気になるわけで。外国の方が考案したのか、日本人が考案したのか。誰なんだろう。どこかに情報はないものか。
各方法に、考案者名がついた状態で普及すれば良かったのに、と思ったりもする。 _Bresenham's line algorithm みたいな感じで。そうすればこのあたりもスッキリするのにな…。特許には愛称・通称の類も設定するよう強制したほうが良いのでは。みたいな。いや、実はそういう記入欄・項目があるのかもしれないけど。
どうしてそのあたり急に気になったかというと。検索してたら比較的近年になって似たような感じのソレが多数特許申請されているようで。特にキヤノンあたりからは、何人もの人がいくつも出してるみたいなんだけど。キヤノンの中で、何かそういうコンテストでもあったのだろうか？ まさかとは思うが、毎月何本特許申請しろとか会社からノルマをかけられて、苦し紛れにパクって出してしまった新人が居るとかそういう…いや、まさかね…。
で。オリジナルは誰がどの時期に考えたのか、気になるわけで。外国の方が考案したのか、日本人が考案したのか。誰なんだろう。どこかに情報はないものか。
各方法に、考案者名がついた状態で普及すれば良かったのに、と思ったりもする。 _Bresenham's line algorithm みたいな感じで。そうすればこのあたりもスッキリするのにな…。特許には愛称・通称の類も設定するよう強制したほうが良いのでは。みたいな。いや、実はそういう記入欄・項目があるのかもしれないけど。
どうしてそのあたり急に気になったかというと。検索してたら比較的近年になって似たような感じのソレが多数特許申請されているようで。特にキヤノンあたりからは、何人もの人がいくつも出してるみたいなんだけど。キヤノンの中で、何かそういうコンテストでもあったのだろうか？ まさかとは思うが、毎月何本特許申請しろとか会社からノルマをかけられて、苦し紛れにパクって出してしまった新人が居るとかそういう…いや、まさかね…。
[ ツッコむ ]
以上です。