hinekure.net が http://hspdev-wiki.net/ から自動クローリングした結果を表示しています。画像やリソースなどのリンクが切れています。予めご了承ください。
小ワザ/対応する四辺が平行な矩形同士の交差判定 - HSP開発wiki
トップ    編集凍結 差分バックアップ添付複製名前変更リロード   新規一覧単語検索最終更新   最終更新のRSS

小ワザ

対応する四辺が平行な矩形同士の交差判定

対応する四辺が平行な任意の二つの矩形、矩形1と矩形2が交差して(重なって)いるかどうかを判定する方法の一つについての説明です。

1111      2222
1  1      2  2
1  1      2  2
1111      2222

アルゴリズム

まず二つの矩形が交差していることを考えるのではなく、交差していないことを考えます。
前提(対応する四辺が平行な二つの矩形)から以下の四つの状態のどれか一つにでも該当すれば二つの矩形が交差していないのは明白です。

  • (状態1) 矩形1の右端が矩形2の左端より左にある状態
       | |
    1111 2222
    1  1 2  2
    1  1 2  2
    1111 2222
       | |
  • (状態2) 矩形1の左端が矩形2の右端より右にある状態
       | |
    2222 1111
    2  2 1  1
    2  2 1  1
    2222 1111
       | |
  • (状態3) 矩形1の下端が矩形2の上端より上にある状態
     1111
     1  1
     1  1
    −1111−
    
    −2222−
     2  2
     2  2
     2222
  • (状態4) 矩形1の上端が矩形2の下端より下にある状態
     2222
     2  2
     2  2
    −2222−
    
    −1111−
     1  1
     1  1
     1111

また以上の四つの状態(の組み合わせ)以外に二つの矩形が交差していない状態はありません。
よって、

二つの矩形が交差していないための条件
二つの矩形の状態が上記の四つの状態のどれかに該当する。

であり、これは逆に

二つの矩形が交差するための条件
二つの矩形が交差していないための条件を満たさない。
つまり、二つの矩形の状態が上記の四つの状態のどれにも該当しない。

ということになります。
このことから二つの矩形の状態を上記四つの状態それぞれについて該当するかどうかを調べれば二つの矩形が交差しているかどうかを判定することができます。

実装例1
四辺が座標軸と平行の場合。
矩形を左上の点の座標と横縦の大きさで表現。
アルゴリズムを直訳。
Everything is expanded.Everything is shortened.
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
//  x : 矩形の左上の点の水平方向座標。
//  y : 矩形の左上の点の垂直方向座標。
//  cx : 矩形の水平方向の大きさ。
//  cy : 矩形の垂直方向の大きさ。
//  cndx : 各状態の該当フラグ。状態に該当していれば 1、該当していなければ 0。
//  result : 結果。交差していれば 1、交差していなければ 0。
 
    //  状態1に該当するかどうかを調べる。
    if ( (x(r1) + cx(r1) - 1) < x(r2) ) { cnd1 = 1 } else { cnd1 = 0 }
    //  状態2に該当するかどうかを調べる。
    if ( x(r1) > (x(r2) + cx(r2) - 1) ) { cnd2 = 1 } else { cnd2 = 0 }
    //  状態3に該当するかどうかを調べる。
    if ( (y(r1) + cy(r1) - 1) < y(r2) ) { cnd3 = 1 } else { cnd3 = 0 }
    //  状態4に該当するかどうかを調べる。
    if ( y(r1) > (y(r2) + cy(r2) - 1) ) { cnd4 = 1 } else { cnd4 = 0 }
    //  状態1から4のどれにも該当していなければ交差している。
    if ( (cnd1 == 0) & (cnd2 == 0) & (cnd3 == 0) & (cnd4 == 0) ) { result = 1 } else { result = 0 }
実装例2
四辺が座標軸と平行の場合。
矩形を左上の点の座標と横縦の大きさで表現。
実装例1から変数を省略。
Everything is expanded.Everything is shortened.
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 
 
 
 
 
 
 
-
|
-
|
|
-
|
-
|
|
-
|
-
|
|
-
|
-
|
|
!
!
!
!
//  x : 矩形の左上の点の水平方向座標。
//  y : 矩形の左上の点の垂直方向座標。
//  cx : 矩形の水平方向の大きさ。
//  cy : 矩形の垂直方向の大きさ。
//  result : 結果。交差していれば 1、交差していなければ 0。
 
    //  状態1に該当するかどうかを調べる。
    if ( (x(r1) + cx(r1) - 1) < x(r2) ) {
        result = 0
    } else {
        //  状態1に該当しない場合。
        //  状態2に該当するかどうかを調べる。
        if ( x(r1) > (x(r2) + cx(r2) - 1) ) {
            result = 0
        } else {
            //  状態1と状態2に該当しない場合。
            //  状態3に該当するかどうかを調べる。
            if ( (y(r1) + cy(r1) - 1) < y(r2) ) {
                result = 0
            } else {
                //  状態1と状態2と状態3に該当しない場合。
                //  状態4に該当するかどうかを調べる。
                if ( y(r1) > (y(r2) + cy(r2) - 1) ) {
                    result = 0
                } else {
                    //  状態1と状態2と状態3と状態4に該当しない場合。
                    result = 1
                }
            }
        }
    }
