Skip to content

Instantly share code, notes, and snippets.

@rfotino
Last active August 7, 2019 10:41
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save rfotino/a0fa1ef2882484e2da89 to your computer and use it in GitHub Desktop.
Calculates the centroid of a non-intersecting polygon.
def get_centroid(poly):
"""Calculates the centroid of a non-intersecting polygon.
Args:
poly: a list of points, each of which is a list of the form [x, y].
Returns:
the centroid of the polygon in the form [x, y].
Raises:
ValueError: if poly has less than 3 points or the points are not
formatted correctly.
"""
# Make sure poly is formatted correctly
if len(poly) < 3:
raise ValueError('polygon has less than 3 points')
for point in poly:
if type(point) is not list or 2 != len(point):
raise ValueError('point is not a list of length 2')
# Calculate the centroid from the weighted average of the polygon's
# constituent triangles
area_total = 0
centroid_total = [float(poly[0][0]), float(poly[0][1])]
for i in xrange(0, len(poly) - 2):
# Get points for triangle ABC
a, b, c = poly[0], poly[i+1], poly[i+2]
# Calculate the signed area of triangle ABC
area = ((a[0] * (b[1] - c[1])) +
(b[0] * (c[1] - a[1])) +
(c[0] * (a[1] - b[1]))) / 2.0;
# If the area is zero, the triangle's line segments are
# colinear so we should skip it
if 0 == area:
continue
# The centroid of the triangle ABC is the average of its three
# vertices
centroid = [(a[0] + b[0] + c[0]) / 3.0, (a[1] + b[1] + c[1]) / 3.0]
# Add triangle ABC's area and centroid to the weighted average
centroid_total[0] = ((area_total * centroid_total[0]) +
(area * centroid[0])) / (area_total + area)
centroid_total[1] = ((area_total * centroid_total[1]) +
(area * centroid[1])) / (area_total + area)
area_total += area
return centroid_total
@valentinoPereira
Copy link

valentinoPereira commented Aug 7, 2019

I'm getting centrol_total [nan, nan] for some polygons.. What to do?

Note: The Red big dots are the centroid.

Working
image

Not working
image

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment