# Centroid of Convex Polygons

In many games, the game objects interact with each other and very often it is important to detect when game objects collide with others, for example when a missile hits a target. A first and rather easy method to detect such collisions is to *inscribe* the polygon inside a sphere, or a circle in 2D.

To compute the radius of the circle, it is possible to take the distance from the center of the polygon to each vertex and to then average those values, or to simply take the smallest or the largest one, depending on what should be achieved. An often used heuristic is to take a value between the largest possible radius and the average of the radii.

This actually basic idea thus already leads to two mathematical problems that need to be solved: First, the centroid, or the geometrical centre, of a polygon must be found and then, the distance between the centroid and different vertices must be computed (fast!).

The following tutorial explains how to compute the centroid of a convex polygon.

Before tackling the task of computing the centroid of a polygon, it is wise to have a look at the better known problem of computing the centroid of a triangle.

## The Barycentre

Most high school students learn how to compute the coordinates of the centroid of a triangle, also called the barycentre of a triangle. The barycentre is the intersection point of the three lines going through one of the vertices and the middle of the opposite edge of the triangle (as seen in the figure above — the point G is the barycentre of the triangle).

In the language of linear algebra, the coordinates of the barycentre

In affine geometry, the above formula can be written as

## Uniform Distribution of Mass

Unfortunately, computing the centroid of a polygon isn’t just as easy as computing the barycentre of a triangle; in the case of a polygon simply averaging over the coordinates of the vertices no longer results in the correct coordinates of the centroid — the only exception being regular polygons. While the centroid of a polygon is indeed its centre of mass, the mass of a polygon is uniformly distributed over its entire surface, not only at the vertices. Note that for simple shapes, such as triangles, rectangles, or the above-mentioned regular polygons, the mass being evenly distributed over the surface is equivalent to the mass being at the vertices only.

In the case of a convex polygon, it is easy enough to see, however, how triangulating the polygon will lead to a formula for its centroid.

## The Area of a Triangle

As the mass is distributed over the entire surface of the polygon, it is necessary to compute the area of the triangles resulting from the triangulation. As above, let

## Convex and Closed

With the knowledge we just gathered, we can now tackle the problem of computing the centroid of a convex and closed polygon. Thus let

## Triangle Centroids

As seen above, to compute the centroid and area of a triangle in vector notation, the vectors between a fixed vertex,

## Triangle Areas

Let us denote the areas of the triangles with a lower

The name *weight* is well suited as, as visualized in the figure below, the area of the triangle measures how much of the entire mass of the polygon is contained in the triangle, thus by how much the barycentre of that triangle influences the location of the centroid of the polygon. Think of an election: the more inhabitants in a region, the more delegates that region sends to the central government, the more influence it has on global politics.

## Centroid of the Polygon

To now finally compute the coordinates of the centroid *weighted* centroids of the triangles by the total area of the polygon:

or, using coordinates in Euclidean space:

Note that these formulas are correct, even if the vertices are not given in counter-clockwise order: The determinants might become negative, but the computed coordinates will be correct.

Obviously, the formula to calculate the centroid of a polygon contains the case of the barycentre of a triangle, as in the case of

## Source Code

In C++, the discussed ideas translate to the following code:

## Examples

As a first example, consider the three points

Clearly, the above formula leads to the same result:

For a more complicated example, let

To compute the centroid *weights*:

## Formula to remember

In later tutorials, we will learn how to detect collisions between games objects. To do so, we must find the centre of the game objects, which are often given as convex polygons (think of aircraft, for example). Thus, the important thing to remember from this tutorial is the following formula to compute the centroid of a convex polygon: