Welcome, guest | Sign In | My Account | Store | Cart

Area of Polygon using Shoelace formula.

Python, 19 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
# Area of Polygon using Shoelace formula
# http://en.wikipedia.org/wiki/Shoelace_formula
# FB - 20120218
# corners must be ordered in clockwise or counter-clockwise direction
def PolygonArea(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

# examples
corners = [(2.0, 1.0), (4.0, 5.0), (7.0, 8.0)]
print PolygonArea(corners)
corners = [(3.0, 4.0), (5.0, 11.0), (12.0, 8.0), (9.0, 5.0), (5.0, 6.0)]
print PolygonArea(corners)

2 comments

FB36 (author) 12 years ago  # | flag

If the corners of the polygon are not sorted then you can sort them first using this:

# sort corners in counter-clockwise direction
def PolygonSort(corners):
    # calculate centroid of the polygon
    n = len(corners) # of corners
    cx = float(sum(x for x, y in corners)) / n
    cy = float(sum(y for x, y in corners)) / n
    # create a new list of corners which includes angles
    cornersWithAngles = []
    for x, y in corners:
        dx = x - cx
        dy = y - cy
        an = (math.atan2(dy, dx) + 2.0 * math.pi) % (2.0 * math.pi)
        cornersWithAngles.append((dx, dy, an))
    # sort it using the angles
    cornersWithAngles.sort(key = lambda tup: tup[2])
    return cornersWithAngles
FB36 (author) 12 years ago  # | flag

The above function moves the polygon to origin and adds angles to each corner. The area calculated will still be correct (when using PolygonArea(PolygonSort(corners))). But if you like corners to be sorted w/o changing the corners then you can use this one:

# sort corners in counter-clockwise direction
import math
def PolygonSort(corners):
    # calculate centroid of the polygon
    n = len(corners) # of corners
    cx = float(sum(x for x, y in corners)) / n
    cy = float(sum(y for x, y in corners)) / n
    # create a new list of corners which includes angles
    cornersWithAngles = []
    for x, y in corners:
        an = (math.atan2(y - cy, x - cx) + 2.0 * math.pi) % (2.0 * math.pi)
        cornersWithAngles.append((x, y, an))
    # sort it using the angles
    cornersWithAngles.sort(key = lambda tup: tup[2])
    # return the sorted corners w/ angles removed
    return map(lambda (x, y, an): (x, y), cornersWithAngles)
Created by FB36 on Sat, 18 Feb 2012 (MIT)
Python recipes (4591)
FB36's recipes (148)

Required Modules

  • (none specified)

Other Information and Tasks