図形の中に長方形を敷き詰めたい

Question

四角形の図形の中に長方形を並べるだけであれば，辺の長さから出すことができるのですが，四角形に限らず円や多角形などの中に並べるとなるとどうしていいのかわからなくなりました．
図形から少しでもはみ出した長方形は，線分交差判定により判定し，完全に図形の中に入っている長方形だけの数を求めたいと思っています．多角形であれば，四角形と線分の交差判定でできるかなと考えております．
いい方法や，参考になる文献，ホームページなどがあれば教えていただきたいです．
アドバイスをお願いしたいです．
言葉足らずかもしれませんがよろしくお願いします．

Answer 1

数学の専門家ではないので思いつきですが、

長方形を敷き詰めた大きな紙を想像すると、線分と交点の集まりに見做せます(方眼紙のような)
その上に図形を置いて、方眼紙の各交点一つ一つについて図形の内側か外側かの判定を行い
内側の点だけを残して各点を線で繋げば、内側に収まった長方形だけを残すことができると思います。
内側か外側かに関しては、ある点から一方に無限に伸ばした線が図形を構成する線と何回接するかを判定すればできそうです。参考

交点を求めるので、図形は数式で表現できる必要があります(不定形の多角形や直線と曲線で構成された図形でも、「図形を構成する線分一つ一つが数式で表現可能」であればそれらすべてと接触判定をすればいいので、大丈夫だと思います。)
図形の直径がわかっていれば、最初の長方形を敷き詰める範囲を限定できますので処理数も節約できると思います。

Comments

[hirohiro]

この方法では「もっとも多くの長方形を敷き詰める」や「少なくとも一つの長方形は図形と接触している」などは考慮していませんので、長方形の塊が内側に浮いたような結果になったり、(図形の直径から全体の大きさを作成するのでない場合などは)実行するたびに方眼紙が図形の中でずれていたりする可能性はあります。

Answer 2

凸図形であれば
長方形メッシュの各点が「図形」内部に含まれるかを判定すれば簡単です。

問題はその判定方法ですが、
一番安直なのが、
中に長方形を詰める「図形」の表現を判定それ自体にしてしまいます。

例えば単位円なら、
UnitCircle(x,y) = (x^2 + y^2 <= 1)

(図形からこの判定をプログラム的に生成するのが面倒なので、
そこは人力計算して与えてしまおうということです。)

Answer 3

最密充填のまとめ
斜めにしたらもっとはいるんじゃないのとか考えてしまうんですよね。
まあ、決めた並べ方（横向き限定、左下からならべていく）のように限定すれば
答えはでるのかとは思いますが。

厳密でなくてもいいのであれば、コンピューターグラフィックス上に配置してピクセルの衝突でチェックするような方法でもいいんじゃないですか。

Answer 4

任意の図形に任意の図形を敷き詰めるアルゴリズムなんてあるんですかねえ。
その図形一つ一つについてそれぞれ違うアルゴリズムが必要だと思いますが。