2

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

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

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

4

2 回答 2

3

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

于 2011-06-22T14:45:34.787 回答
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[] 数组包含面积求和公式的每个元素。

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

于 2011-06-22T14:48:54.873 回答