Given a polygon & line in It: Find position on line where to split the polygon with perpendicular line to get subpolygon with cetain area

Question

Inputs:

Polygon (you can imagine this as a street: long and relatively narrow)
Line: the line is assumed to lie within the polygon and to run along the full length of the polygon
Required Area: The area the resulting output sub-polygon must have

Outputs:

Subpolygon of the input polygon with an area of the required area from input.

Example image of inputs and outputs: input polygon (blue), input line (red), line where the polygon is cut to produce output polygon (green)

The input polygon is cut into two pieces at some point along the given line, with a line that is (if possible) perpendicular to the line.

I hope its clear what I mean - it's already rather difficult to alone describe the problem.

I'm using the shapley geometry library (for python). Polygons are described as a set of points that represent the outer boundary and optionally also sets of point that describe holes inside the polygon. Lines are described as a list of points.

RaffleBuffle RaffleBuffle · Accepted Answer · 2021-07-12T17:00:31

You could consider a binary search along the red polyline.

Calculate the total length (L) of the red polyline (= sum of all segment lengths)
Assume we have a function that can calculate the point (p) and normal (n) corresponding to a value v along the polyline, where 0 <= v <= L.
Assume we have a function that can calculate the result of splitting the input polygon given a line defined by a point p and direction vector n.
Perform a binary search, starting with left = 0, right = L, splitting the polygon at the line defined by mid(left, right) and comparing the resulting areas against the target.

Here's a sketch of the solution:

fn areaSearch(polygon, polyline, aTarget)

  left = 0
  right = length(polyline)

  while left < right
    mid = left + (right-left)/2;
    (p,n) = pointNormal(polyline, mid)
    (aLeft, aRight) = split(polygon, p, n)

    if aLeft eq aTarget or aRight eq aTarget return (p, n)

    if aLeft < aTarget
     right = mid
    else
     left = mid

pointNormal would look something like:

fn pointNormal(polyline, v) 
  for each segment of polyline
    len = len(segment)
    if v < len
      p = segment.start + v*unit(segment) 
      n = segment normal
      return (p, n)
    else
      v = v - len

There are a couple of issues with this approach:

It requires the splitting line to be perpendicular to a segment of the red polyline. It doesn't, for example, consider lines that bisect adjacent segments at endpoints.
For a given target there could be two possible solutions, one where the "left" polygon has the required area and another where the "right" polygon does. It's possible that a solution exists for one but not the other, given issue 1. The solution sketched above only consider the "left" polygon.

Given a polygon & line in It: Find position on line where to split the polygon with perpendicular line to get subpolygon with cetain area

1 Answers