Calculate area of polygon given (x,y) coordinates

PythonCoordinatesPolygonArea

Python Problem Overview


I have a set of points and would like to know if there is a function (for the sake of convenience and probably speed) that can calculate the area enclosed by a set of points.

for example:

x = np.arange(0,1,0.001)
y = np.sqrt(1-x**2)

points = zip(x,y)

given points the area should be approximately equal to (pi-2)/4. Maybe there is something from scipy, matplotlib, numpy, shapely, etc. to do this? I won't be encountering any negative values for either the x or y coordinates... and they will be polygons without any defined function.

EDIT:

points will most likely not be in any specified order (clockwise or counterclockwise) and may be quite complex as they are a set of utm coordinates from a shapefile under a set of boundaries

Python Solutions


Solution 1 - Python

Implementation of Shoelace formula could be done in Numpy. Assuming these vertices:

import numpy as np
x = np.arange(0,1,0.001)
y = np.sqrt(1-x**2)

We can redefine the function in numpy to find the area:

def PolyArea(x,y):
    return 0.5*np.abs(np.dot(x,np.roll(y,1))-np.dot(y,np.roll(x,1)))

And getting results:

print PolyArea(x,y)
# 0.26353377782163534

Avoiding for loop makes this function ~50X faster than PolygonArea:

%timeit PolyArea(x,y)
# 10000 loops, best of 3: 42 µs per loop
%timeit PolygonArea(zip(x,y))
# 100 loops, best of 3: 2.09 ms per loop.

Timing is done in Jupyter notebook.

Solution 2 - Python

The most optimized solution that covers all possible cases, would be to use a geometry package, like shapely, scikit-geometry or pygeos. All of them use C++ geometry packages under the hood. The first one is easy to install via pip:

pip install shapely

and simple to use:

from shapely.geometry import Polygon
pgon = Polygon(zip(x, y)) # Assuming the OP's x,y coordinates

print(pgon.area)

To build it from scratch or understand how the underlying algorithm works, check the shoelace formula:

# e.g. corners = [(2.0, 1.0), (4.0, 5.0), (7.0, 8.0)]
def Area(corners):
    n = len(corners) # of corners
    area = 0.0
    for i in range(n):
        j = (i + 1) % n
        area += corners[i][0] * corners[j][1]
        area -= corners[j][0] * corners[i][1]
    area = abs(area) / 2.0
    return area

Since this works for simple polygons:

  • If you have a polygon with holes : Calculate the area of the outer ring and subtrack the areas of the inner rings

  • If you have self-intersecting rings : You have to decompose them into simple sectors

Solution 3 - Python

