Calculates the centroid of a non-intersecting polygon.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I'm getting centrol_total
[nan, nan]
for some polygons.. What to do?Note: The Red big dots are the centroid.
Working
Not working