小ワザ
対応する四辺が平行な矩形同士の交差判定 †
対応する四辺が平行な任意の二つの矩形、矩形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
- 四辺が座標軸と平行の場合。
- 矩形を左上の点の座標と横縦の大きさで表現。
- アルゴリズムを直訳。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
|
if ( (x(r1) + cx(r1) - 1) < x(r2) ) { cnd1 = 1 } else { cnd1 = 0 }
if ( x(r1) > (x(r2) + cx(r2) - 1) ) { cnd2 = 1 } else { cnd2 = 0 }
if ( (y(r1) + cy(r1) - 1) < y(r2) ) { cnd3 = 1 } else { cnd3 = 0 }
if ( y(r1) > (y(r2) + cy(r2) - 1) ) { cnd4 = 1 } else { cnd4 = 0 }
if ( (cnd1 == 0) & (cnd2 == 0) & (cnd3 == 0) & (cnd4 == 0) ) { result = 1 } else { result = 0 }
|
- 実装例2
- 四辺が座標軸と平行の場合。
- 矩形を左上の点の座標と横縦の大きさで表現。
- 実装例1から変数を省略。
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
|
-
|
-
|
|
-
|
-
|
|
-
|
-
|
|
-
|
-
|
|
!
!
!
!
|
if ( (x(r1) + cx(r1) - 1) < x(r2) ) {
result = 0
} else {
if ( x(r1) > (x(r2) + cx(r2) - 1) ) {
result = 0
} else {
if ( (y(r1) + cy(r1) - 1) < y(r2) ) {
result = 0
} else {
if ( y(r1) > (y(r2) + cy(r2) - 1) ) {
result = 0
} else {
result = 1
}
}
}
}
|
- 実装例3
- 四辺が座標軸と平行の場合。
- 矩形を左上の点の座標と横縦の大きさで表現。
- 実装例2から条件式を状態に該当しない条件に変更。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
-
|
|
-
|
|
-
|
|
-
|
|
!
!
!
!
|
result = 0
if ( (x(r1) + cx(r1) - 1) >= x(r2) ) {
if ( x(r1) <= (x(r2) + cx(r2) - 1) ) {
if ( (y(r1) + cy(r1) - 1) >= y(r2) ) {
if ( y(r1) <= (y(r2) + cy(r2) - 1) ) {
result = 1
}
}
}
}
|
実装例を簡単に実行してみたい場合は、次のスクリプトを利用してください。
使い方は、実装例のスクリプトをここに実装例のスクリプトを挿入する。の部分に挿入して実行するだけです。
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?
- アルゴリズムを直訳した実装と最適化を進めた実装という概念を知ってもらうためにこういう構成にしています。 -- naznyark?
- 回転を加えた矩形(長方形)を考えた場合、この説明では少し難がありますね。この説明の前提として「boxfで描画される矩形」(もっといい表現があればいいのですが…思いつかない)などと書いたほうがよいかもしれません。上手い表現が思いつかないので直接修正はせずコメントにさせていただきました。(^ ^; -- GENKI?
- ちなみに回転を加えた四辺が平行な矩形同士の場合は、まず全体を回転させてから評価してやればこの評価方法のままでいけると思います。 -- GENKI?
- 「4辺が平行な矩形」は「矩形」ではないと思うのですが。 --
- 目の前の問題を一方向から捉えるのではなく、別の視点からアプローチするという点では、わかりやすく説明されてると思います。 --