What Is a Centroid?

The centroid is a geometric holding of a shape, somewhat related to the center of mass. Information technology is the point denoted (x̄, ȳ) that is the average of all points in the shape. For example, in a rectangle the average of all points in the shape is dead center, equally shown in Figure 1 below.

Figure 1, the centroid of a rectangle

Figure ane. The average position of all points, or centroid, of a rectangle is precisely in the center of the shape.

The centroid can be used every bit the center of mass if we assume the mass of the shape to be evenly spread throughout. With this definition, the centroid is the point at which you could residuum the shape on the tip of a pencil. If the centroid is not within the shape, every bit in Effigy 2 below, so information technology is non possible to remainder the shape in such a way.

Figure 2, the centroid of a crescent moon

Figure 2. The centroid of a crescent is not within the bounds of the shape, and then there is no point on which it can be counterbalanced.

Complex shapes can be broken down into simpler component shapes to make calculations easier. For example, nosotros don't know intuitively how to summate the centroid of the shape shown in Figure 3 below, but nosotros have a formula for its rectangular pieces. The centroid of the overall shape is the weighted average of the centroids of its constituent parts. In precise terms, if we divide a shape into n regions with areas Aone, Atwo, ..., An and centroids (x̄1, ȳ1), (x̄2, ȳtwo), ..., (x̄n, ȳn), the centroid of the original shape would exist:

Summation notation for the centroid

Applying these equations to the T shape in Effigy 3 below, we can summate the location of the overall centroid as:

Formula for the centroid of the T shape in Figure 3

Figure 3, finding the centroid of a complex shape.

Effigy 3. We tin find the centroid of a complex shape by taking the weighted boilerplate of the centroids of its constituent pieces.

Why Is This Useful?

Our goal hither is to notice the centroid of any polygon by using a simple algorithm. This is useful because nosotros tin can extend it to include shapes with curved edges, every bit in Figure four below. The centroid of a shape with smooth curved edges can be approximated past replacing the curve with a segmented approximation. We did something similar already in the crescent of Figure 2 above.

Figure 4, approximating curves with segmentation

Figure four. The curved shape on the left higher up can exist approximated by replacing its curved edges with straight line segments, forming a polygon as shown on the right. We tin and so estimate the centroid of the resulting polygon.

The centroid is also useful when yous need to get the middle of mass for an object of uniform mass distribution. This comes in handy for all sorts of things, from implementing physics in a computer game to calculating the maximum expected stress on an I-beam.

The only caveat with our algorithm is that the polygon must be non-intersecting. This is oft the case, every bit a self-intersecting polygon doesn't model a physical object in the real world.

What Is a Not-Intersecting Polygon?

In this context, we will define a not-intersecting polygon to be a polygon in which no two edges intersect with each other. The shapes that nosotros typically consider such every bit rectangles, triangles, trapezoids, etc. are all non-intersecting. We define a self-intersecting polygon to be a shape in which at least 2 edges intersect with each other, such as the hourglass shape in Figure 5 below.

Figure 5, a self-intersecting polygon

Figure 5. The hourglass shape to a higher place is self-intersecting, and using it as input to our algorithm will yield incorrect results.

The Algorithm

The polygon that we use as input to the algorithm we will denote every bit the ordered gear up of vertices P = { v1, v2, ..., vnorth }.

Getting the Area and Centroid of a Triangle

The footing of our algorithm will rest upon the assumption that we know how to get the area and centroid of a triangle, given the coordinates for its iii vertices. Given a triangle ABC, we can calculate the components of ii vectors AB and AC, as shown in Effigy half dozen below.

Figure 6, turning a triangle into vectors.

Effigy 6. Going from a triangle to a pair of vectors.

Past taking the cantankerous product of the 2 vectors, Air-conditioning × AB, we get a resulting vector that has the magnitude of the area of the parallelogram that is spanned by AB and BC. By cutting this area in half, we go but the area of the triangle ABC. This is shown in Figure seven below.

Figure 7, turning vectors into the area of the triangle.

Figure 7. Going from a pair of vectors back to the expanse of the triangle.

Considering of the right-hand dominion, taking the cross product Air conditioning × AB gives united states a positive result if the triangle ABC is right-handed (its vertices are clockwise) and gives us a negative result if it is left-handed (its vertices are counterclockwise). However, this signed area volition turn out to be necessary for our algorithm. Working out the algebra results in the following airtight formula for the signed area of triangle ABC:

Formula for the signed area of a triangle ABC

Side by side we take to discover the centroid of the triangle. We volition use simple geometry to find a closed formula, although information technology is possible to use an algebraic argument besides. If we split up triangle ABC into n dissever strips with edges parallel to side BC as shown on the left in Figure 8 below, we tin can employ the weighted boilerplate of their centroids every bit the overall centroid of the triangle. As north becomes large, the strips go very sparse, and their centroids arroyo the midpoint of their two endpoints. For the longest strip, this centroid is the midpoint of points B and C. The centroids for the other strips all follow a straight line from the midpoint of side BC through point A. Whatever weighted average of these points must likewise lie along the straight line they make.

We can brand a similar argument using n strips parallel to side AB or AC to show that the centroid of the triangle must lie on the line between the midpoint of side AB and point C equally well every bit the line between the B and the midpoint of side Air conditioning and betoken B. The only way for the centroid to lie on all three of these lines at once is if it is located at their intersection.

Figure 8, geometric proof that the centroid of a triangle must be located at the intersection of lines from a vertex to the midpoint of the opposite edge.

Figure 8. On the left we have the triangle ABC divide into strips parallel to side BC, with centroids that course a straight line from the midpoint of BC to betoken A. The correct side shows the location of the triangle'south centroid, which is at the intersection of all three such lines.

At present that we know where the centroid of a triangle is geometrically, how do we summate information technology numerically from the coordinates of its vertices? Annotation that when we take the average of three vertices A, B, C, we can start by taking the average of any pair of the vertices to get a midpoint Chiliad. We tin then boilerplate the remaining vertex with M, which must event in a point on the line between M and the remaining vertex. Since we tin choose any ii vertices for M, the boilerplate of A, B, C must be on the line betwixt A and the midpoint of BC, the line betwixt B and the midpoint of AC, and the line between C and the midpoint of AB. Therefore the average of the vertices A, B, C is precisely the centroid of the triangle ABC, every bit shown on the right in Figure 8 in a higher place. This gives us the following closed formula:

Formula for the centroid of triangle ABC

Splitting the Polygon Into Triangles

Since we accept a mode to calculate the area and centroid of a triangle, and nosotros have a way to calculate the centroid of a complex shape given the areas and centroids of its component parts, the next logical step is to split the polygon P into triangles. We do this by taking any three consecutive vertices A = vi , B = fivei+1 , C = vi+2 in P and forming a triangle ABC. The situation so far is shown in Figure 9 below.

Figure 9, creating a triangle from three consecutive vertices.

Figure ix. The two possible scenarios when forming a triangle from iii consecutive vertices. Either the triangle is function of the polygon P as shown on the left, or information technology is empty space as shown on the right.

The algorithm keeps a running count Atotal of the total area of P and a running average (x̄total, ȳtotal) of the centroid calculated and so far. We add together each triangle ABC's area to Afull and average its centroid into (x̄total, ȳtotal). Next we remove the vertex B from P , forming the smaller polygon P' = P – { B }.

If the triangle ABC is part of the polygon P as on the left in Effigy ix, then ABC volition be right-handed and its area will exist positive. Removing B removes ABC's area from ***P'***, so ABC's expanse and centroid volition count positively toward Atotal and (x̄full, ȳfull) overall. On the other manus, if the triangle ABC is empty infinite as on the correct in Figure ix, and so ABC will exist left-handed and its expanse volition be negative. All the same, removing B adds ABC's surface area to ***P'***, and so ABC'south area and centroid volition count positively toward the totals due to another triangle in ***P'***. Since ABC counts negatively toward Atotal and (x̄total, ȳtotal) and and then positively, it makes no impact overall. This is what nosotros expect, as in this case ABC is empty space. The result of removing vertex B is shown in Figure 10 beneath.

Figure 10, removing vertex B from the polygon.

Figure ten. The result of removing vertex B from the polygon P is shown above, both in the case where ABC is part of P (left) and in the example where ABC is empty space (right).

We proceed in this fashion, setting P equal to ***P'***, and removing a vertex each time until P' has less than 3 vertices and thus can't form a triangle. So Atotal and (x̄total, ȳtotal) are the overall signed area and centroid of the original polygon P .

Runtime Analysis

The polygon begins with n vertices, and with each iteration of the algorithm it removes a vertex. Since it terminates when the polygon has less than 3 remaining vertices, it runs for a maximum of due north – 2 = O(n) steps. With each stride, we have to calculate the signed area and centroid of a triangle and average them into the running total for the polygon. These calculations have a constant amount of fourth dimension, so overall the algorithm runs in O(northward) time. This means the amount of steps the algorithm has to have increases linearly with the number of vertices in the polygon.

However, if we wanted to cheque the polygons to make sure that they were non-intersecting before running the algorithm, we would have to cheque every border against every other border. This would increase the run fourth dimension of the algorithm to O(n 2). For polygons with a large number of vertices, checking for self-intersection would dramatically increase the number of steps in the algorithm.

Python Implementation

The post-obit is an implementation of the algorithm in Python. Given a listing of three or more points, it returns the centroid of the polygon that they form.