By analysis of Mahdi's answer, I concluded that the majority of time was spent doing np.roll(). By removing the need of the roll, and still using numpy, I got the execution time down to 4-5µs per loop compared to Mahdi's 41µs (for comparison Mahdi's function took an average of 37µs on my machine).

def polygon_area(x,y):
	correction = x[-1] * y[0] - y[-1]* x[0]
	main_area = np.dot(x[:-1], y[1:]) - np.dot(y[:-1], x[1:])
	return 0.5*np.abs(main_area + correction)

By calculating the correctional term, and then slicing the arrays, there is no need to roll or create a new array.

Benchmarks:

10000 iterations
PolyArea(x,y): 37.075µs per loop
polygon_area(x,y): 4.665µs per loop

Timing was done using the time module and time.clock()

Solution 4 - Python

maxb's answer gives good performance but can easily lead to loss of precision when coordinate values or the number of points are large. This can be mitigated with a simple coordinate shift:

def polygon_area(x,y):
    # coordinate shift
    x_ = x - x.mean()
    y_ = y - y.mean()
    # everything else is the same as maxb's code
    correction = x_[-1] * y_[0] - y_[-1]* x_[0]
    main_area = np.dot(x_[:-1], y_[1:]) - np.dot(y_[:-1], x_[1:])
    return 0.5*np.abs(main_area + correction)

For example, a common geographic reference system is UTM, which might have (x,y) coordinates of (488685.984, 7133035.984). The product of those two values is 3485814708748.448. You can see that this single product is already at the edge of precision (it has the same number of decimal places as the inputs). Adding just a few of these products, let alone thousands, will result in loss of precision.

A simple way to mitigate this is to shift the polygon from large positive coordinates to something closer to (0,0), for example by subtracting the centroid as in the code above. This helps in two ways:

  1. It eliminates a factor of x.mean() * y.mean() from each product
  2. It produces a mix of positive and negative values within each dot product, which will largely cancel.

The coordinate shift does not alter the total area, it just makes the calculation more numerically stable.

Solution 5 - Python

cv2.contourArea() in OpenCV gives an alternative method.

example:

points = np.array([[0,0],[10,0],[10,10],[0,10]])
area = cv2.contourArea(points)
print(area) # 100.0

The argument (points, in the above example) is a numpy array with dtype int, representing the vertices of a polygon: [[x1,y1],[x2,y2], ...]

Solution 6 - Python

There's an error in the code above as it doesn't take absolute values on each iteration. The above code will always return zero. (Mathematically, it's the difference between taking signed area or wedge product and the actual area http://en.wikipedia.org/wiki/Exterior_algebra.) Here's some alternate code.

def area(vertices):
    n = len(vertices) # of corners
    a = 0.0
    for i in range(n):
        j = (i + 1) % n
        a += abs(vertices[i][0] * vertices[j][1]-vertices[j][0] * vertices[i][1])
    result = a / 2.0
    return result

Solution 7 - Python

a bit late here, but have you considered simply using sympy?

a simple code is :

from sympy import Polygon
a = Polygon((0, 0), (2, 0), (2, 2), (0, 2)).area
print(a)

Solution 8 - Python

It's faster to use shapely.geometry.Polygon rather than to calculate yourself.

from shapely.geometry import Polygon
import numpy as np
def PolyArea(x,y):
    return 0.5*np.abs(np.dot(x,np.roll(y,1))-np.dot(y,np.roll(x,1)))
coords = np.random.rand(6, 2)
x, y = coords[:, 0], coords[:, 1]

With those codes, and do %timeit

%timeit PolyArea(x,y)
46.4 µs ± 2.24 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
%timeit Polygon(coords).area
20.2 µs ± 414 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Solution 9 - Python

I compared every solutions offered here to Shapely's area method result, they had the right integer part but the decimal numbers differed. Only @Trenton's solution provided the the correct result.

Now improving on @Trenton's answer to process coordinates as a list of tuples, I came up with the following:

import numpy as np

def polygon_area(coords):
    # get x and y in vectors
    x = [point[0] for point in coords]
    y = [point[1] for point in coords]
    # shift coordinates
    x_ = x - np.mean(x)
    y_ = y - np.mean(y)
    # calculate area
    correction = x_[-1] * y_[0] - y_[-1] * x_[0]
    main_area = np.dot(x_[:-1], y_[1:]) - np.dot(y_[:-1], x_[1:])
    return 0.5 * np.abs(main_area + correction)

#### Example output
coords = [(385495.19520441635, 6466826.196947694), (385496.1951836388, 6466826.196947694), (385496.1951836388, 6466825.196929455), (385495.19520441635, 6466825.196929455), (385495.19520441635, 6466826.196947694)]

Shapely's area method:  0.9999974610685296
@Trenton's area method: 0.9999974610685296

Solution 10 - Python

This is much simpler, for regular polygons:

import math

def area_polygon(n, s):
    return 0.25 * n * s**2 / math.tan(math.pi/n)

since the formula is ¼ n s2 / tan(π/n). Given the number of sides, n, and the length of each side, s

Solution 11 - Python

Based on

https://www.mathsisfun.com/geometry/area-irregular-polygons.html

def _area_(coords):
    t=0
    for count in range(len(coords)-1):
        y = coords[count+1][1] + coords[count][1]
        x = coords[count+1][0] - coords[count][0]
        z = y * x
        t += z
    return abs(t/2.0)

a=[(5.09,5.8), (1.68,4.9), (1.48,1.38), (4.76,0.1), (7.0,2.83), (5.09,5.8)]
print _area_(a)

The trick is that the first coordinate should also be last.

Solution 12 - Python

def find_int_coordinates(n: int, coords: list[list[int]]) -> float:
    rez = 0
    x, y = coords[n - 1]
    for coord in coords:
        rez += (x + coord[0]) * (y - coord[1])
        x, y = coord
    return abs(rez / 2)

Attributions

All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
QuestionpbreachView Question on Stackoverflow
Solution 1 - PythonMahdiView Answer on Stackoverflow
Solution 2 - PythonNikos AthanasiouView Answer on Stackoverflow
Solution 3 - PythonmaxbView Answer on Stackoverflow
Solution 4 - PythonTrentonView Answer on Stackoverflow
Solution 5 - PythonToru KikuchiView Answer on Stackoverflow
Solution 6 - PythonChris JudgeView Answer on Stackoverflow
Solution 7 - PythonAlex JiangView Answer on Stackoverflow
Solution 8 - PythonC.K.View Answer on Stackoverflow
Solution 9 - PythonHumbleBeeView Answer on Stackoverflow
Solution 10 - PythonBizarreView Answer on Stackoverflow
Solution 11 - PythonTakis TsiberisView Answer on Stackoverflow
Solution 12 - PythonAliView Answer on Stackoverflow