この問題は、あるrectが別のrectにあるかどうかをテストすることとは異なります。
既知の情報は、2つの長方形の辺の長さです。
ある長方形を別の長方形に配置できるかどうかを計算するにはどうすればよいですか?
これは素晴らしい質問です!これらの条件の1つが満たされた場合にのみ、辺と( )のある小さな長方形が、辺p
とq
( )のある大きな長方形p >= q
に完全に適合します。a
b
a >= b
また
これを参照してください。
したがって、変数、、、があれa
ば、次のように評価することで、そのような長方形の配置が可能かどうかを確認できます。b
p
q
(p <= a && q <= b) || (p > a &&
b >= (2*p*q*a + (p*p-q*q)*sqrt(p*p+q*q-a*a)) / (p*p+q*q))
編集:彼のコメントにこの代替バージョンを投稿してくれた@amulwareに感謝します:
最初に行うチェックは、もちろん、長方形が軸に沿った方向のいずれかで他の長方形の内側に収まるかどうかです。
そうでない場合、それを適合させるための唯一のオプションは対角線ですが、実際にはそれが適合する多くの角度があるかもしれません。難しいのは、推測するだけでなく、実際に可能な角度が存在する場合はそれを計算することです。
ここで、内側の長方形が実際に対角線上に収まる場合、反対側の角が外側の長方形の上端と下端の両方、または左右のいずれかに接触する場合は、2つまで回転できることに注意してください。(あなたの図では、多かれ少なかれ最初のものです。)
その場合、あなたはすでにそれをその一次元(この例ではy軸)に収めていることを知っています。次に、他の次元の内側の長方形の境界幅を計算し、それを外側のボックスの幅と照合する必要があります。
これにはもっと賢いアルゴリズムがあるかもしれませんが、私が説明していることがうまくいくと100%確信しています。これの数学を自分で理解できるかどうかを教えてください(これが良い解決策だと思う場合)、そうでない場合は、後で試してみる可能性があります。私のアルゴリズムは三角関数なしで完全に実装できるのだろうか...
編集: わかりました、私は抵抗できませんでした...
上記の問題を解決するために私が行った数学は次のとおりです。(申し訳ありませんが、画像形式でのみ、私の手書きが読めることを願っています。) 誰かが私の数学をチェックできれば幸いです。現在、どの手順にも問題はありませんが、他の人に確認してもらうことをお勧めします。(そしてもちろん:これは自己責任で使用してください。)
誰かがこのアルゴリズムに何か問題を見つけた場合は、私に知らせてください。できるだけ早く修正します。
また、それほど複雑でない数学を含む、より良い解決策を誰かが持っているかどうかを確認することに非常に興味があります。多分ベクトルベースのアプローチ?
そうですね、ARSソリューションは正しいように見えますが、それでもソリューションを投稿しようとします。難しいですが、ある長方形を別の長方形に具体的に埋め込むことができます(可能な場合)。
a>b
それとを仮定しましょうp > q
。a > p
との場合、解決策は明らかですb > q
。a<p
この問題は、との場合にも解決できますb>q
。添付の写真を見てください。必要なのは最後の不等式システムだけです(興味がある場合は、それがどのように導き出されたかを見ることができます)。
必要なのは、最後の不等式システムにとの間にある解があることを確認することだけ0
です1
。これを行うには、各不等式を方程式として解く必要があります(通常の2次方程式のように)。解決策がない場合(それはありそうもない)、不等式の解決策は完全な実数直線です。方程式に2つの(おそらく等しい)解がt_1
ありt_2
、不等式の解がセグメント[-infinity, t_1]
結合されている場合[t_2, infinity]
。両方の不等式の解を得た後、それらを交差させる必要があります。ここで、それが角度(との間)であることを思い出すt
必要cos
が0
あります。pi/2
したがって、不等式にはとの間の解が必要0
です1
。その場合、2番目の長方形を最初の長方形に埋め込むことができます。そして、あなたが例えばを取る場合t_1
(方程式の小さい方の根)長方形のconcreate埋め込みを作成できます。
2つの単純なケースをかなり簡単に取り除くことができます。
難しいのは、スケッチのような角度で収まるかどうかを検討することです。簡単な式はわかりません。おそらくプラグアンドチャグソリューションが必要です。
MathematicsStackExchangeサイトにとって良い質問かもしれません。
追加: これが100%確実かどうかはわかりませんが、2番目の斜辺が最初の斜辺よりも小さければ収まると思います。
おっと:いいえ-私はそれを取り戻します。しかし、2番目の斜辺が最初の斜辺よりも大きい場合、それは適合しません。