どのように任意の四辺形の中に矩形または円を書くことができますか

Question

これはもっと数学的に重視される質問かもしれませんが、CS文脈の中にあるのでここで質問したいと思っていました。私は可能な最大の高さと幅を持つ刻まれたクワッドを持つ別の（任意の）クアッドの内側に四角形を刻むことを探しています。私はアルゴリズムが似ていると思うので、私は円でこれを行うことができるかどうかを見ています。

もっと明確に聞くと、境界四角形が例として挙げられます。私はいくつかの予備検索を行っているが、決定的な何かを発見していない

：

は、ここで私が達成しようとしている内接最大化の2例です。動的プログラミングの何らかの形が解決策になると思われます。これは、私が見つけたよりも一般的なはずの線形最適化問題でなければならないと思われます。おそらく私は間違った条件を探しています。

注：刻まれた四角形については、私たちが探している目標w/h比（例えば4：3）を知っていると仮定します。四辺については、辺が交差しないこと、およびそれが凹であると仮定します（計算が簡単になる場合）。

Answer 1

1）円。
三角形の場合、これは学校プログラムのstandard math questionです。
四辺形の場合、最大内円が少なくとも3つの辺に接触することがわかります。だから、3つの面のあらゆる組み合わせを取って、各三角形の問題を解く。
平行な場合の場合は別々に考慮する必要があります（三角形を形成しないため）が、それほど難しいことではありません。

2）長方形。
「最大の高さと幅」を使用することはできません。別の条件を選択する必要があります。たとえば、写真上では高さを減らすことで幅を広げることができます。

Answer 2

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 

我々は機能の一つでDIV/0で終わるだろう、完全に水平または垂直の線を持っていた場合私たちは、その後、四辺形

 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 

の各側面のための機能と逆機能を作成

逆関数を使用しているため、このケースを個別に処理する必要があります。

ここでは、記号が異なる勾配のkを持つ2つの関数で囲まれたすべてのコーナーを調べます。私たちの場合、それはP2とP3になります。

P2から始まり、P1とP3のうちの高い方の値の間のy値を適切なステップサイズで反復し、逆関数を使用して関数間の水平方向の距離を計算します。これは私達に二つのXの値X = p2p3_inv（Y）とx = p1p2_inv（y）における

a=p2p3_inv(y)-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になります。

は私が証明するために、Excelで簡単な例をした：

ここでB最小値は6.9であるので、ソリューションの右上隅には、P2P3上にあり、長方形が水平とBに延びていますそれぞれ上下左右に移動する。

長方形の四点は、私はC++コードにこれを配置する必要があります、これはちょうどだった場合ソリューションが一般化かどうかを確認するためにいくつかのテストを実行したりしますので、

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

です"運"。

関数でA = a * bのaとbを代入し、それをP1とP2などの間でのみ定義された条件で最大化する必要がある1つの線形式に入れることもできるはずです...