6

これは数学に焦点を当てた質問かもしれませんが、CSのコンテキストにあるため、ここで質問したいと思います。別の（任意の）クワッドの内側に、可能な限り最大の高さと幅を持つ内接クワッドで長方形を内接することを検討しています。アルゴリズムも似ていると思うので、サークルでもできるかと思っています。

より明確に聞くことは、例として境界四辺形が意味することです。 ここに画像の説明を入力してください

これが私が達成しようとしている内接最大化の2つの例です： ここに画像の説明を入力してください ここに画像の説明を入力してください

私はいくつかの予備調査を行いましたが、決定的なものは何も見つかりませんでした。何らかの形の動的計画法が解決策になる可能性があるようです。これは線形最適化問題であり、私が見つけたよりも一般的であるはずであり、おそらく私は間違った用語を探しています。

注： 内接正方形については、探しているターゲットのw / h比がわかっていると仮定します（例：4：3）。クワッドの場合、辺が交差せず、凹面になると想定します（計算が簡単になる場合）。

4

2 に答える 2

4

1) 円。
三角形の場合、これは学校のプログラムの標準的な数学の問題です。
四角形の場合、最大の内側の円が少なくとも 3 つの辺に接していることがわかります。したがって、3 辺のすべての組み合わせを取り、それぞれの三角形について問題を解きます。
平行な辺の場合は (三角形を形成しないため) 個別に考慮する必要がありますが、それほど難しくありません。

2) 長方形。「最大の高さと幅」を
持つことはできません。別の基準を選択する必要があります。たとえば、あなたの写真では、高さを減らすことで幅を増やすことができ、その逆も可能です。

于 2011-02-06T14:36:59.713 に答える
1

4年前のスレッドですが、問題をグーグルで調べているときにたまたま見つけました。

現在のCVアプリケーションでこのような問題があります。最大のものを見つけるための単純でやや不器用な解決策を思いつきました。まったく同じではありませんが、辺の比率を固定せずに長方形の面積を最大化するためです。

私のソリューションが最適なものを見つけるかどうか、またはすべての場合に機能するかどうかはまだわかりません。効率の良い方法もあると思いますので、ご意見をお待ちしております。

まず、(凸) 四角形を形成する 4 つの点のセットを想定します。

    x   y
P1  -2  -5
P2  1   7
P3  4   5  
P4  3   -2

この手順では、一番左のポイントが P1 で、次のポイントは時計回りに番号が付けられます。次のようになります。

四角形

次に、ポイント間の線形関数を作成します。各関数について、傾き k と 0 からの距離 d を知る必要があります。k は単純に、2 つのポイントの Y の差を X の差で割ったものです。d は、線形関数を d に解くことによって計算できます。だから私たちは持っています

k=dy/dx
d=y1-k*x1

逆関数も必要になります。

k_inv = 1/k
d_inv = -d/k

次に、四角形の各辺の関数と逆関数を作成します

        k        d                        k         d
p1p2    4       3           p1p2_inv    0.25    -0.75
p2p3    -0.67   7.67        p2p3_inv    -1.5    11.5
p3p4    7       -23         p3p4_inv    0.14    3.29
p4p1    0.6     -3.8        p4p1_inv    1.67    6.33

完全に水平線または垂直線がある場合、関数または逆関数のいずれかで DIV/0 になるため、このケースを個別に処理する必要があります。

ここで、符号が異なる勾配を持つ ak を持つ 2 つの関数で囲まれたすべてのコーナーを通過します。私たちの場合、それは P2 と P3 です。

P2 から開始し、適切なステップ サイズで P2 と P1 および P3 の高い値の間の y 値を反復処理し、逆関数を使用して関数間の水平方向の距離を計算します。これにより、長方形の一辺が得られます

a=p2p3_inv(y)-p1p2_inv(y)

2 つの x 値 x = p2p3_inv(y) と x = p1p2_inv(y) で、2 つの反対関数に対する y の差を計算し、現在の y 位置までの距離を長方形の 2 番目の辺の候補として取得します。

b_candidate_1 = y-p4p1(p2p3_inv(y))
b_candidate_2 = y-p4p1(p1p2_inv(y))
b_candidate_3 = y-P3p4(p2p3_inv(y))
b_candidate_4 = y-P3p4(p1p2_inv(y))

4 つのパラメータのうち小さい方がサイド b の解になります。面積は明らかに a*b になります。

私はデモンストレーションのためにエクセルで簡単な例を作りました:

ここに画像の説明を入力

ここでの最小 b は 6.9 であるため、ソリューションの右上隅は p2p3 にあり、長方形は a を水平方向に、b を垂直方向にそれぞれ左と下に拡張します。

したがって、長方形の 4 つの点は次のようになります。

Rect    x       y
R1      0.65    -1.3
R2      0.65    5.6
R3      3.1     5.6
R4      3.1     -1.3

ここに画像の説明を入力

これを C++ コードに入れ、いくつかのテストを実行して、解決策が一般化するかどうか、またはこれが単なる「運」であるかどうかを確認します。

関数によって A=a*b の a と b を置換し、p1p2 が P1 と P2 の間でのみ定義されているという条件の下で最大化する必要がある 1 つの線形式に入れることも可能であると思います...

于 2015-06-04T02:05:36.793 に答える