给定一个凸多边形，添加一个点并重新计算该区域

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。