площадь, содержащаяся в кусочно-прямой просто замкнутой кривой

Question

У меня есть точки плоскости pi i = 1, ..., n, и они образуют просто замкнутую, но не обязательно выпуклую кривую. Кривая от pi к p (i + 1) и от pn к p1 - прямая линия. Мне нужен алгоритм для вычисления содержащейся области.

Answer 1

Давайте разберем проблему на гораздо меньшие, поддающиеся решению.

Идея:
Разбейте его на треугольники и просуммируйте их площади. На каждой итерации получите выпуклую точку (по отношению к предыдущей и последующей), получите площадь этого треугольника (area(p(i), p(i-1), p(i+1))) и удалите эту точку из списка соответствующих точек, которые еще предстоит обработать.

На вершине c проверки, находится ли точка внутри выпуклого многоугольника, я предполагаю, что точки движутся по часовой стрелке (в противном случае, поменяйте местами их условие на угол). В основном, учитывая 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)

У меня нет математического доказательства под рукой, но я почти уверен, что если взять любой многоугольник, он состоит из выпуклых треугольников, которые можно найти в описанном мной методе.

Надеюсь, это было полезно.