給定一個凸多邊形，添加一個點並重新計算該區域

Question

假設您有一個凸多邊形P（由點陣列p定義）和一組點S（所有這些都在P之外），您如何選擇一個點s in S，這樣可以增加P的最大面積。 例
我有一個O（| P |）的公式來計算多邊形的面積，但我不能在S做到這一點，每一點因爲

3 ≤ |P|, |S| ≤ 10^5 

大點是S中的點
3個在P u S點共線

Answer 1

你必須計算出由點添加的確切面積的方法ñ（和David Eisenstat另發了一篇文章），但其複雜程度取決於多邊形的邊數。理想情況下，你會有一種方法可以快速估計附加區域，並且只需要針對有限數量的點運行確切的方法。

正如Paul在評論中指出的那樣，這樣的近似應該給出一個比實際值更大的結果;這樣，如果近似值告訴你一個點增加了小於當前最大值的面積（並且隨機排序的輸入對大多數點都是成立的），那麼你可以放棄它而不需要確切的方法。

最簡單的方法是隻測量多邊形中每個點到一個點的距離;這可以通過例如像這樣：

開始通過計算多邊形的面積，然後查找包含整個多邊形的最小圓，與中心點Ç和半徑 [R。

然後，對於每個點Ñ，計算距離 d從Ñ到Ç，和近似附加區域爲：

• 與區域三角形r ×（ d - r）
• 加上與區域2 × - [R （預先計算的）
• 加上區域 r處的半圈 × π（預先計算的）
• 減去區域的矩形的多邊形（預先計算）

該區域在下圖中以藍色表示，實際附加區域稍暗，由近似稍輕加入過量的面積：

因此，對於每一個點，則需要計算使用√（（ X _Ñ的距離 - X _Ç） +（ý_ñ - ý_ç）），然後將該距離乘以一個常數並加上一個常數。

當然，這種近似的精度取決於多邊形的形狀有多不規則;如果它根本不像一個圓，最好創建一個包含原始多邊形的較大的簡單多邊形（如三角形或矩形），然後在較大的多邊形上使用精確方法作爲近似。

---

UPDATE

在一個簡單的測試，其中所述多邊形是在100×100平方空間的中間一個1x1正方形，隨機放置在其周圍100,000點，如上所述的方法降低了數調用從100,000到150到200之間的精確測量功能，以及在這些調用中的10到20個之間導致新的最大值。

在寫爲我在測試中使用的正方形的精確測量功能，我意識到，使用軸對齊的矩形，而不是圍繞多邊形的圓導致一個更簡單的近似法：

創建圍繞多邊形的矩形，具有兩側甲和乙和中心點ç，並計算矩形和多邊形的區域。然後，對於每個點Ñ，附加區域的近似的總和：

• 與基體A和高度ABS（Y _Ñ - ý_Ç） - 三角形B/2
• 與基極B與高度ABS三角形（X _ñ - X _ç） - A/2
• 的矩形的面積減去多邊形的面積

（如果該點上方，下方或旁邊的矩形，那麼三角形中的一個具有高度< 0，並且僅添加其他三角形）

所以所需近似的步驟是：

ABS（X _ñ - X _ç）× X + ABS（Y _ñ - ý_ç）× Y + Z

其中X，Y和Z是常數，即2次減法，2次加法，2次乘法和2次絕對值。這比圓方法更簡單，矩形也更適合長方形多邊形。對精確測量功能的調用次數的減少應與上述測試結果類似。

Answer 2

給定的固定點p =（PX，PY），Q =（QX，QY）和一個可變點s =（SX，SY），三角形的符號面積Δpqs是

|px py 1| 
½ |qx qy 1| 
    |sx sy 1| , 

這是sx，sy中的一個線性多項式。

一種方法是計算這些多項式的累積和，其中p，q是順時針順序的邊。使用二分查找找到保留在凸包中的邊的子列表，給定點s，添加多項式並評估s。