実装例3
四辺が座標軸と平行の場合。
矩形を左上の点の座標と横縦の大きさで表現。
実装例2から条件式を状態に該当しない条件に変更。
Everything is expanded.Everything is shortened.
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 
 
 
 
 
 
 
 
-
|
|
-
|
|
-
|
|
-
|
|
!
!
!
!
//  x : 矩形の左上の点の水平方向座標。
//  y : 矩形の左上の点の垂直方向座標。
//  cx : 矩形の水平方向の大きさ。
//  cy : 矩形の垂直方向の大きさ。
//  result : 結果。交差していれば 1、交差していなければ 0。
 
    result = 0
    //  状態1に該当しないかどうかを調べる。
    if ( (x(r1) + cx(r1) - 1) >= x(r2) ) {
        //  状態1に該当しない場合。
        //  状態2に該当しないかどうかを調べる。
        if ( x(r1) <= (x(r2) + cx(r2) - 1) ) {
            //  状態1と状態2に該当しない場合。
            //  状態3に該当しないかどうかを調べる。
            if ( (y(r1) + cy(r1) - 1) >= y(r2) ) {
                //  状態1と状態2と状態3に該当しない場合。
                //  状態4に該当しないかどうかを調べる。
                if ( y(r1) <= (y(r2) + cy(r2) - 1) ) {
                    //  状態1と状態2と状態3と状態4に該当しない場合。
                    result = 1
                }
            }
        }
    }

実装例のテスト

実装例を簡単に実行してみたい場合は、次のスクリプトを利用してください。
使い方は、実装例のスクリプトをここに実装例のスクリプトを挿入する。の部分に挿入して実行するだけです。

Everything is expanded.Everything is shortened.
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
;
;	実装例動作テスト用スクリプト
;
 
r1 = 0 : r2 = 1
cx = 100,100
cy = 100,100
x = 0, (ginfo_winx-cx)/2
y = 0, (ginfo_winy-cy)/2
 
*main
    redraw 1 : await 16 : redraw 0 : color 255, 255, 255 : boxf : color : pos 0,0
 
    x(r1) = mousex
    y(r1) = mousey
    color 255,0,0
    boxf x(r1),y(r1), x(r1)+cx(r1),y(r1)+cy(r1)
    color 0,0,255
    boxf x(r2),y(r2), x(r2)+cx(r2),y(r2)+cy(r2)
 
    //
    //	ここに実装例のスクリプトを挿入する。
    //
 
    if result!0 : color : pos 0,0 : mes "Hit!"
    goto *main

コメント

  • 実装例1ですが、最初にcnd=0としておき、条件式に当てはまったらcnd=1とすれば、複数の変数を使わなくても処理できるのでは? -- xeno? 2009-02-08 (日) 11:33:22
  • アルゴリズムを直訳した実装と最適化を進めた実装という概念を知ってもらうためにこういう構成にしています。 -- naznyark? 2009-02-08 (日) 17:53:01
  • 回転を加えた矩形(長方形)を考えた場合、この説明では少し難がありますね。この説明の前提として「boxfで描画される矩形」(もっといい表現があればいいのですが…思いつかない)などと書いたほうがよいかもしれません。上手い表現が思いつかないので直接修正はせずコメントにさせていただきました。(^ ^; -- GENKI? 2009-02-09 (月) 21:26:02
  • ちなみに回転を加えた四辺が平行な矩形同士の場合は、まず全体を回転させてから評価してやればこの評価方法のままでいけると思います。 -- GENKI? 2009-02-09 (月) 21:26:41
  • 「4辺が平行な矩形」は「矩形」ではないと思うのですが。 -- 2009-02-10 (火) 14:38:01
  • 目の前の問題を一方向から捉えるのではなく、別の視点からアプローチするという点では、わかりやすく説明されてると思います。 -- 2009-02-10 (火) 14:40:38

URL B I U SIZE Black Maroon Green Olive Navy Purple Teal Gray Silver Red Lime Yellow Blue Fuchsia Aqua White

トップ    編集凍結 差分バックアップ添付複製名前変更リロード   新規一覧単語検索最終更新   最終更新のRSS
Last-modified: 2009-02-10 (火) 14:40:38 (1762d)