给定一个多边形和其中的线：找到线上的位置，用垂直线分割多边形以获得具有特定面积的子多边形

Question

输入：

多边形（你可以把它想象成一条街道：又长又窄）
线：假定线位于多边形内并运行沿着多边形的全长
所需面积：生成的输出子多边形必须具有的面积

输出：

输入多边形的子多边形，其面积为输入所需面积。

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

输入多边形在给定线的某个点被切成两部分，其中一条线（如果可能）垂直于该线。

我希望你明白我的意思 - 单独描述这个问题已经相当困难了。

我正在使用 shapley 几何库（针对 python）。多边形被描述为表示外边界的一组点，也可以选择描述多边形内部孔的点集。线被描述为点列表。

Answer 1

您可以考虑沿红色折线进行二分查找。

计算红色折线的总长度（L）（=所有的总和段长度）
假设我们有一个函数可以计算点 (p) 和法线 (n) 对应于沿折线的值 v，其中 0 <= v <= L.
假设我们有一个可以计算拆分结果的函数给定一条由点 p 和方向定义的线的输入多边形向量 n.
执行二进制搜索，从 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，可能存在一个解决方案而不存在另一个解决方案。上面草拟的解决方案仅考虑“左”多边形。

给定一个多边形和其中的线：找到线上的位置，用垂直线分割多边形以获得具有特定面积的子多边形

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

python

geometry