输入：
- 多边形(你可以把它想象成一条街道：又长又窄(
- 直线：假定直线位于多边形内，并沿多边形的全长延伸
- 必需面积：生成的输出子多边形必须具有的面积
输出：
- 输入多边形的子多边形，其面积为输入所需面积
输入和输出的示例图像：输入多边形(蓝色(、输入线(红色(、切割多边形以生成输出多边形的线(绿色(
输入多边形在沿着给定直线的某个点被切割成两块，其中一条直线(如果可能的话(垂直于该直线。
我希望我的意思很清楚——单独描述这个问题已经相当困难了。
我正在使用shapley几何体库(用于python(。多边形被描述为表示外部边界的一组点，也可以描述为描述多边形内部孔的点集。线被描述为点的列表。
您可以考虑沿着红色折线进行二进制搜索。
- 计算红色多段线的总长度(
L((=所有分段长度( - 假设我们有一个函数，可以计算点(
p(与沿着折线的值v相对应的法线(n(，其中0 <= v <= L - 假设我们有一个函数可以计算分裂的结果给定由点
p和方向定义的线的输入多边形矢量CCD_ 7 - 执行二进制搜索，从
left = 0, right = L开始，在mid(left, right)定义的线上分割多边形，并将结果区域与目标进行比较
下面是解决方案的草图：
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看起来像：
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
这种方法有几个问题：
- 它要求分割线垂直于红色多段线的一段。例如，它不考虑在端点平分相邻线段的直线
- 对于给定的目标可能有两种可能的解决方案；"左"；多边形具有所需的面积；右"；多边形可以。考虑到问题1，可能存在一个解决方案，但不存在另一个。上面概述的解决方案仅考虑"；"左"；多边形