0

ここで少し数学の最適化を行います。大学は遠く離れているので、あなたの助けが必要です... 私は本当に具体的なものを見つけようとしています. できるだけ正確にしましょう。

  • R を任意のサイズと縦横比の境界矩形とします (必要に応じて、縦横比が 2/1 と 1/2 を超えないと仮定します)。

  • C を円とし、その中心は R の内側にあり、少なくとも 1 つの点は R の内側にあります。ただし、一部の点は R の外にある可能性があります。

  • r を任意のアスペクト比とし、R のアスペクト比とは異なる可能性があります。

R' n C が最大になるように、R と完全に交差するアスペクト比 r の四角形 R' のサイズと位置を決定する既知のアルゴリズムはありますか (交差の場合は n、ここで MathML を入力する方法がわかりません)。

多項式時間には完全な解は存在しない可能性があると考える傾向があるため、タイムアウト後に停止できる反復解であっても、適切な近似値が機能します。

R と R' は回転しない、つまり、辺が単位ベクトルに平行か垂直であると予想します。しかし、R の 2 つの側面が R' の 2 つの側面に平行で、両方が任意に回転するソリューションは完全に適合します。その場合、私は特定のケースになります。

どうもありがとう、

マチュー

4

1 に答える 1

1

役立つかもしれないいくつかの観察：

R'1) ヘンリーがコメントで述べたように、「 ができるだけ大きい場合に最適化されるため、 と同じ高さまたは幅になりRます。これにより、最適化するパラメータ (1 次元の位置) が 1 つだけ残ります。」

2) これで、 の高さまたは幅に沿ってスライドできる長方形R'ができました。その中心が円の中心にできるだけ近くなるように移動すると、ほとんどの領域をカバーできることがわかると思います。RRR'

3) たとえば、比率rは常に幅/高さですか、それとも高さ/幅にすることもできますか? 言い換えると、R'より適切に収まるように回転できますRか? もしそうなら、あなたは2つの答えを考える必要がありますr != 1. R'比較するには、 と円の交点の面積を計算する必要があります。これはおそらく問題の最も難しい部分です。円の半径を指定していますか、それともエッジの一部が交差していることを知っていますRか?

4)Rが軸に対して平行でも垂直でもない場合は、平行移動を適用して円の中心を原点(0, 0)に移動し、次に回転をR適用して軸に整列させることができます。次に、 のコーナーの座標を見つけるために解いてから、 のコーナーの座標にR'逆回転と逆平行移動を適用してR'、最終的な解を見つけます。

于 2013-11-02T13:26:51.390 に答える