如何識別周圍的矩形

Question

如何識別給定點的近似周圍矩形？

預期輸出：如下圖所示。

輸入：下部。

Answer 1

我的建議是做遵循兩個步驟：

1. 找到點
2. 找到一個凸多邊形的最小邊界框可以在O（N）來解決的convex hull，這個algorithm以下

編輯：好的，其實上述2個步驟是不足以成爲一個正確和接受的答案。

在這兩個步驟之前，您必須先對該組點進行預處理。

1. 檢查是否有3個或更多點共線，除去兩個端點以外的點。
2. 第1步之後，你現在應該得到一組沒有3點或多點共線的點。

檢查集合的大小：如果它只剩下1點或2點，你必須特別處理它們（對於1點，你可以找到任何最小的方框來包含它自己的方法; 2點也許使他們成爲邊框的對角線）

如果結果集已經離開> = 3分，那麼只要按照我原來的2個步驟：凸包+旋轉卡鉗

歡呼。

Answer 2

看起來這是一個minimzation problem with constraints。

你需要找到4條線路：

l1: a1x + b1y + c1 = 0 
l2: a1x + b1y + c2 = 0 
l3: a2x + b2y + c3 = 0 
l4: a2x + b2y + c4 = 0 

所以，你有8個變量：a1,a2,b1,b2,c1,c2,c3,c4

您需要減少：

Sum(distance(li,point_j) | i from [1,4], j - over all points) 

受到約束：

l1 dot l3 = 0 [ensuring rectangle - cosine=0->angle between lines=90] 
for each point j: 
a1xj + b1yj + c1 >=0 ['above' l1] 
a1xj + b1yj + c2 <= 0 ['below' l2] 
(similarly for l3,l4) 

請注意，您可以更改目標函數以匹配其他最小化標準，如最小面積。