Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Simple math solution in Clear category for Area of a Convex Polygon by macfreek
#!/usr/bin/env python3.3
# -*- coding: utf-8 -*-
"""Given a convex polygon on a coordinate plane, return the area of the polygon.
Input: N coordinates as a list of (x,y) coordinates. Each coordinate contains two integers.
Output: The area of the polygon as a float.
"""
def triangle_area(A, B, C):
"""Given 3 points A, B, C in the cartesian plane, return the area of the triangle."""
return ( (A[0] - B[0]) * (C[1] - A[1]) - (A[0] - C[0]) * (B[1] - A[1]) ) / 2
def checkio(data):
"""Since the polygon is convex, we can bisect it as a series of triangles and use a simple formula for triangle areas. We bisect it using lines between coordinate 0 to coordinate 2, coordinate 0 to coordinate 3, ..., coordinate 0 to coordinate N-1. This creates N-2 triangles."""
assert len(data) >= 3
area = 0.0
A = data[0]
for i in range(1, len(data)-1):
area += triangle_area(A, data[i], data[i+1])
return abs(area)
if __name__ == '__main__':
#This part is using only for self-checking and not necessary for auto-testing
def almost_equal(checked, correct, significant_digits=1):
precision = 0.1 ** significant_digits
return correct - precision < checked < correct + precision
assert almost_equal(checkio([[1, 1], [9, 9], [9, 1]]), 32), "The half of the square"
assert almost_equal(checkio([[4, 10], [7, 1], [1, 4]]), 22.5), "Triangle"
assert almost_equal(checkio([[1, 2], [3, 8], [9, 8], [7, 1]]), 40), "Quadrilateral"
assert almost_equal(checkio([[3, 3], [2, 7], [5, 9], [8, 7], [7, 3]]), 26), "Pentagon"
assert almost_equal(checkio([[7, 2], [3, 2], [1, 5], [3, 9], [7, 9], [9, 6]]), 42), "Hexagon"
assert almost_equal(checkio([[4, 1], [3, 4], [3, 7], [4, 8], [7, 9], [9, 6], [7, 1]]), 35.5), "Heptagon"
April 14, 2014
Comments:
