「直方体の重なり」を Squeak Smalltalk で

OOPL


http://www.sony.co.jp/SonyInfo/Jobs/newgrads/sus/images/question.jpg


おもしろい。やってみよう。


この例題のような仕様の直方体の場合、二つに重なりがあるかは、X-Y 平面、X-Z 平面 Y-Z 平面への投影図（ふたつの矩形からなる）のどれにもちゃんと重なりがあるかどうかで判断できそうです。

Squeak Smalltalk の場合、すでに組み込みの「矩形オブジェクト」（Rectangle のインスタンス。原点座標 extent: 幅@高 で生成可能)があり、それに二つのインスタンスの重なりの有無を真偽値で返す #intersects: というメソッドもあるのでこれらを省力化のために積極的に活用します。

| rect1 rect2 rect3 |
rect1 := 0@0 extent: 10@10.
rect2 := 5@5 extent: 10@10.
rect3 := 15@15 extent: 10@10.

"重なりがある場合"
rect1 intersects: rect2.  "=> true "

"重なりがない場合"
rect1 intersects: rect3.  "=> false "


前後しますが、x@y はやはり組み込みの「座標オブジェクト」（Point のインスタンス）を生成するための式です（リテラルっぽいですがそうではなくごく普通の式で、Number>>#@ というメソッドをコールしています）。

まず、こういうテストが通ることを目指します。

TestCase subclass: #CubeIntersectionTest
   instanceVariableNames: ''
   classVariableNames: ''
   poolDictionaries: ''
   category: 'Sony-Quiz-Tests'

CubeIntersectionTest >> test000
   "二つの直方体に重なりがあるかを真偽値で返すことができる"
   | cube1 cube2 cube3 |
   cube1 := 0@0@0 extent: 10@10@10.
   cube2 := 5@5@5 extent: 10@10@10.
   cube3 := 15@15@15 extent: 10@10@10.

   self assert: (cube1 intersects: cube2) = true.
   self assert: (cube1 intersects: cube3) = false


そのためには x@y@z に三次元座標オブジェクトを返させなければいけません。テストはこんな感じ。

CubeIntersectionTest >> test001
   "x@y@z で三次元座標オブジェクト（a Point3D）を生成できる"
   self assert: (0@0@0) class = Point3D


このテストのコンパイル時に Point3D が見つからないがどうしたいか？とコンパイラーに怒られるので促されるままに定義しておきます。インスタンス変数は Point に倣って x y z でよいでしょう。

Object subclass: #Point3D
   instanceVariableNames: 'x y z'
   classVariableNames: ''
   poolDictionaries: ''
   category: 'Sony-Quiz'


いずれ Point3D class>>#x:y:z: も必要なので同様に Point class>>#x:y: に倣って先に定義しておきます。

Point3D class >> x: x y: y z: z
   ^self basicNew setX: x setY: y setZ: z

Point3D >> setX: newX setY: newY setZ: newZ
   x := newX.
   y := newY.
   z := newZ


さて。Smalltalk では x@y@z という式は、前述の x@y で生成された座標オブジェクト（Point のインスタンス）にあらためて @z というメッセージを送る、と解釈されます。したがって Point3D オブジェクトを生成させるには Point>>#@ を定義すればよいことになります。

Point >> @ z
   ^Point3D x: x y: y z: z


これで #test001 がグリーンに。あと、#test000 は最後まで通らないのでコメントアウトならぬブロックで括って機能しないようにしておくほうがオールグリーンが確認がしやすいと思います。

CubeIntersectionTest >> test000 [
   "二つの直方体に重なりがあるかを真偽値で返すことができる"
   | cube1 cube2 cube3 |
   cube1 := 0@0@0 extent: 10@10@10.
   cube2 := 5@5@5 extent: 10@10@10.
   cube3 := 15@15@15 extent: 10@10@10.

   self assert: (cube1 intersects: cube2) = true.
   self assert: (cube1 intersects: cube3) = false
]


こうしてできあがった Point3D オブジェクトに、extent: w@h@d というメッセージを送ることで直方体オブジェクト（Cube のインスタンス）を生成できるようにします。まずテスト。

