2005/06/17

長方形が重なるかどうかの問題(参照)。数式は陰気臭いからコードにしろという圧力があったのでがんばった。結局、3時間以上かかった。ほとんどの時間を長方形の表現に悩んだ気がする。で、まあ自然数の直交グリッドに沿ったものだけでいいじゃんということにして、あきらめました。有理数の直交グリッド(つまりコンピュータディスプレイ)までなら同じノリで解決できると信じる。だって定積分ってそういうノリだし(ようは言い訳)。でも、一般のHausdorff空間で解決しろといわれているわけでもないし、そもそも長方形が定義できない空間じゃ意味ないしね。

(use srfi-1)

;; 長方形は対角線の端点(にあるマス)で定義: ((x0 y0) (x1 y1))
;; ただし、 右上がりの対角線で定義 i.e. x0 <= x1, y0 <= y1
(define-syntax rect?
(syntax-rules ()
((_ rect ...)
(and (and (<= (caar rect) (caadr rect)) (<= (cadar rect) (cadadr rect))) ...))))

(define (expand-x from-ls to-ls)
(let ((xfrom (car from-ls)) (xto (car to-ls)) (yfrom (cadr from-ls)))
(map (lambda (x) (cons x yfrom))
(let f ((xcurrent xfrom))
(let ((xnext (+ xcurrent 1)))
(if (> xnext (+ xto 1))
'()
(cons xcurrent (f xnext))))))))

(define (expand-rect-diag from-ls to-ls)
(let ((x-ls (expand-x from-ls to-ls)) (yfrom (cadr from-ls)) (yto (cadr to-ls)))
(let* ((ycurrent yfrom) (ynext (+ ycurrent 1)))
(if (> ynext (+ yto 1))
'()
(append x-ls
(expand-rect-diag (list (car from-ls) ynext) to-ls))))))

(define (expand-rect rect-with-diag)
(let ((from-ls (car rect-with-diag)) (to-ls (cadr rect-with-diag)))
(expand-rect-diag from-ls to-ls)))

;; 長方形からなる領域の面積(=マスの数)
(define-syntax sumup-rect
(syntax-rules ()
((_ e1) (length (expand-rect e1)))
((_ e1 e2 ...)
(length (lset-union equal? (expand-rect e1) (expand-rect e2) ...)))))

;; 2つの長方形が交わってるかどうか
(define (intersect? rect1 rect2)
(if (rect? rect1 rect2)
(< (sumup-rect rect1 rect2) (+ (sumup-rect rect1) (sumup-rect rect2)))))

できたかな?

(define rect1 (list '(0 0) '(3 2)))
(define rect2 (list '(3 3) '(4 4)))
(define rect3 (list '(1 1) '(4 4)))

gosh-rl> (intersect? rect1 rect2)
#f
gosh-rl> (intersect? rect1 rect3)
#t

そうそう。ようやく Gauche-readline の存在を知りました。画期的です。横田さん、ありがとうございます。

3 comments :

hisashim said...

面白いね。この方法で小数も扱えるといいな。
あとrectangleは「矩形」でお願いします。日本語の長方形は正方形を除くという含みがあるから。

k16 said...

ここでは、定積分の定義における面積要素→0の粒度を自然数に制限したということです。積分の対象となる領域がデカルト座標の両軸と各辺が並行な矩形の内部に限定されているのでこれでOKとしました。hisashimさんのコメントの意味で小数まで扱うには、グリッドの粒度を1/10とか1/100000とかにして定義すればいいだけです。あとはメモリの問題。

たしかに日本語の「長方形」って用語は、そんな扱いですね。「長」の語感がそうさせるんでしょう。その意味では、コメントで使われている「小数」という語にも、無理数を含まないというようなニュアンスがありますね。

hisashim said...

> ... グリッドの粒度を1/10とか1/100000とかにして定義すればいいだけです。あとはメモリの問題。
いやそれは分かってるんだけど、エレガントなままで同時に *実用性が高い* アルゴリズムにならない? 実行時の話は興味ないだろうけど、桁が増えるといかにも効率が落ちそう。毎秒60フレーム出ないよ!(CG脳)