algorithm - 凸多边形中的最短面积二等分线

Question

我很难找到这个：

我不知道如何找到这个，甚至不知道如何编写算法来做到这一点。你能帮助我吗？

提前致谢

Answer 1

暗示：

我将按以下方式解决此问题：

• 在四边形中研究问题并建立规则，该规则将边缘上的点的位置与将面积减半的线段的长度相关联，或者更一般地分成两个指定的部分。

• 找到给出最短线的条件。

• 泛化到一般多边形的边上的一点。

我相当肯定，对于在边缘上移动的点，最小配置以有限的数量出现，并且通过扫描所有边缘，您可以枚举所有候选并找到最短的。

Answer 2

将区域一分为二的每条线都将通过一个点，称为“质心”： https ://en.wikipedia.org/wiki/Centroid

此外，通过质心的每条线都将该区域一分为二。

因此，第一步是定位质心。然后，当您在多边形周围移动一个点时，您只需从该点通过质心画一条线即可找到另一侧的点。您将遍历将区域分成两半的所有可能的线段。你的任务是找到这些段中最短的。

对于具有 N 个顶点的多边形，随着通过质心的线的角度发生变化，它会扫出 N 个不同的领结形区域，在这些区域中，两边的线多边形边缘都不会改变。当通过质心的线在任一端撞击多边形顶点时，该区域会发生变化。

解决此问题的有效算法将找到每个区域中最短的段，然后选择其中的最小值。它要么是接触多边形顶点的区域的末端之一，易于测量，要么位于中间的某个地方。

当最小距离在区域中间的某个地方时，您可以使用三元搜索 ( https://en.wikipedia.org/wiki/Ternary_search ) 找到它，或者您可以使用微积分。我会将该区域任一侧的多边形边缘转换为极坐标，使用质心作为原点然后我将翻转一个 180 度，将它们加在一起，并找到最小化半径的角度。

以这种方式工作的算法可以在 O(N) 时间内得到最短区域二等分线的准确答案。