Programming Tips 1024
プログラムしているときに思いついた小ネタを書きます。このコーナーへの投稿もお待ちしてます＾＾
特にことわりが無い限り、C++／VC++／Win32です。情報提供者orネタ提供者がいる場合は、表題の右横に《 》で書いています。
'04/03/05
Tips 71. 点と矩形との領域判定の高速化
2次元の点と矩形との判定で、以下のようなコードをよく目にします。
| Rect r; int x,y; if (r.left<=x && x<r.right && r.top<=y && y<r.bottom){ // (x,y)は矩形rの内部にある } |
まあ、複数の矩形があって複数の点との領域判定を行ないたいならば、2分サーチなり何なりすればいいのですが、このへんは3次元での技法が参考になるでしょう。（→BSP,8分木)
ここでは2次元にしぼって話を進めます。上のコードは3回の論理積がありますが、これは速度面で言えば、以下のようなコードになるのでお世辞にも早いとは言えません。
| if (!(r.left<=x)) goto next; if (!(x<r.right)) goto next; if (!(r.top<=y)) goto next; if (!(y<r.bottom)) goto next; { // (x,y)は矩形rの内部にある } next:; |
分岐予測の外れた時のペナルティを考えると、これはかなり悪質なコードだと言えます。
そのへんを理解している人ならば、論理積ではなくビット積で書くでしょう。
| Rect r; int x,y; if (r.left<=x & x<r.right & r.top<=y & y<r.bottom){ // (x,y)は矩形rの内部にある } |
当然、こちらのほうが断然速いコードです。条件分岐が一度しか行なわれないからです。しかもその条件分岐はシューティングで自機と弾との交差判定のような場合、ほとんどが交差しないので分岐予測は当たり続けます。前者と後者との差は比較にならないことは言うまでもないでしょう。
しかし、後者のコードは甘い。さっかりんのように甘いと言わざるを得ません。（何のこっちゃ）
アセンブラをある程度やっている人ならわかるでしょうけど、xがaからbの間にあるかどうかは、cmp一回で判定できます。xからa引いてからb-aとコンペアすればいいのです。
C言語で言えば、
| Rect r; int x,y; if ( ((unsigned int)(x-r.left)<r.right-r.left) & ((unsigned int)(y-r.top )<r.bottom-r.top) ){ // (x,y)は矩形rの内部にある } |
てなコードになります。コンパイラが十分賢いなら最適化で上のようなコードにしてくれるかも知れませんけど、この手の最適化はあまり期待できないでしょう。if (x in [a,b) )のような判定を行なう構文があって上のように最適化してくれるといいんでしょうけど．．。