最大自交多边形的面积

Question

我正在寻找一种算法，用于计算自交多边形的最大面积。由于它是自交的，因此使用诸如鞋带公式之类的方法计算面积并不容易。

示例：

在这个例子中，多边形优先考虑字母顺序最小的顶点，有时会以非字母顺序返回到相同的顶点，因为它是自相交的。尽管如此，在预期面积上不应该有任何区别。

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

约束条件：

- 交点事先已知，无需计算（如示例所示） - 最后一个点保证连接回图形，即没有悬挂的线 - 多边形始终是可追踪的，即可以画出来，而不需要抬起笔 - 时间复杂度理想情况下不劣于O(n log(n))，其中n是点数

感谢您的帮助！

- satoshi

---

最后一个点是否保证与图形连接，即没有悬空线条？ - Carlos

它总是可追溯的，对吧？你可以在不抬笔的情况下画出这个图形？ - Carlos

我认为真正的问题是哪些点在一个更大的多边形内。一旦你把它们移除了，Shoelace算法就可以工作了。为此，我找到了这个链接：https://en.wikipedia.org/wiki/Point_in_polygon。不过我还不确定该如何继续，正在考虑中。 - Carlos

我想你会构建一组线段，并针对每个点测试一条射线以计算交点数量，从而确定该点是内部还是外部。然后构建一组已删除内部点的点集。 - Carlos

在图形上，多边形的顶点不是“按字母顺序排列的”：D->B，B->E... 一些顶点有多个入射线段（D&F->B），一些顶点有多个出射线段（B->C&E）。 - Reblochon Masque

Answer 1

我想我懂了。

1. 找到 x 坐标最小的顶点。如果有多个，则选择 y 坐标最小的顶点。这个过程的时间复杂度是 O(n)。
2. 在与第一步中找到的顶点相连的 2 条或以上线段中，选择与 x 轴夹角最小的线段，以便按顺时针方向遍历多边形。这个过程的时间复杂度是 O(s)，其中 s 是与起始顶点相连的线段数。
3. 保持选择下一个相连的线段，忽略原始多边形中的线段顺序。如果出现交叉，则选择与当前线段逆时针方向夹角最小的线段，以便选择位于多边形外部的线段。这个过程的时间复杂度是 O(n i/2)，其中 i 是每个顶点相连的平均线段数。
4. 回到起点后，使用鞋带公式计算面积。在步骤 2 和 3 中遍历多边形时，实际上可以并行计算面积。

这个算法的最坏时间复杂度为 O(n i/2)，其中 n 是顶点数，i 是每个顶点连接的平均线段数。当多边形不相交时，最佳情况的复杂度为 O(n)。在我的案例中，多边形很少相交，因此这个过程接近于 O(n)。

- satoshi

---

我认为这可能有效，看起来有点像我们研究过的 Graham 扫描算法。我会给你一票。 - Carlos

Answer 2

1. 根据给定的点构建线段集
2. 对于每个点，测试一条射线是否与这些线段相交了偶数次或奇数次。
3. 偶数次相交计数是内部点，将其删除。
4. Shoelace算法告诉你剩余形状的面积。

让我想一种不是n^2的方法，因为你要比较n个点和n个线段。

- Carlos

---

是的，谢谢你提供这个方案，这是我能想到的最好的方法，但正如你所说的“O(n²)”，并不理想... - satoshi

@satoshi 请考虑是否有用使用一个点(x,y)，其中x和y都比集合中的最小值更低，即在集合的左下角，然后计算到所有点的角度，并进行nlogn排序。我还没有完全想清楚。 - Carlos

嗨@Carlos，是的，我一直在考虑类似于Graham扫描算法用于凸包的东西，但我无法完全适应它来解决我的问题。 - satoshi