Given are:
The ordered points of a convex, non-intersecting polygon
An area value (always smaller than the area of the initial polygon)
Question:
- Where does a horizontal line have to cut through the polygon, so one of the two resulting polygons has exactly the given area?
Context:
- This is needed for a feature in a game. Procedurally generated (random) terrain shall be floodable with water bodies of player-controled volume.
What I have tried so far: Unfortunately not a lot as I'm missing an entry point for an efficient algorithm.
What I could do is to sorta apply the "divide and conquer" method: Slice the polygon into two halves and recompute the area of each half. If volume of lower half is too small, split the upper half and add its half to the lower half from before. Otherwise split lower half and continue from there. Repeat this until the area is close enough to the target value.
Unfortunately that results in recomputing area over and over which might be too slow for a real-time feature.
Any more mathematical approach?