多边形区域(递归使用Python)

Question

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

无论如何,让我给你一个完整的问题:

多边形可以由(x,y)对列表表示,其中每对是元组:[(x1,y1),(x2,y2),(x3,y3),...(xn,yn)] .编写递归函数来计算多边形的面积.这可以通过"切断"三角形来实现,使用具有角(x1,y1),(x2,y2),(x3,y3)的三角形具有面积(x1y1 + x2y2 + x3y2-y1x2-y2x3)的事实. y3x1)/ 2.

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

一步一步地描述我的程序会更好,以便解释我想要的东西.好的,我必须声明全局范围,因为递归:

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讨论之后,我明白了问题在哪里,发送者的解决方案比我的更好,所以我建议你应该使用它.无论如何,他帮助我使我的代码正确.我不得不再次更改我的公式.

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

他还添加了更长的多边形3必须是len(顶点).谢谢大家的时间.

Answer 1

你的公式的实施是有缺陷的.它展望了尚未设置的x,y列表中的值(x[i]*y[i+1] - x[i+1]*y[i])

如果你在try-except块中放置一个print语句,你会看到你只是乘以零并得到零区域:

try:
    x[i], y[i] = polygon[i]
    area += (x[i]*y[i+1] - x[i+1]*y[i])
    print x[i], y[i+1], x[i+1], y[i]
except IndexError, e:
    return area/2

#1 0 0 2
#2 0 0 5

此外,您没有将递归调用的结果返回到areaofpolygon,因此您永远不会得到它area/2.你想要:return areaofpolygon(polygon, i+1).并确保你实际上除以2.0,以便你得到浮点精度,因为你的积分是整数.

尝试使用您找到的公式或另一个问题中建议的公式.

更新

以下是您的代码的固定版本:

#!/usr/bin/env python

from random import randint
from shapely.geometry import Polygon

area = 0

def areaofpolygon(polygon, i):
    global area
    if i == 0: 
        area = 0

    try:
        x1, y1 = polygon[i]
        x2, y2 = polygon[i+1]
        area += (x1*y2) - (x2*y1)

    except IndexError, e:
        x1, y1 = polygon[0]
        x2, y2 = polygon[-1]
        area += (x2*y1) - (x1*y2)
        return abs(area/2.0)

    return areaofpolygon(polygon, i+1)   

def main():
    mypolygon = [(randint(0, 100), randint(0, 100)) for _ in xrange(10)]
    print mypolygon

    area = areaofpolygon(mypolygon, 0)
    assert area == Polygon(mypolygon).area

    print "Test passed."
    return 0

if __name__ == '__main__':
    main()

### Output ###
$ ./test.py 
[(29, 76), (85, 49), (27, 80), (94, 98), (19, 1), (75, 6), (55, 38), (74, 62), (0, 25), (93, 94)]
Test passed.
$ ./test.py 
[(13, 37), (98, 74), (42, 58), (32, 64), (95, 97), (34, 62), (34, 59), (21, 76), (55, 32), (76, 31)]
Test passed.
$ ./test.py 
[(38, 67), (66, 59), (16, 71), (53, 100), (64, 52), (69, 31), (45, 23), (52, 37), (27, 21), (42, 74)]
Test passed.

请注意,您不需要全局x,y列表.你也错过了使用最后一点和第一点的等式的最后一部分.

Answer 2

递归的本质如下:

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顶点多边形.然后砍掉一个三角形,再次调用(c3),但这次使用3顶点多边形.然后它不必再次打电话.它只是将三角形区域返回到前一个调用(c2).将结果与(c2)中的三角形相加,并将该值返回到(c1).然后你有答案.area_of_polygonarea_of_polygonarea_of_polygon

此外,对于它的价值,wolfram公式可以非常清晰地写成三行:

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