时间戳

首页 > 解决方案 > 包含在分段直线简单闭合曲线中的面积

algorithm - 包含在分段直线简单闭合曲线中的面积

问题描述

我有平面点 pi i=1,...,n 并且它们形成一个简单的闭合但不一定是凸曲线。从 pi 到 p(i+1) 和从 pn 到 p1 的曲线是直线。我需要一种算法来计算包含的区域。

标签： algorithm

解决方案

让我们将问题分解为更小、更易于管理的问题。

想法：
将其分解为三角形并求和它们的面积。在每次迭代中，获取一个凸点（相对于之前和之后的点），获取该三角形的面积 ( area(p(i), p(i-1), p(i+1))) 并将该点从仍待处理的相关点列表中删除。

关于检查一个点是否在凸多边形内的主题，我将假设这些点顺时针方向（如果不是，则反转它们以交换角度上的条件）。基本上，给定p(i), p(j), p(k)位置i + 1 = j和j + 1 = k（连续），壁架之间的角度edge(i, j)和edge(j, k)将告诉我们p(j)是凹的还是凸的。这个解决方案可以在这里看到

totlaArea = 0
listOfPoints = inputtedPoints

getThreeAdjacentPoints(listOfPoints, index) {
  n = listOfPoints.length
  point1 = listOfPoints[pointIndex]
  point2 = listOfPoints[(pointIndex + 1) % n]
  point3 = listOfPoints[(pointIndex - 1) % n]
  return { point1, point2, point3 }
}

getTriangleArea(listOfPoints, index) {
  { point1, point2, point3 } = getThreeAdjacentPoints(listOfPoints, index)
  return calculateTriangleArea(point1, point2, point3)
}

getNextConvexPointIndex(listOfPoints) {
  for index in listOfPoints.length - 1:
    { point1, point2, point3 } = getThreeAdjacentPoints(listOfPoints, index)
    angleBetweenEdges = getAngle(edge(point3, point1), edge(point1, point2))
    if angleBetweenEdges < 180:
      return index

  // Will never actually reach here unless code error:
  return -1
}

while listOfPoints.length > 2:
  pointIndex = getNextConvexPointIndex(listOfPoints)
  triangleAreaOfPoint = getTriangleArea(listOfPoints, pointIndex)
  totalArea += triangleAreaOfPoint
  listOfPoints.remove(pointIndex)

我手头没有数学证明，但我很确定任何多边形都是由凸三角形组成的，可以在我描述的方法中找到。

希望这会有所帮助。

推荐阅读