Comment diviser un polygone convexe en deux zones d'une proportion donnée?

Question

Étant donné un polygone convexe P et un point A sur la frontière de P, comment puis-je calculer un point B également sur la limite de P de sorte que AB divise P en deux zones d'une proportion donnée?

Idéalement, je voudrais une solution analytique. En dernier recours, je peux tracer une ligne n'importe où sur le polygone et la déplacer progressivement jusqu'à ce que la proportion soit correcte pour une précision donnée.

J'ai travaillé sur la façon de calculer B une fois que je sais, entre lesquels deux points sur le polygone il devrait aller. Donc, s'il y a un moyen de savoir entre quels points il devrait aller, je devrais être capable de le prendre à partir de là!

Answer 1

de Split le polygone en triangles à partir du point A, et calculer leurs domaines. Ensuite, vous pouvez ajouter des triangles de chaque extrémité à chaque polygone en fonction de leurs proportions, jusqu'à ce qu'il ne reste plus qu'un triangle. Alors vous savez que le point B est quelque part sur la base de ce triangle.

Answer 2

Comme souvent c'est le cas, j'ai répondu à ma propre question quelques minutes après l'avoir posté!

Mon code pour déterminer entre quels points B devrait aller ressemble à quelque chose comme:

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

Il se trouve que je avais juste besoin d'insérer le dernier élément de la formule de sommation de la zone dans la même vérification:

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

Notez que les zones [] tableau ci-dessus contient tous les éléments du area summation formula.

Ceci est similaire dans l'esprit à la réponse de Guffa, mais légèrement plus efficace.