CODEWITHSUNDEEP
geometrypolygoncomputational-geometrydata-partitioningconvex
Jason Davies
Jason Davies

Reputation: 4693

How do I split a convex polygon into two areas of a given proportion?

Given a convex polygon P and a point A on P's boundary, how do I compute a point B also on P's boundary such that AB splits P into two areas of a given proportion?

Ideally I'd like an analytical solution. As a last resort I can draw a line anywhere on the polygon and gradually move it until the proportion is correct to a given precision.

I've worked out how to calculate B once I know between which two points on the polygon it should go. So if there's a way to find out between which points it should go, I should be able to take it from there!

Upvotes: 2

Views: 1115

Answers (2)

Jason Davies
Jason Davies

Reputation: 4693

As often is the case, I've answered my own question only minutes after posting it!

My code to determine between which points B should go looks something like:

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

It turns out that I just needed to insert the last element of the area summation formula into the same check:

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

Note that the areas[] array above contains each element of the area summation formula.

This is similar in spirit to Guffa's answer, but slightly more efficient.

Upvotes: 2

Guffa
Guffa

Reputation: 700790

Split the polygon into triangles from the point A, and calculate their areas. Then you can add triangles from each end to each polygon depending on their proportions, until there is only one triangle left. Then you know that the point B is somewhere on the base of that triangle.

Upvotes: 3

Related Questions