Centroids and area

There is a really surprising fact about centroids, one I had not known about until this year. The area of a triangle is equal to 1.5 times the distance of centroid to a side times the length of the side. It is not too hard to prove this result.

As I showed before, the area of a triangle is 0.5 (a*d - b*c) where u = (a, b) and v = (c, d) are two vectors that are the triangle's sides. To prove the really surprising fact about the centroid, all that must be shown is that $1.5·||g\perp v||·||v||=0.5·\left(ad-bc\right)$. The vector v is the side, so we need its magnitude; the perpendicular vector is adjusted by the scale factor g so that it is the proper distance from the side v to the centroid.

Finding g takes a little more work. Again as shown before, the vector w to the centroid is (u+v)/3, that is (a+c, b+d)/3. Using the Pythagorean theorem, it is true that ${||w||}^2={||g\perp v||}^2+{||fv||}^2$. One also knows from vector addition that $fv=w+g\perp v$. This allows a substitution for fv: . Therefore, substituting into the Pythagorean theorem yields:

This sets up showing that g = 0 (the trivial solution) or that:

$g=\frac{\left(a+c\right)·d-\left(b+d\right)c}{3\left(c^2+d^2\right)}=\frac{ad-bc}{3\left(c^2+d^2\right)}$

Therefore, our proof is nearly done. Going back to the original statement to prove,

$$\begin{gathered} 1.5·||g\perp v||·||v||=0.5·\left(ad-bc\right)\text{ \\ 1.5·g·c2+d2=0.5·ad-bc \\ 1.5·ad-bc3c2+d2·c2+d2=0.5·ad-bc} \end{gathered}$$

And our work is done.

Centroids

In a beginning geometry course, students can find the centroids of triangles by constructing two or three medians. As an extension, I ask my students to think about finding the centroid of a non-special quadrilateral. Most quickly recognize that medians of a non-special quadrilateral are not concurrent, so that method is out. I offer the suggestion to treat a quadrilateral as two triangles:

A few stall out, but a couple students think to look at the other two triangles.

This method is very intuitive and lends itself immediately to the solution --

-- but this method is not scalable. Go ahead; try it for a pentagon. I dare you!

The key to a scalable method relies in understanding that the first pair of centroids is sufficient to find the center of gravity. The solution must lie on this line:

Furthermore, the center of gravity must be positioned on that line proportionally to the relative areas of the two triangles. If the two triangles are equal in area, it must be the midpoint. In my example, the left triangle has an area of 11 sq. units, and the right triangle has an area of 13 sq. units. Therefore, the center of gravity must be 13/24 of the way from the left triangle's centroid to the right triangle's centroid. In effect, this treats each triangle as a point-mass.

This is a method that will work for pentagons. Here is an example:

The centroids of each triangle are marked. Now all one has to do is use the three point-masses (location and area) and then find their collective center of gravity. Is there a way to do this simply with coordinates? Yes. And it is one of the more surprising results I think I have ever seen.

*   *   *

Let's start with finding the centroid of a triangle. Is there any easy method, using the coordinates, to find it?

The easiest way to find the centroid is by vectors. The centroid is 2/3 of the way from A to D, the midpoint of side BC. That means we need to find 2/3 of vector w and add it to point A. One can show in several different ways that w = 0.5 u + 0.5 v. Using this, one can show that E = u/3 + v/3 + A.

Now it is possible to put everything in coordinates. If $A=(x_1,y_1), B=(x_2, y_2), C=(x_3, y_3)$, then . Thus, the coordinate of E is given by:

$\left(\frac{1}{3}\left(x_2-x_1\right)+\frac{1}{3}\left(x_3-x_1\right)+x_1,\frac{1}{3}\left(y_2-y_1\right)+\frac{1}{3}\left(y_3-y_1\right)+y_1\right)=\left(\frac{x_1+x_2+x_3}{3},\frac{y_1+y_2+y_3}{3}\right)$

It is quite easy to find the centroid of a triangle.

*   *   *

How about area? Is there an easy way to find area using coordinates?

Once easy way to find the area using the coordinates is to think about vectors. Specifically, look at two vectors: u = a, b and v = c, d.

How do we find the shaded area between these two vectors? Copy the two vectors again to make a parallelogram:

Now box it in with a rectangle. The rectangle has an area of (a+c)(b+d). Now label all the other parts in terms of a, b, c, and/or d.

Therefore, the area of the parallelogram is (a+c)(b+d) - 2ad - 2 (0.5 ab) - 2 (0.5 cd), which simplifies down to bc - ad. Thus, the area of the triangle formed by vectors u and v is half the area of the parallelogram. Since we know that $a=x_2-x_1, b=y_2-y_1, c=x_3-x_1, d=y_3-y_1$, we can find the area of the triangle very simply in terms of the coordinates:

$\frac{\left|x_2{y}_1-x_1{y}_2+x_3{y}_2-x_2{y}_3+x_1{y}_3-x_3{y}_1\right|}{2}$

This pattern is remarkable, and it extends to any polygon. For example, try it on a quadrilateral.

Set up the areas for each triangle, and the amazing part is that two terms from the first triangle will cancel out two terms from the second: $x_2{y}_4, x_4{y}_2$. That leaves the area formula:

$\frac{\left|x_2{y}_1-x_1{y}_2+x_3{y}_2-x_2{y}_3+x_4{y}_3-x_3{y}_4+x_4{y}_1-x_1{y}_4\right|}{\mathrm{2 }}$

This formula extends easily to any polygon.

*   *   *

Now we are ready to combine it all together. In overall form, the first step to find the center of gravity of a pentagon is to divide it into three triangles, find the centroid of each, and find the area of each. Given three point-masses, the center of gravity can be found by weighting the triangle centroid formula, like so:

$\left(\frac{a_1{x}_{c1}+a_2{x}_{c2}+a_3{x}_{c3}}{a_1+a_2+a_3}, \frac{a_1{y}_{c1}+a_2{y}_{c2}+a_3{y}_{c3}}{a_1+a_2+a_3}\right)$

Now all that remains is to substitute in.

It is an amazing monstrosity to try to simplify it. I only did the x-coordinate because it takes so much time. Here is the result:

Centroid

It is one of the most surprisingly simple results. This works for a polygon that does not intersect itself, whether it be convex or concave.

I also put together another post on centroids and area.

Two problems in one: density and minimum enclosing circle

I think a lot about density. If there is a relatively homogeneously distributed element in a clearly defined space, density is easy: amount of substance divided by amount of space. But it makes much less sense for a small, discrete set of elements in a poorly defined space. Consider this example of six cities.

There is not a uniform density, but an investigation of local density turns up the question of how to define the boundaries. One possibility is to draw in the perpendicular bisectors, like so:

The polygons indicate all the places in the space which are closest to each point. (This is a Voronoi diagram.) The numbers indicate the areas of each polygon. To the good, the polygon around D is the largest, reflecting that D is the least dense. On the other hand, neither E nor F is given "credit" for how close they are to each other. I think density at a point ought to be more influenced by the local density than by the global density -- small, isolated, dense clusters ought to be given a rating of "relatively dense." So for that reason, I abandoned areas. How one draws them makes an enormous difference, and the above scheme is the only non-arbitrary way I can see to draw them -- and it does not work.

That is why I started thinking about distances. The density at a point ought to be inversely proportional to the "average" distance a traveler must go to get to any other point, weighted more heavily for the shorter distances. This makes a lot of sense to me. A neighborhood is dense if a resident can walk to many shops, restaurants, and parks, even if it is a small, isolated pocket of the city; a neighborhood is relatively dense if a resident can drive less than 5 minutes to many shops, restaurants, and parks; and a neighborhood is not dense if the closest shops, restaurants, and parks are not close at all. Therefore, we must weight the closest amenities more heavily in the average, like this:

where d_ i_ j is the distance between two points, and p is a function based inversely on distance. I do not believe it works if p is a linear function, so I tried this for p:

where k is any number greater than the maximum length in the whole set. This formula results in very, very heavily weighting the shortest distance. A lot of other formulas could be used for p that do not weight the shortest distance quite so heavily. Here is what the results look like (avg. distances in blue, some actual path lengths marked in black):

A and B are the most dense (close proximity to each other), followed by E and F (again, local density), then largely trailed by D, and even farther, C. One surprising result is that A, which is farther from D, E, and F, and closer only to C, has a lower average distance than B. One way to think about it is that the farther distances of D, E, and F mean that A's average is more influenced by B's proximity (higher distances push down p, so that these longer distances count for very little in the average). In real terms, this might mean that someone living in city A is less likely to travel to cities D, E, and F than someone living in city B -- thus, city A's residents have a lower overall average trip. Another way to think about it is that, under this measure, density is increased by isolation: the self-contained bubble. If two small cities had equal density, but one was in the orbit of a major city, which is less dense? The orbit city residents are more likely to venture into the major city, so perhaps this should count as less dense. An interesting question is whether a function p can be created which does not have this effect.

* * *

Another, seemingly dissimilar problem, is finding a minimum enclosing circle for a set of points. The minimum enclosing circle (MEC) is the smallest-area circle, and by definition, it must go through either three of the points (forming an acute triangle) or two (on the diameter of the circle). There are a lot of algorithms to find the MEC, but here is one I have not seen written up before.

To start, find the centroid of the points (merely average the x-coordinates, and then the y-coordinates, to find the x- and y-coordinate of the centroid, respectively), like so:

Next, compare the distances from each point to the centroid:

Point F is the farthest (and is definitely on the MEC). So, move the centroid closer to F by weighting F more heavily in the centroid calculation (ah, this is why it was in the same post). Here is the centroid's movement:

It turns out that F only needs to go up to a weight of 1.7 before C is now the farthest point from the adjusted centroid (and therefore, C is definitely on the MEC). So, move the centroid closer to C. In this case, it takes only a slight tweak to C before A, C, and F are equidistant from the adjusted centroid (so now, these are the three points on the MEC, and the adjusted centroid is its center). However, in other cases, it takes a lot of bouncing back and forth between C and F until a third point ties. In essence, bouncing back and forth between C and F moves the adjusted centroid along the perpendicular bisector of C and F toward the midpoint of C and F:

Of course, the centroid does not have to reach the midpoint; it only needs to approach the midpoint until a third point is equidistant (in this case, point A). And here is the minimum enclosing circle:

It works.