Area of a polygon given a set of points

Introduction

There are many ways to calculate the area of a polygon. Area of a well-known polygon like Triangles, Rectangles, Squares, Trapezoids, etc. can be calculated using simple mathematical formula. In this post, I talk how to calculate the area of a polygon given the set of vertices. The method discussed here is applicable for most of the polygons without holes.

Set of ordered vertices

If the vertices of a polygon are ordered in a clockwise or an anti-clockwise direction, then the area can be calculated using a shoelace algorithm. The formula can be represented by the expression
$$A = \frac{1}{2}\left|\sum_{i = 1}^{n-1}x_iy_{i+1}+x_ny_1 - \sum_{i = 1}^{n - 1}x_{i + 1}y_i - x_1y_n\right|$$
The only condition to use this formula is that the vertices must be ordered in clockwise or anti-clockwise direction otherwise the area would be incorrect. Here is the python implementation of the algorithm.

# Shoelace formula to calculate the area of a polygon
# the points must be sorted anticlockwise (or clockwise)
def polygon_area(vertices):
    psum = 0
    nsum = 0

    for i in range(len(vertices)):
        sindex = (i + 1) % len(vertices)
        prod = vertices[i].x * vertices[sindex].y
        psum += prod

    for i in range(len(vertices)):
        sindex = (i + 1) % len(vertices)
        prod = vertices[sindex].x * vertices[i].y
        nsum += prod

    return abs(1/2*(psum - nsum))

The list vertices contain a list of object of type Point. Point is a data structure that represents a point in a 2D plane. A python code to represent a point would be

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __str__(self):
        return '(' + str(self.x) + ', ' + str(self.y) + ')'

The following code snippet tests the above code.

1
2
3

if __name__ == '__main__':
    points = [Point(0, 0), Point(5, 0), Point(5, 5), Point(0, 5)]
    print polygon_area(points) # prints 25

Set of unordered vertices

If the vertices are not ordered clockwise or anti-clockwise, then calculating the area can be a little tricky. That means, before calling the polygon_area(points) , we need to sort the points clockwise or anti-clockwise. To sort the vertices, we need a reference point that lies completely inside the polygon. After we have a reference point, then we calculate the angle between the reference point and each of the vertices and sort them in increasing or decreasing order. Now the question is, how do we find the reference point? the answer is simple ‘that depends on the type of the polygon’.

Convex Polygon
If the polygon is convex polygon i.e. a polygon whose all interior angles are less than or equal to $180^0$, any point inside the polygon can be a reference point that gives the exact same area i.e. no matter where the reference point is inside the polygon, the area is same in all cases. This is because the choice of a reference point doesn’t alter the shape of a convex polygon. In this case, we can simply average the $x$ and $y$ coordinates to find the reference point. This can be easily calculated as shown in the code below.

# returns the average x and y coordinates of all the points
def average_point_inside(points):
    x = 0
    y = 0
    for point in points:
        x += point.x
        y += point.y
    return Point(x / len(points), y / len(points))

Non-convex polygon
In the case of a non-convex polygon, the choice of reference point alters the shape of the polygon and therefore we may get different areas for different reference points. Therefore, if the polygon is not a convex polygon then finding the area if the vertices are not ordered does not make any sense.

Once we have a reference point (which make sense only for the convex polygon), we can then sort all the vertices based on the angle made by a line segment joining the reference point and each vertex with x-axis in an anti-clockwise direction as shown in the figure below

The following code calculates the angle (in radian) between the line joining the reference point and a vertex with the x-axis.

# 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.x
    x1 = p1.x

    if k >= 0:
        if x2 >= x1: # First Quadrant
            return (2.0 * math.pi - math.asin(k))
        else: # Second Quadrant
            return (math.pi + math.asin(k))
    else:
        if x2 >= x1: # Fourth Quadrant
            return math.asin(-k)
        else: # Third Quadrant
            return (math.pi - math.asin(-k))

We can sort the vertices using the sorted method of the standard python library. The trick here is we pass the comparator that compares the point based on the angle.

1
2
3

# angularly sort the points anticlockwise
def sort_angular(points, reference_point):
    return sorted(points, key = lambda point: -angle(point, reference_point))

Now we are done. We pass the sorted points in the polygon_area function that gives the correct area. The code snippet below test the codes above.

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

Conclusion

In this article, I talked about how to calculate the area given a set of vertices. If the vertices are ordered, the area can be calculated using the shoelace formula. If the vertices are not ordered, then the area can be calculated after sorting the vertices which are accurate only if the polygon is convex. If the polygon is not convex, the method may or may not work. Finally, python code is provided that implements all the methods discussed.

References

Shoelace formula. (n.d.). Retrieved August 20, 2018, from https://en.wikipedia.org/wiki/Shoelace_formula
“How to sort vertices of a polygon in counter-clockwise order?”: Computing Angle? (n.d.). Retrieved August 20, 2018, from https://math.stackexchange.com/questions/1329128/how-to-sort-vertices-of-a-polygon-in-counter-clockwise-order-computing-angle?noredirect=1&lq=1