做网站用什么系统,广州兼职做网站,网站文章收录慢,深圳网站设计张兵目录 一、说明二、有序顶点集三、无序顶点集3.1 凸多边形3.2 非凸多边形 四、结论 一、说明 计算多边形面积的方法有很多种。众所周知的多边形#xff08;如三角形、矩形、正方形、梯形等#xff09;的面积可以使用简单的数学公式计算。在这篇文章中#xff0c;我将讨论… 目录 一、说明二、有序顶点集三、无序顶点集3.1 凸多边形3.2 非凸多边形 四、结论 一、说明 计算多边形面积的方法有很多种。众所周知的多边形如三角形、矩形、正方形、梯形等的面积可以使用简单的数学公式计算。在这篇文章中我将讨论如何计算给定顶点集的多边形面积。这里讨论的方法适用于大多数没有孔的多边形。
二、有序顶点集 如果多边形的顶点按顺时针或逆时针方向排列则可以使用鞋带算法计算面积。该公式可以用表达式表示
A 1 2 ∣ ∑ i 1 n − 1 x i y i 1 x n y 1 − ∑ i 1 n − 1 x i 1 y i − x 1 y n ∣ A \frac{1}{2}\left|\sum_{i 1}^{n-1}x_iy_{i1}x_ny_1 - \sum_{i 1}^{n - 1}x_{i 1}y_i - x_1y_n\right| A21 ∑i1n−1xiyi1xny1−∑i1n−1xi1yi−x1yn 使用此公式的唯一条件是顶点必须按顺时针或逆时针方向排序否则面积将不正确。这是该算法的Python实现。
# Shoelace formula to calculate the area of a polygon
# the points must be sorted anticlockwise (or clockwise)def polygon_area(vertices):psum 0nsum 0for i in range(len(vertices)):sindex (i 1) % len(vertices)prod vertices[i].x * vertices[sindex].ypsum prodfor i in range(len(vertices)):sindex (i 1) % len(vertices)prod vertices[sindex].x * vertices[i].ynsum prodreturn abs(1/2*(psum - nsum))列表顶点包含 Point 类型的对象列表。点是表示 2D 平面中的点的数据结构。表示一个点的Python代码是
class Point:def __init__(self, x, y):self.x xself.y ydef __str__(self):return ( str(self.x) , str(self.y) )下面的代码片段测试了上面的代码。
if __name__ __main__:points [Point(0, 0), Point(5, 0), Point(5, 5), Point(0, 5)]print polygon_area(points) # prints 25三、无序顶点集 如果顶点不是顺时针或逆时针排列的那么计算面积可能会有点棘手。这意味着在调用 之前我们需要按顺时针或逆时针polygon_area(points)排序。points为了对顶点进行排序我们需要一个完全位于多边形内部的参考点。有了参考点后我们计算参考点与每个顶点之间的角度并按升序或降序对它们进行排序。现在的问题是我们如何找到参考点呢答案很简单“这取决于多边形的类型”。
3.1 凸多边形 如果多边形是凸多边形即所有内角都小于或等于的多边形18001800多边形内的任何点都可以是给出完全相同面积的参考点即无论参考点位于多边形内的哪个位置面积在所有情况下都是相同的。这是因为参考点的选择不会改变凸多边形的形状。在这种情况下我们可以简单地平均X 和y 坐标来找到参考点。这可以很容易地计算出来如下面的代码所示。
# returns the average x and y coordinates of all the points
def average_point_inside(points):x 0y 0for point in points:x point.xy point.yreturn Point(x / len(points), y / len(points))3.2 非凸多边形 对于非凸多边形参考点的选择会改变多边形的形状因此不同的参考点可能会得到不同的面积。因此如果多边形不是凸多边形那么在顶点未排序的情况下求面积没有任何意义。 一旦我们有了参考点仅对凸多边形有意义我们就可以根据参考点与每个顶点与 x 轴逆时针方向连接的线段所成的角度对所有顶点进行排序如下图所示下面的代码计算参考点和顶点与x轴的连线之间的角度以弧度为单位。
# returns the angle made by a line segment
# connecting p1 and p2 with x-axis in the anticlockwise direction
def angle(p1, p2):k (p2.y - p1.y) / distance(p1, p2)x2 p2.xx1 p1.xif k 0:if x2 x1: # First Quadrantreturn (2.0 * math.pi - math.asin(k))else: # Second Quadrantreturn (math.pi math.asin(k))else:if x2 x1: # Fourth Quadrantreturn math.asin(-k)else: # Third Quadrantreturn (math.pi - math.asin(-k))sorted我们可以使用标准Python库的方法对顶点进行排序。这里的技巧是我们传递根据角度比较点的比较器。
# angularly sort the points anticlockwise
def sort_angular(points, reference_point):return sorted(points, key lambda point: -angle(point, reference_point))现在我们完成了。我们将排序后的点传递到polygon_area给出正确面积的函数中。下面的代码片段测试了上面的代码。
if __name__ __main__:points [Point(0,3), Point(2, 4), Point(3,1), Point(4,3), Point(3, 5), Point(1, 1)]reference_point average_point_inside(points)spoints sort_angular(points, reference_point)print polygon_area(spoints) # prints 9四、结论 在这篇文章中我讨论了如何计算给定一组顶点的面积。如果顶点是有序的则可以使用鞋带公式计算面积。如果顶点没有排序则将顶点排序后即可计算面积只有多边形是凸多边形时才是准确的。如果多边形不是凸的则该方法可能有效也可能无效。最后提供了实现所讨论的所有方法的 python 代码。
