多边形的区域(递归使用Python) [英] Area of a polygon (Recursively using Python)
问题描述
我正在尝试探索Python"一书中的一个练习.但是，我想我不理解递归的概念.我已经写了一些递归函数.因此，我知道一些方面.但是，我没有足够的经验.而且我已经停止学习编程大约一年了.
I'm trying a solve an exercise from Exploring Python book. But, I guess I don't understand concept of the recursion. I've written some Recursively function. Therefore I know some of the aspects. But, I don't have enough experience. And I've stopped to study programming about one year.
无论如何，让我给你一个完整的问题:
Anyway, let me give you the full question:
一个多边形可以由(x，y)对的列表表示，其中每对 是一个元组:[(x1，y1)，(x2，y2)，(x3，y3)，...(xn，yn)].写一个 递归函数来计算多边形的面积.这可以是 通过切除"一个三角形来完成，使用以下事实: 角为(x1，y1)，(x2，y2)，(x3，y3)的三角形的面积为(x1y1 + x2y2 + x3y2 – y1x2 –y2x3 – y3x1)/2.
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.
尽管这个问题已经给出了公式，但我还是使用了另一个公式.因为，我对多边形的面积进行了一些研究.而且，如果您在此处查看，则公式会有所不同.
Despite the fact that, the question already gave the formula, I used another formula. Because, I made some research about area of a polygon. And if you look at here the formula is different.
逐步解释我的程序会更好，以便解释我想要的内容. 好的，由于递归，我不得不声明全局范围:
And describing my program step by step would be better, in order to explain what I want. OK, I had to declare global scopes, because of recursion:
area = 0
x = [0] * 3
y = [0] * 3
然后，我创建了一个递归函数.结果，此函数始终返回零.所以我真正的问题是:
And then, I created a recursively function. Zero is always returned by this function as a result. So my real problem is this:
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()
这是我的完整代码，没有注释:
And here is my full code without comments:
'''
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)函数
After reading your answers, I've understood what was wrong with my code. So I decided to share last version of my program in order to get some other helps. Again, I had to declare global variables. How can I apply ( lop_triangle ) function from senderle
area = 0
x = [0] * 3
y = [0] * 3
我的函数，用于除以元组并获取x和y坐标.
My function that divides tuple and to get x and y coordinates.
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
我的函数计算多边形的面积(与之前相同)
My function calculate area of polygon( Same as before )
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()
请帮助我改进代码而不提供完整的解决方案.
Please help me to improve my code without giving full solution.
编辑两个
与senderle讨论之后，我了解了问题所在，并且senderle的解决方案比我的解决方案要好，因此我建议您使用它. 无论如何，他帮助我使代码正确无误，而且我不得不再次更改公式.
After making discussion with senderle, I understood where is the problem and senderle's solution is better than mine so I suggest that you should use it. Anyway, He helped me to make my code correct.And I had to change my formula again.
area += x[i]*y[(i+1) % 3] - x[(i+1) % 3]*y[i]
他还为更长的多边形添加了3必须是len(顶点). 谢谢大家的时间.
He also added for longer polygons 3 must be len(vertices). Thanks everyone for their time.
推荐答案
递归的实质如下:
- 确定一个简单的基本案例并为此解决.
- 设想一个过程，当重复执行该过程时，会将更复杂的情况减少为该基本情况.
- 将#2中的过程应用于该问题，直到达到基本情况为止.
对于您而言，第一步很容易.最小的多边形是三角形.三角形的面积为(x1y2 + x2y3 + x3y1 – y1x2 –y2x3 – y3x1) / 2. (看起来他们好像在问题中错了了……)
In your case, the first step is easy. The smallest polygon is a triangle. The area of a triangle is (x1y2 + x2y3 + x3y1 – y1x2 –y2x3 – y3x1) / 2. (It looks like they misstated it in the problem though...)
第二步也很容易，因为问题陈述可以为您提供:给定n个顶点多边形，倾斜一个三角形，确定其面积，然后将其添加到结果(n-1)的面积中-顶点多边形.
The second step is also easy, because the problem statement gives it to you: given an n-vertex polygon, lop off a triangle, determine its area, and add it to the area of the resulting (n-1)-vertex polygon.
我们将其分为几部分.首先，要解决#1的函数:
We'll break it down into parts. First, a function to solve #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的函数.我们需要的是一个倾斜三角形的函数，然后将其返回并返回较小的多边形:
Easy. Now a function to solve #2. All we need is a function that lops off a triangle and returns both it and the resulting smaller polygon:
def lop_triangle(points):
triangle = [points[0], points[-1], points[-2]]
polygon = points[:-1]
return triangle, polygon
如果不明显，则仅使用多边形的前两个点创建一个三角形.然后，它删除多边形的最后一点，现在这相当于切掉三角形. (绘制一个n多边形，并将其顶点标记为0到n，以查看其工作原理.)因此，现在我们有了一个三角形和一个更简单的多边形.
If it's not obvious, this simply creates a triangle using the first and the last two points of the polygon. Then it removes the last point of the polygon, which is now equivalent to chopping off the triangle. (Draw a n-polygon and label its vertices from 0 to n to see how it works.) So now we have a triangle and a simpler polygon.
现在，让我们把它们放在一起.第三步在某些方面是最难的，但是因为我们已经解决了前两个问题，所以第三步更容易理解.
Now, let's put it all together. This third step is in some ways the hardest, but because we solved the first two problems already, the third is easier to understand.
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).然后您有答案.
All the magic happens in that last line. Every time area_of_polygon gets a triangle, it just returns the area of a triangle. But when it gets a larger polygon, it lops off a triangle, takes the area of that triangle, and adds it to... the area of a smaller polygon. So say the polygon has 5 vertices. The first time area_of_polygon is called (c1), it lops off a triangle, takes its area, and then calls area_of_polygon (c2) again, but this time with a 4-vertex polygon. Then area_of_polygon lops of a triangle, and calls area_of_polygon (c3) again, but this time with a 3-vertex polygon. And then it doesn't have to call area_of_polygon again. It just returns the area of a triangle to the previous call (c2). That sums the result with the triangle in (c2) and returns that value to (c1). And then you have your answer.
对于它的价值， wolfram公式可以很清楚地写成三个行:
Also, for what it's worth, the wolfram formula can be written with great clarity in three lines:
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)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
