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 of a triangle , where , and are three non-aligned points in , can easily be computed as follows: , as indeed is the barycentre of the triangle, if, and only if, .

In affine geometry, the above formula can be written as . As an example, let , and be three points in the plane, then the barycentre of the triangle is .

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 be a triangle, then the well-known formula, , for the area of the triangle, where is the length of the base of the triangle and its height, can be reformulated in the language of affine geometry using the determinant function: . Note that the choice of and is irrelevant, the formula holds for any two points, i.e. let and be two vectors defining two sides of the triangle, then . Using, once again, the example from above, the area of the triangle is .

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 be a convex and closed polygon defined by its vertices , , …, , noted in a counter-clockwise order, simple to make sure that the determinant computed for the area of a triangle is positive, and thus being able to omit the use of the absolute value.

Triangle Centroids

As seen above, to compute the centroid and area of a triangle in vector notation, the vectors between a fixed vertex, , for convenience, and the other vertices of the triangle are needed. Thus let , for , , … be those vectors between and the other vertices. After triangulation, there are adjacent triangles with centroids , for , , …, .

Triangle Areas

Let us denote the areas of the triangles with a lower , for weight. In vector notation, the weight of the triangles resulting from the triangulation are , , , …, . The total area of the polygon is thus .

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 of the polygon , it is thus sufficient to divide the sum of the weighted centroids of the triangles by the total area of the polygon: . To resemble the formula for the barycentre of a triangle in affine space, the above formula can be rewritten as follows:

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 the formula reads: .

Source Code

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

void Geometry::computeCentroid(const std::vector<D2D1_POINT_2F>& vertices, D2D1_POINT_2F* centroid)
{
  float centroidX = 0, centroidY = 0;
  float det = 0, tempDet = 0;
  unsigned int j = 0;
  unsigned int nVertices = (unsigned int)vertices.size();

  for (unsigned int i = 0; i < nVertices; i++)
  {
    // closed polygon
    if (i + 1 == nVertices)
      j = 0;
    else
      j = i + 1;

    // compute the determinant
    tempDet = vertices[i].x * vertices[j].y - vertices[j].x*vertices[i].y;
    det += tempDet;

    centroidX += (vertices[i].x + vertices[j].x)*tempDet;
    centroidY += (vertices[i].y + vertices[j].y)*tempDet;
  }

  // divide by the total mass of the polygon
  centroidX /= 3*det;
  centroidY /= 3*det;

  centroid->x = centroidX;
  centroid->y = centroidY;
}

Examples

As a first example, consider the three points , and in the Euclidean plane, then the barycentre of the triangle is the point :

Clearly, the above formula leads to the same result: , or in coordinate form: .

For a more complicated example, let , , , and be five points in the Euclidean plane and the polygon defined by those five points:

To compute the centroid using the coordinates of the five vertices, it is a good idea to first compute the weights: , , , and . The -coordinate of the centroid can now be computed as follows: . The -coordinate of the centroid can be computed equivalently: . Thus, the centroid of the above polygon is .

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:

References

• Calculating the area and centroid of a polygon by Paul Bourke
• Geogebra
• Wikipedia