The Shoelace formula (also called Gauss's area formula) is a convenient method to calculate the area of a simple polygon (one that does not intersect itself) when you know the coordinates of its vertices.
If a polygon has $n$ vertices $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$, listed in order (clockwise or counterclockwise), then the area $A$ is: $$ A = \frac{1}{2} \left| \sum_{i=1}^{n} (x_i y_{i+1} - x_{i+1} y_i) \right| $$ where $(x_{n+1}, y_{n+1}) = (x_1, y_1)$ - that is, the first vertex is repeated at the end to "close the loop".
The following Python script defines a class that computes the area of a polygon using the Shoelace formula and checks whether the polygon is convex.
class Polygon:
def __init__(self, vertices):
self.vertices = vertices
def get_area(self):
# Initializations
area = 0.0
n = len(self.vertices)
j = n - 1
for i in range(0, n):
area += (self.vertices[j][0] + self.vertices[i][0]) * \
(self.vertices[j][1] - self.vertices[i][1])
j = i # set j to the previous vertex
return abs(0.5 * area)
def is_convex(self):
# Initializations
N = len(self.vertices) # Stores count of edges in polygon
prev = 0 # Stores direction of cross product of previous traversed edges
cur = 0 # Stores direction of cross product of current traversed edges
for i in range(N):
# Stores three adjacent edges of the polygon
temp = [self.vertices[i], self.vertices[(i + 1) % N], self.vertices[(i + 2) % N]]
cur = self.cross_product(temp)
if (cur != 0):
# If direction of cross product of all adjacent edges are not same
if (cur * prev < 0):
return False
else:
prev = cur
return True
def cross_product(self, a):
x1 = (a[1][0] - a[0][0]) # Stores abscissas of vector a[1] ---> a[0]
y1 = (a[1][1] - a[0][1]) # Stores ordinates of vector a[1] ---> a[0]
x2 = (a[2][0] - a[0][0]) # Stores abscissas of vector a[2] ---> a[0]
y2 = (a[2][1] - a[0][1]) # Stores ordinates of vector a[2] ---> a[0]
# Return cross product
return (x1 * y2 - y1 * x2)
if __name__ == "__main__":
vertices1 = [[1, 6], [3, 1], [7, 2], [2, 4], [8, 5]]
polygon1 = Polygon(vertices1)
print(polygon1.get_area())
print(polygon1.is_convex())
vertices2 = [[4, 10], [9, 7], [11, 2], [2, 2]]
polygon2 = Polygon(vertices2)
print(polygon2.get_area())
print(polygon2.is_convex())