geometry - 如何将凸多边形分成给定比例的两个区域？

Question

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

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

一旦我知道它应该在多边形上的哪两个点之间，我已经计算出如何计算 B 。因此，如果有办法找出它应该在哪些点之间移动，我应该能够从那里拿走它！

score 3 · Accepted Answer

从A点将多边形分割成三角形，并计算它们的面积。然后你可以根据它们的比例从每一端添加三角形到每个多边形，直到只剩下一个三角形。然后你就知道 B 点在那个三角形底边的某个地方。

score 2 · Accepted Answer

通常情况下，我在发布后几分钟就回答了我自己的问题！

我确定 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[] 数组包含面积求和公式的每个元素。

这在精神上与 Guffa 的答案相似，但效率更高。

2 回答 2