我正在尝试解决 Exploring Python 一书中的练习。但是，我想我不明白递归的概念。我写了一些递归函数。因此我知道一些方面。但是，我没有足够的经验。我已经停止学习编程大约一年了。

无论如何，让我给你完整的问题:

A polygon can be represented by a list of (x, y) pairs where each pair is a tuple: [ (x1, y1), (x2, y2), (x3, y3) , ... (xn, yn)]. Write a recursive function to compute the area of a polygon. This can be accomplished by “cutting off” a triangle, using the fact that a triangle with corners (x1, y1), (x2, y2), (x3, y3) has area (x1y1 + x2y2 + x3y2 – y1x2 –y2x3 – y3x1) / 2.

尽管问题已经给出了公式，但我使用了另一个公式。因为，我对多边形的面积做了一些研究。如果你看看 here公式不同。

并且逐步描述我的程序会更好，以便解释我想要什么。 好的，我必须声明全局范围，因为递归:

area = 0
x = [0] * 3
y = [0] * 3 

然后，我创建了一个递归函数。结果，此函数始终返回零。所以我真正的问题是:

def areaofpolygon(polygon, i):
    global area, x, y # My variables 
    try: # I prefered using try statement from using if-else statements. So it is the easier I guess.
        x[i], y[i] = polygon[i] # X and Y coordinates from tuple
        area += (x[i]*y[i+1] - x[i+1]*y[i]) #My formula
    except IndexError:
        return area/2
    
    areaofpolygon(polygon, i+1)   # Here, this is my weird recursion

还有我的主要功能:

  def main():
      mypolygon = [(1,2), (2,5), (1,4)] # I declared polygon as tuples
      # I called my function and started to count from zero, and the result will be prompted.
      print(areaofpolygon(mypolygon,0))
        
      return 0
  if __name__ == '__main__':
      main()

这是我没有注释的完整代码:

'''
Created on Feb 24, 2012

@author: msarialp
'''
area = 0
x = [0] * 3
y = [0] * 3
def areaofpolygon(polygon, i):
    global area, x, y
    try:
        x[i], y[i] = polygon[i]
        area += (x[i]*y[i+1] - x[i+1]*y[i])
    except IndexError:
        return area/2
    
    areaofpolygon(polygon, i+1)   
def main():
    mypolygon = [(1,2), (2,5), (1,4)]
    print(areaofpolygon(mypolygon,0))
    
    return 0
if __name__ == '__main__':
    main()

编辑一个

阅读您的回答后，我明白了我的代码出了什么问题。所以我决定分享我程序的最新版本以获得其他帮助。 同样，我必须声明全局变量。我如何从 senderle 应用 ( lop_triangle ) 函数

area = 0
x = [0] * 3
y = [0] * 3

我的函数划分元组并获取 x 和 y 坐标。

def sides_of_polygon(polygon, i):
    global x, y
    try:
        x[i], y[i] = polygon[i]
        return sides_of_polygon(polygon, i+1)
    except IndexError:
        return x, y

我的函数计算多边形的面积(和以前一样)

def area_of_polygon(x, y, i):
    global area
    try:
        area += x[i]*y[i+1] - x[i+1]*y[i]
        return area_of_polygon(x, y, i+1)
    except IndexError:
        return area/2.0

我的主要功能...

def main():
    mypolygon = [(1,2), (2,5), (1,4)]
    dx, dy = sides_of_polygon(mypolygon, 0)
    print(area_of_polygon(dx,dy,0))
    
    return 0
if __name__ == '__main__':
    main()

请在不提供完整解决方案的情况下帮助我改进我的代码。

编辑二

经过与senderle的讨论，我明白了问题出在哪里，senderle的解决方案比我的好，所以我建议你使用它。 无论如何，他帮助我使我的代码正确。我不得不再次更改我的公式。

area += x[i]*y[(i+1) % 3] - x[(i+1) % 3]*y[i]

他还补充说，对于更长的多边形，3 必须是 len(vertices)。 感谢大家的宝贵时间。

最佳答案

递归的本质是这样的:

1. 确定一个简单的基本案例并解决该问题。
2. 构思一个过程，该过程在重复时将更复杂的情况简化为该基本情况。
3. 将 #2 中的过程应用于问题，直到达到基本情况。

对于您的情况，第一步很简单。最小的多边形是三角形。三角形的面积是 (x1y2 + x2y3 + x3y1 – y1x2 –y2x3 – y3x1)/2。 (不过看起来他们在问题中表述错误了……)

第二步也很简单，因为问题陈述给了你:给定一个有 n 个顶点的多边形，砍掉一个三角形，确定它的面积，并将它添加到所得 (n-1)- 的面积中顶点多边形。

我们将把它分解成几个部分。首先，解决 #1 的函数:

def area_of_triangle(points):
    (x1, y1), (x2, y2), (x3, y3) = points
    return abs(x1 * y2 + x2 * y3 + x3 * y1 - y1 * x2 - y2 * x3 - y3 * x1) / 2

简单。现在是解决#2 的函数。我们所需要的只是一个函数，它可以切掉一个三角形并返回它和由此产生的更小的多边形:

def lop_triangle(points):
    triangle = [points[0], points[-1], points[-2]]
    polygon = points[:-1]
    return triangle, polygon

如果不是很明显，这只是使用多边形的第一个和最后两个点创建一个三角形。然后它删除多边形的最后一个点，现在相当于砍掉三角形。 (绘制一个 n 多边形并将其顶点标记为从 0 到 n 以查看它是如何工作的。)现在我们有一个三角形和一个更简单的多边形。

现在，让我们把它们放在一起。这第三步在某些方面是最难的，但是因为我们已经解决了前两个问题，所以第三步更容易理解。

def area_of_polygon(points):
    if len(points) == 3:
        return area_of_triangle(points)
    else:
        triangle, polygon = lop_triangle(points)
        return area_of_triangle(triangle) + area_of_polygon(polygon)

所有的魔法都发生在最后一行。每次 area_of_polygon 获取一个三角形时，它只返回三角形的面积。但是当它得到一个更大的多边形时，它会砍掉一个三角形，取那个三角形的面积，然后把它加到……一个更小的多边形的面积上。所以说多边形有 5 个顶点。第一次 area_of_polygon 被调用 (c1)，它切掉一个三角形，获取它的面积，然后再次调用 area_of_polygon (c2) ，但这次是一个 4 顶点多边形。然后是三角形的 area_of_polygon 圈，并再次调用 area_of_polygon (c3) ，但这次是一个 3 顶点多边形。然后它不必再次调用 area_of_polygon。它只是将三角形的面积返回给之前的调用 (c2)。将结果与 (c2) 中的三角形相加并将该值返回给 (c1)。然后你就有了答案。

另外，就其值(value)而言，wolfram formula可以用三行写得非常清楚:

def area_of_polygon(vertices):
    pairs = zip(vertices, vertices[1:] + vertices[0:1])
    return sum(x1 * y2 - y1 * x2 for (x1, y1), (x2, y2) in pairs) / 2

关于python - 多边形的面积(递归使用 Python)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9447227/