多边形的面积(使用 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(vertices).感谢大家的时间.
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屋！
