我面临以下问题：我在整数网格上给出了一组坐标，这些坐标定义了多边形的顶点。多边形保证是凸的。事实证明，这样的多边形总是可以被 2 条正交线切割成 4 个面积相等的部分。我们称这些线的交点为P。鉴于该集合，我应该计算P多边形内的坐标和线条需要打开的角度，以便线条将多边形切割成 4 个相等的部分。
我意识到，总的来说，蛋糕切割问题没有“好的”解决方案。但它的这种特殊情况应该。我已经搜索了一种算法来解决这个问题，但没有发现任何有用的东西。我应该去哪里看？
我的方法是计算多边形中心的坐标（可以或多或少容易地完成），放置P在那里，然后“摆动”线条，直到部件的区域匹配。但这听起来太不雅了。
UPD：这就是我正在处理的问题。也许这个问题应该暂停，直到我提出实际的代码问题。
这是解决方案的部分草图：
选择任意方向并找到平行于将多边形一分为二的方向的线。为此，请在每个顶点上画一条线以将多边形分解为平板。板的相应区域将告诉您所需的线相交的板。简单的线性插值将给出直线的确切位置。
现在你的多边形被分成两个凸多边形。对于每一半，使用垂直方向重复上述过程。一般来说，你会得到两个不同的分离器，剩下要做的就是找到方向，使它们确实重合。
在给定方向上，分割器与多边形的四个特定边相交。如果稍微旋转，它们仍然与相同的四个边相交。您可以在角度范围内分解一个完整的转弯，以使四个相交的边保持不变。
知道四个相交的边，您可以建立关系，告诉您两个垂直分离器之间的距离作为角度的函数。然后您可以计算两个分离器重合的角度，并检查该角度是否属于为这些边定义的范围。
通过依次尝试所有范围，您将找到解决方案。
注意：角度范围的限制对应于平行或垂直于连接两个顶点的线的方向。