给定凸多边形 P 和 P 边界上的点 A,我如何计算 P 边界上的点 B 使得 AB 将 P 分成给定比例的两个区域?
理想情况下,我想要一个分析解决方案。作为最后的手段,我可以在多边形的任何地方画一条线并逐渐移动它,直到比例正确到给定的精度。
一旦我知道它应该在多边形上的哪两个点之间,我已经计算出如何计算 B 。因此,如果有办法找出它应该在哪些点之间移动,我应该能够从那里拿走它!
给定凸多边形 P 和 P 边界上的点 A,我如何计算 P 边界上的点 B 使得 AB 将 P 分成给定比例的两个区域?
理想情况下,我想要一个分析解决方案。作为最后的手段,我可以在多边形的任何地方画一条线并逐渐移动它,直到比例正确到给定的精度。
一旦我知道它应该在多边形上的哪两个点之间,我已经计算出如何计算 B 。因此,如果有办法找出它应该在哪些点之间移动,我应该能够从那里拿走它!
从A点将多边形分割成三角形,并计算它们的面积。然后你可以根据它们的比例从每一端添加三角形到每个多边形,直到只剩下一个三角形。然后你就知道 B 点在那个三角形底边的某个地方。
通常情况下,我在发布后几分钟就回答了我自己的问题!
我确定 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 的答案相似,但效率更高。