質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.51%

  • C#

    9041questions

    C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。

  • C++

    4431questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • Visual Studio

    2359questions

    Microsoft Visual StudioはMicrosoftによる統合開発環境(IDE)です。多種多様なプログラミング言語に対応しています。

  • Visual C++

    145questions

    Microsoft Visual C++はWindowsのCとC++の統合開発環境(IDE)であり、コンパイラやデバッガを含んでいます。

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

解決済

回答 4

投稿

  • 評価
  • クリップ 0
  • VIEW 1,577

ohana1515

score 5

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 4

checkベストアンサー

+2

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/07/19 11:18

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

    キャンセル

0

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

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

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

同じタグがついた質問を見る

  • C#

    9041questions

    C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。

  • C++

    4431questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • Visual Studio

    2359questions

    Microsoft Visual StudioはMicrosoftによる統合開発環境(IDE)です。多種多様なプログラミング言語に対応しています。

  • Visual C++

    145questions

    Microsoft Visual C++はWindowsのCとC++の統合開発環境(IDE)であり、コンパイラやデバッガを含んでいます。