問題タブ [rectangles]

私の現在の計画は、NSView をサブクラス化して四角形を描画することですが、それは私がやろうとしていることに対して非常に非効率的な方法のように思えます。より良い方法はありますか？ありがとう。

N 次元の整数点のセットが与えられた場合、N 次元の直方体 (2 次元の場合は四角形) の最小のセットを見つけるにはどうすればよいですか? 1 つまたは複数の直方体/長方形。整数点とは、整数座標を持つ点を意味します。

たとえば、点 (1,0)、(2, 0)、および (3,1)、(4,1) が与えられた場合、長方形の最小のセットは (1,0-2,0),(3,1-4, 1)、下の図を参照してください。

明らかに、ブルート フォース検索を行うこともできますが、それでも複雑性が高い場合でも、より効率的なアルゴリズムを探しています。

私はこれがより高校の数学であることを知っています（私がそこにいたときから長い時間が経ちました）が、私はこれをプログラムで解決しようとしているので、stackoverflowの集合的な知識に手を差し伸べています

このレイアウトを考えると：

中点は私の基準点であり、配列には他のすべての点のベクトル点があります (P)

この状態に到達するには、水色の領域を 4 つの象限に分割し、ラメ バブル ソートを実行して各象限の最大値 (y) または最小値 (x) を見つけます。

外側の境界線が完全に赤く、空白がない象限のみを見つける必要があります。たとえば、左下と右上には、水色の長方形に当たる空白がありません。

私の用語はすべてここにあると確信しており、特定のコードを探しているわけではありませんが、誰かがこの問題のより最適化されたソリューションまたは私がすでに持っているものの次のステップを教えてくれれば.

ありがとうございました

回転した長方形（2D）の頂点を計算しようとしています。

長方形が回転していなければ、それは十分に簡単です、私はその部分を理解しました。

長方形が回転している場合、頂点を計算する2つの方法を考えました。

1. 頂点をローカル/オブジェクト/モデル空間（以下で理解したもの）からワールド空間に変換する方法を理解してください。正直なところわかりませんが、それが最善の方法であるとすれば、それを理解できれば、そこから多くのことを学ぶことができると思います。

2. 三角関数を使用して、長方形の端点がワールド空間内の長方形の位置に対して相対的な位置を何らかの方法で把握します。これは私が今までやろうとしてきた方法でした、私はただその方法を理解していませんでした。

これまでの頂点を計算する関数です。助けてくれてありがとう

画面に最適に表示したい、同じ比率でサイズの長方形のオブジェクトが動的に多数あります。オブジェクトのサイズを変更できますが、比率を維持する必要があります。

私は画面のサイズが何であるかを知っています。

画面を分割するために必要な行と列の最適な数と、オブジェクトをスケーリングするために必要なサイズを計算するにはどうすればよいですか？

ありがとう、

ジェイミー。

編集：

誰かが興味を持った場合に問題を解決するために使用した単純なコード（Fredrikに感謝）：

元の質問：

2つの長方形が重なっているかどうか、および重なっている面積を計算しているかどうかを確認するための簡単で汚い方法を知りたいです。好奇心のために、1）両方の長方形のすべての線が垂直または水平である場合、または2）任意の2つの長方形の一般的な場合に興味がありますが、本当に必要な答えはケース1だけです。

私は次のように考えています：

A.Intersects（）の場合、分離軸テストを使用することを考えていましたが、長方形に水平線と垂直線しかない場合、さらに簡単な（より高速な）チェック方法はありますか？

そして、それらが交差する面積を計算するために、長方形が水平線と垂直線のみである場合、それを行う簡単な方法はありますか？

最後に、これは質問とは関係ありませんが、コンピュータグラフィックスの数学を復習できる良い本/ウェブページについて誰かがアドバイスをいただければ幸いです。私はしばらく大学を卒業していて、すべてを忘れているような気がします:)！他の誰かがその問題を抱えていますか？

（注：この質問はこれとは異なり、より複雑に見え、質問に直接答えることはできません。）

若年成人向けの衝突判定ゲームのチュートリアルをデザインしているので、わかりやすくするためにできるだけシンプルにしたいと思います。

要件は非常に単純です。世界は2Dであり、（任意のサイズの）長方形のみが含まれています。BSPや四分木でさえ、やり過ぎのように見えますが（ここでも、単純さに重点が置かれています）、n（n-1）/2の可能なすべての衝突をブルートフォースするよりも効率的なものが必要です。

2D、長方形のみ、およびシンプル。

誰かが私が調べることができるアルゴリズムを指すことができますか？四分木アルゴリズムは私が探しているものですか？

編集：また、長方形は決して回転しません（私はそれを単純に保ちます）。そして、私が取り組んでいるスケールのアイデアを与えるために、Pygameを使用してPythonで実装された典型的なユーザーのラップトップ/デスクトップ（5歳未満）で実行されている数百の長方形のオーダーがあります。

N個の正の数のセットと、次元XとYの長方形があり、次のようにN個の小さな長方形に分割する必要があります。

• それぞれの小さい長方形の表面積は、与えられたセットの対応する数に比例します
• 大きな長方形のすべてのスペースが占有され、小さな長方形の間に残りのスペースはありません
• それぞれの小さな長方形は、可能な限り正方形に近い形にする必要があります
• 実行時間は適度に短くする必要があります

これについての指示が必要です。Webで説明されているそのようなアルゴリズムを知っていますか？何かアイデアはありますか（擬似コードで問題ありません）？

ありがとう。

x 軸と y 軸に平行な辺を持つN 個の長方形があります。別の四角形modelがあります。モデルがN 個の長方形で完全に覆われているかどうかを判断できるアルゴリズムを作成する必要があります。

いくつかのアイデアがあります。最初に、長方形を左側で並べ替え ( O(n log n)時間で実行できます)、次に垂直方向のスイープ ラインを使用する必要があると思います。

青い長方形がモデルです。

まず、抽象アルゴリズムが必要です。実現に関して特別な要件はありません。四角形は、点のペア (左上と右下) として表すことができます。

これは、テストの準備のためのタスクの 1 つです。私は、最良のアルゴリズムがO(n log n)時間でこれを実行できることを知っています。