凸多角形 P と P の境界上の点 A が与えられた場合、AB が P を所定の比率の 2 つの領域に分割するように、P の境界上の点 B を計算するにはどうすればよいですか?
理想的には、分析ソリューションが必要です。最後の手段として、ポリゴンの任意の場所に線を描画し、比率が所定の精度になるまで徐々に移動します。
ポリゴン上のどの 2 点間を移動すべきかがわかったら、B を計算する方法を考え出しました。したがって、どのポイントの間を進むべきかを調べる方法があれば、そこから取ることができるはずです!
点 A から多角形を三角形に分割し、その面積を計算します。次に、残りの三角形が 1 つになるまで、比率に応じて各端から各ポリゴンに三角形を追加できます。次に、点 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]
上記のareas[]配列には、面積合計式の各要素が含まれていることに注意してください。
これは精神的にはGuffaの答えに似ていますが、少し効率的です。