CubeIntersectionTest >> test002
   "x@y@z extent: w@h@d で直方体オブジェクト（a Cube）を生成できる"
   self assert: (0@0@0 extent: 10@10@10) class = Cube


例によってコンパイル時に Cube が見当たらないといってコンパイラーが怒ってくるのでこれも促されるまま定義しておきます。インスタンス変数は Rectangle に倣って origin と corner でよいでしょう。

Object subclass: #Cube
   instanceVariableNames: 'origin corner'
   classVariableNames: ''
   poolDictionaries: ''
   category: 'Sony-Quiz'

Cube class >> origin: originPoint3D extent: extentPoint3D 
   ^self basicNew setOrigin: originPoint3D corner: originPoint3D + extentPoint3D

Cube >> setOrigin: newOrigin corner: newCorner
   origin := newOrigin.
   corner := newCorner


Point3D>>#extent: は Point>>#entent: を参考にして書きます。

Point3D >> extent: aPoint3D
   ^Cube origin: self extent: aPoint3D


Point3Dオブジェクト同士の加算なども Point>>#+ に倣って定義。（#adaptToPoint3D:andSend: は YAGNI なのでエラーを出したほうがよいかも。）

Point3D >> + arg 
   arg isPoint3D ifTrue: [^ (x + arg x) @ (y + arg y) @ (z + arg z)].
   ^arg adaptToPoint3D: self andSend: #+

Object >> isPoint3D
   ^false

Point3D >> isPoint3D
   ^true

Point3D >> x
   ^x

Point3D >> y
   ^y

Point3D >> z
   ^z


お膳立ては整ったので最後に本題である Cube>>#intersects: の定義。X-Y、X-Z、Y-Z 平面に投影される矩形情報を得る便利メソッドをそれぞれ #xyRect #xzRect #yzRect とすれば Cube>>#intersects: は次のように書くことができます。

Cube >> intersects: aCube
   ^(self xyRect intersects: aCube xyRect)
      and: [self xzRect intersects: aCube xzRect]
      and: [self yzRect intersects: aCube yzRect]


#xyRect #xzRect #yzRect は実装はこんなので。

Cube >> xyRect
   ^origin x @ origin y extent: corner x @ corner y

Cube >> xzRect
   ^origin x @ origin z extent: corner x @ corner z

Cube >> yzRect
   ^origin y @ origin z extent: corner y @ corner z


最後に #test000 のブロックの囲いを外してグリーンになることを確認できれば、これでおしまい。

CubeIntersectionTest >> test000
   "二つの直方体に重なりがあるかを真偽値で返すことができる"
   | cube1 cube2 cube3 |
   cube1 := 0@0@0 extent: 10@10@10.
   cube2 := 5@5@5 extent: 10@10@10.
   cube3 := 15@15@15 extent: 10@10@10.

   self assert: (cube1 intersects: cube2) = true.
   self assert: (cube1 intersects: cube3) = false


お題の二項目目を鑑みてもう少し網羅的なテストを書き足してもいいですね。

CubeIntersectionTest >> test003
   "完全に内部にあるパターンや面や辺から一部がはみ出ているパターンでの交差"
   | cube |
   cube := 0@0@0 extent: 8@8@8.
   self assert: (cube intersects: (2@2@2 extent: 4@4@4)) = true.
   self assert: (cube intersects: (2@2@6 extent: 4@4@4)) = true.
   self assert: (cube intersects: (2@6@6 extent: 4@4@4)) = true

CubeIntersectionTest >> test004
   "面、辺、角のみで接していても交差とは判定しない"
   | cube |
   cube := 0@0@0 extent: 5@5@5.
   self assert: (cube intersects: (0@0@5 extent: 5@5@5)) = false.
   self assert: (cube intersects: (0@5@5 extent: 5@5@5)) = false.
   self assert: (cube intersects: (5@5@5 extent: 5@5@5)) = false


なお、#assert: で false かどうかをチェックする代わりに #deny: も使えます。同様に #assert: で true かどうかのチェックも本当は必要ありません。念のため。