我如何在任意四邊形內刻出一個矩形或圓形

Question

這可能是一個更關注數學的問題，但是想在這裏問一下，因爲它在CS環境中。我正在尋找在另一個（任意）四邊形內刻出矩形，其中具有最大高度和寬度的內接四邊形可能。因爲我認爲算法會類似，所以我期待着看看我是否也可以用圓圈來做這個。

爲了更清楚聽到我的意思是以邊界四邊形爲例。

下面是刻最大化的兩個例子，我想實現：

我已經做了一些初步的搜索，但沒有發現任何明確的。似乎某種形式的動態編程可能是解決方案。看起來這應該是一個線性優化問題，應該比我發現的更普遍，也許我正在尋找錯誤的術語。

備註：對於刻寫的方塊，假設我們知道目標w/h比率，我們正在尋找（例如4：3）。對於四邊形，假定邊不會交叉，並且它將是凹的（如果這簡化了計算）。

Answer 1

1）Circle。
對於三角形，這是一個來自學校計劃的standard math question。
對於四邊形，您可以注意到最大內圓至少會觸及其三個邊。因此，採取三方面的每個組合並解決每個三角形的問題。
平行邊的情況必須分開考慮（因爲它們不形成三角形），但這並不是非常困難。

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只不過是兩點的Y的差異除以X的差異而已。可以通過求解d的線性函數來計算d0。所以我們有

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或者反函數，因此我們需要分別處理這種情況。

現在我們通過兩個函數所包含的所有角落，這兩個函數具有不同符號的斜率。在我們的情況下，這將是P2和P3。

我們從P2開始，用適當的步長迭代P2和P1和P3中較高的一個之間的y值，並使用反函數來計算水平方向上函數之間的距離。這將使我們矩形

a=p2p3_inv(y)-p1p2_inv(y) 

在兩個X值x = p2p3_inv（Y）並且x = p1p2_inv（Y），那麼我們計算在y中的差異在兩個相反的功能，並採取的距離的一側到我們當前的y位置作爲我們矩形第二面的候選位置。

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)) 

四個參數中較小的一個將是b方案的解決方案。 該地區顯然成爲a * b。

我確實在Excel一個簡單的例子來證明：

最小B給是6.9，因此該溶液的右上角是上P2P3和矩形在水平和b延伸的分別垂直於左邊和底部。

矩形的四點是這樣

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之間定義的條件下必須最大化的線性公式中。 ...