區四邊形

Question

的我在一個平面ñ點和目標區域P。我試圖找到四個點，它們的面積是四邊形的角落，面積最接近P。下面是Ñ = 5和P上的示例 = 30：

• 0,0
• 10，0
• 0,10
• 10,10
• 7,3

答案應該是30.0（最接近P，在此情況下它是平等的）。

你有任何想法如何，我能做到這一點？我知道我可以使用Heron的公式計算每個四邊形的面積，但是我必須嘗試每種組合還是有一些更短的方法？

Answer 1

一般來說，我不認爲提高了對最壞情況下的遍歷所有可能的四邊形的算法。如果面積小於點的面積，則可以使用quadtree排列來排除太遠而無法制作合理的四邊形的點。但即使在那裏，你也必須小心，因爲可能有一個非常薄的具有遠點的四邊形將只有正確的區域，所以你可能不得不將自己歸於四次算法。

但是你可以使用加速：當你有三個點時，找到相關三角形的面積，如果它大於abs（目標面積 - 目前爲止的最佳面積），那麼你不需要嘗試任何值爲第四點。

正如我在你需要Bretschneider's formula的四邊形區域的評論中提到，蒼鷺的是三角形。

Answer 2

可以

1. 採取與頂點和形狀的所需數量的單位/模板多邊形。

2. 乘法比例因子t添加到它，這樣它的座標樣子

   0, 0 
   10t, 0 
   0, 10t 
   10t, 10t 
   7t, 3t 
   

3. 使用shoelace formula找出區域，說f(t)。

4. 解決縮放係數t和你的多邊形的相關座標多項式方程f(t) = 30.0。

這應該給你你想要的區域（30.0）的多邊形。

順便說一句，我假設你知道多邊形的形狀，否則，有（無限），能適合你的目標地區的許多解決方案。