algorithm - 自相交多边形的最大面积

Question

我正在寻找一种算法来计算自相交多边形中的最大面积。由于它是自相交的，因此使用鞋带公式等方法计算面积并非易事。

例子:

示例中的多边形按字母顺序对具有“最小”字母的顶点进行优先排序，有时会以非字母顺序返回到同一顶点，因为它是自相交的。尽管这不会对预期区域产生影响。

在这种情况下，算法应输出 40:正方形的面积 (36) 加上 4 个外三角形的面积 (4)。

约束:

• 交叉点是预先知道的，不需要计算它们(如示例所示)
• 最后一点保证连接回图形，即没有悬垂线
• 多边形始终是可追踪的，即无需提笔即可绘制
• 理想情况下，时间复杂度不低于 O(n log(n))，其中 n 是点数

感谢您的帮助!

Answer 1

我想我明白了。

1. 找到具有最小x 的顶点。如果出现平局，请选择 y 最低的那个。这个过程是O(n)
2. 在连接到点 1 中找到的顶点的 2+ 段中，选择与 x 轴形成最小角度的段，以便开始沿顺时针方向遍历多边形。此过程是 O(s)，其中 s 是连接到起始顶点的线段数。
3. 继续选择下一个连接线段，忽略线段在原始多边形中的顺序。在相交的情况下，选择与当前线段形成最小角度的线段，方向取反，顺时针测量。这是为了选择位于多边形外部的线段。此过程是 O(n i/2)，其中 i 是连接到每个顶点的线段的平均数。
4. 回到起点后，使用鞋带公式计算面积。这实际上可以在遍历点 2 和点 3 中的多边形时并行计算。

该算法最坏情况下的时间复杂度是O(n i/2) 其中n是顶点数，i是平均数连接到每个顶点的线段。对于从不相交的多边形，最好的情况复杂度是 O(n)。在我的例子中，多边形很少相交，所以这个过程接近 O(n)。