如何将凸多边形分割为给定比例的两个区域？

Question

给定一个凸多边形P和P的边界上的一个点A，我如何计算P的边界上的点B，使得AB将P分成给定比例的两个区域？

理想情况下，我想要一个解析解决方案。作为最后的手段，我可​​以在多边形上的任何地方绘制一条线，并逐渐移动它，直至比例对于给定的精度正确。

我已经计算出一旦我知道它应该去的多边形上的哪两点之间的时候如何计算B.所以如果有办法找出它应该走哪一点，我应该能够从那里拿走它！

Answer 1

将多边形从A点拆分为三角形，并计算它们的面积。然后，可以根据各自的比例将每个三角形的每个端点添加到每个多边形，直到只剩下一个三角形。然后你知道B点在那个三角形的基础上。

Answer 2

往往是这样，我已经回答了我自己的问题，发布后只有几分钟！

我的代码，以确定它们之间的部位B应该看起来像：

while areaSoFar + areas[i] < targetArea: 
    i++ 
    areaSoFar += areas[i] 

事实证明，我只需要在区域求和公式的最后一个元素插入到相同的检查：

while areaSoFar + areas[i] + points[i].x * start.y - points[i].y * start.x < targetArea: 
    i++ 
    areaSoFar += areas[i] 

请注意，上面的区域[]数组包含area summation formula的每个元素。

这与古法的答案精神相似，但效率略高一些。