A pray to the everlasting†
Go with God...
プロフィール

Amu

Author:Amu
(゚Д゚)<久々にロゴを変えました!!
(゚Д゚)<デザインセンス0!
(゚Д゚)<むずかしいです!



Clocks



ブログ検索



カレンダー

07 | 2017/08 | 09
- - 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 - -



最近の記事



最近のトラックバック



月別アーカイブ



ブロとも申請フォーム

この人とブロともになる



リンク

このブログをリンクに追加する



RSSフィード



全ての記事を表示する

全ての記事を表示する



スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。


raw intelligence
二つの長方形が交わる条件

トラックバックというよりリンクをば。
マイクロソフトの試験官をされていた方のブログから。

[問題]
二次元座標上に、それぞれの辺がX軸・Y軸と平行に置かれた長方形Aと長方形Bがあるとする。その時、長方形Aと長方形Bが一部でも重なるかどうかを判断する条件式を書け。フォーマットは、CやJavaなどのコンピューター言語でも良し、単なる数式でも良い。制限時間は30分。ただし、考えていることを声に出し、ホワイト・ボードを使って自分の考えのプロセスを説明しながら解くこと。
実際に動くレベルのものをプログラムで書くには30分では少し
足りないかもだから、あえて数学的にときました。内容自体は
東大数学に似ている、所要時間は20分。

前提:線の太さは考えない

3分くらいはどの方法で解こうか考えてました。まず交わる条件の
余事象を考えて、交わらない条件を考えます。
長方形A,Bが交わらない条件は、以下の二つ。

"長方形Aの示す領域と長方形Bを示す領域が独立である"・・・①
or
"長方形Aの示す領域に長方形Bが内包される"・・・②

長方形の領域は offset = (x,y), x_len = a, y_len = b とすると
0≦α≦1, 0≦β≦1 ・・・③なる実数α、βを用いて、
ベクトル形式で、(x+αa, y+βb) と表現される。

長方形Aのものを添え字1で、Bを2であらわすと
長方形Aの領域 = (x1+α1*a1, y1+β1*b1)
長方形Bの領域 = (x2+α2*a2, y2+β2*b2)
①を考えると、すべての上記実数群に対して、
x1+α1*a1 = x2+α2*a2 かつ y1+β1*b1 = y2+β2*b2 を満たしては
いけない。長方形A,Bは同じ条件の下なので、α1、β1について解く。
a,bの非負性から、
α1 = (x2-x1+α2*a2)/a1, β1 = (y2-y1+β2*b2)/b1
③より
(x2-x1-a2)/a1 ≦ α1 ≦ (x2-x1+a2)/a1
(y2-y1-b2)/b1 ≦ β1 ≦ (y2-y1+b2)/b1
(上二式を④とする)
これを満たすα1、β1が存在すると交わるので、交わらない条件は
すべてのα1、β1に対して④を満たさなければよい。
つまり、
(x2-x1-a2)/a1 > 1 or (x2-x1+a2)/a1 < 0
(y2-y1-b2)/b1 > 1 or (y2-y1+b2)/b1 < 0

これを解くと
a1 + a2 < x2 - x1 , x2 - x1 < -a2
b1 + b2 < y2 - y1 , y2 - y1 < -b2

②の条件はすべてのα2、β2を考えても長方形Aに内包される条件を
考える。
以下省略、暇があれば加筆します。

ちなみに、余事象を考えなくても、交わる状態は角を1つ含むか、
2つ含むかの2通りになるので、結果的には同じかな。

なんていうか、簡単だけど、いろんな解き方が考えられて楽しいね。
ちなみに、プログラムで書き始めなかったのにはもう一つ理由が、、

プログラムって言うのは、個人的には人間の手の届かないレベルに
いたったときに使うと思ってて、人間の思考でブレークダウンした
もの(ここでいうと、ワシが求めた最後の条件)を処理させる時に
使ってます。

これもcase by case で、後の人に読んでもらう場合には、多少
遅くても可読性を優先するし、ワシのテリトリーであるマイコン
などのシビアな場合には処理速度を優先します。

余事象云々とか言ってましたけど、リンク先見たらちゃんと
書いてありましたね。とりあえず、
"一部の学生は、この段階で、最初から交わらない場合を考えていれば、XY座標を分割して考える必要が無かったことに気がつくのだが、そこまで30分でたどり着けるのはごく一部の学生だけだ。"
には至ったので満足。

--プログラムでやるとするならば、長方形Aの原点(もしくは、ある角)
--から、線の上のみを探索する虫を乗っけて、交点に差し掛かった
--ときの移動可能な方向の数をカウントさせようかな。
--自分の来た道をカウントしないならば、移動可能な方向数が1以下で
--あるとき長方形は交わらない、と。
--移動可能な方向数が2以上なら return true, 1以下のまま3回まがれ
--たら return false と。

スポンサーサイト

この記事に対するコメント

この記事に対するコメントの投稿














管理者にだけ表示を許可する


この記事に対するトラックバック
この記事にトラックバックする(FC2ブログユーザー)
トラックバックURL
→http://ayutama.blog22.fc2.com/tb.php/49-1486761c

raw intelligence

二つの長方形が交わる条件トラックバックというよりリンクをば。マイクロソフトの試験官をされていた方のブログから。[問題]二次元座標上に、それぞれの辺がX軸・Y軸と平行 laugh out loudly【2006/01/18 01:45】



上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。