将二维多边形分成两半的算法

Question

寻找一种算法，将自定义 2D 多边形作为输入。 该算法应将多边形分成两半，并根据面积产生两个（至少大约）相等的一半。

到目前为止我的想法是：

1. 将多边形放在高分辨率网格上 --> 如果多边形在其中，则用 1 标记单元格，否则为 0
2. 找到一个在边缘的单元格（至少有一个邻居为 0）
3. 开始添加相邻单元格，而单元格面积为< half of the polygons area

我很好奇在速度或准确性方面是否有比这更好的解决方案。

Answer 1

快速、精确的解决方案简单多边形：

1. 三角化多边形。
2. 计算每个三角形的面积。
3. 形成对偶树，其中每个节点的权重等于相应三角形的面积。
4. 找到节点，当删除时，留下连接的组件，每个组件的总重量最多为多边形面积的一半。
5. 剩下的最大连通分量包含在一半中，其他包含在另一半中。切割对应于移除节点的三角形，使它们均匀（如果它有三个邻居，你可能需要两段）。

Step 1 有一个 O(n log n)-time 算法。 （有更快的算法，但我不知道它们有多复杂。）

第 2 步和第 3 步显然是 O(n)。

Step 4 有一个 O(n)-time 算法。将树放在某处，并使用深度优先搜索计算每个子树的总数。从根节点开始，通过占总总数一半以上的孩子重复下降，直到不再可能为止。

第 5 步是 O(1) 时间。