Two-liners for triangle centers using Barycentric coordinates

Правка en6, от Hikari9, 2015-12-24 01:43:04

Recently, I created a blog entry about using C++ std::complex as an alternative to points for computational geometry. We will now apply this technique for more geometry for C++!

Triangle centers are important for they create a connection between triangles, circles, and angles in geometric construction. But the classical way to determine them is a little hassle to either derive, or code.

For example, we can get the circumcenter by constructing two perpendicular bisectors and intersecting them. Math for dummies provides a brief explanation of some triangle center formulae if you want to know what I'm talking about.

But can we generalize the way to get ALL kinds of triangle centers?

Barycentric Coordinates

Barycentric coordinates uses a kind of coordinate system through three vertices of the triangle as basis. Basically, a coordinate has three real numbers (a, b, c) determining the "weight" of the vertex at vertices (A, B, C) respectively. This paper provides a well-formed definition of the Barycentric coordinates.

Barycentric points can be determined using the formula (A*a + B*b + C*c) / (a + b + c). You might relate this formula to the center of mass or the weighted average of three objects in space in physics. In addition, you can observe that (a, b, c) == (k*a, k*b, k*c), meaning, a coordinate is not unique when mapped from a point.

The Bary Function

We need to have a function that converts Barycentric coordinates to Cartesian points. Well, the formula is rather straightforward so it's rather easy. Since std::complex allows us vector addition and scalar multiplication, it's a 1-liner. Remember, we're using complex numbers so don't forget to typedef std::complex<double> point.

point bary(point A, point B, point C, double a, double b, double c) {
    return (A*a + B*b + C*c) / (a + b + c);
}

Triangle Centers

How can we get the triangle centers from Barycentric coordinates? Here's the cheat sheet.

point centroid(point A, point B, point C) {
    // geometric center of mass
    return bary(A, B, C, 1, 1, 1);
}

point circumcenter(point A, point B, point C) {
    // intersection of perpendicular bisectors
    double a = norm(B - C), b = norm(C - A), c = norm(A - B);
    return bary(A, B, C, a*(b+c-a), b*(c+a-b), c*(a+b-c));
}

point incenter(point A, point B, point C) {
    // intersection of internal angle bisectors
    return bary(A, B, C, abs(B-C), abs(A-C), abs(A-B));
}

point orthocenter(point A, point B, point C) {
    // intersection of altitudes
    double a = norm(B - C), b = norm(C - A), c = norm(A - B);
    return bary(A, B, C, (a+b-c)*(c+a-b), (b+c-a)*(a+b-c), (c+a-b)*(b+c-a));
}

point excenter(point A, point B, point C) {
    // intersection of two external angle bisectors
    double a = abs(B - C), b = abs(A - C), c = abs(A - B);
    return bary(A, B, C, -a, b, c);

    //// NOTE: there are three excenters
    // return bary(A, B, C, a, -b, c);
    // return bary(A, B, C, a, b, -c);
}

Getting diabetes from the syntax sugar? I hope you did. If you want to know how it works, Wolfram-alpha provides a brief summary and some equations for each triangle center. The site also provides other centers I did not mention here, such as the Symmedian point.

For the proofs, some of them are straightforward. For example, for the centroid, you just need to show that if a = b = c = 1, then (A*a + B*b + C*c) / (a + b + c) == (A + B + C) / 3. The other triangle centers, however, have rather extensive proofs (e.g. orthocenter proof), so I suggest that you just look up papers online on your own.

You might also want to see Silvester's book "Geometry — Ancient & Modern" for he also showed useful theorems built around Barycentric coordinates, though it's not available online so you should buy it in a bookstore. If you also found some research papers that look useful, I would also like to know.

UPD: These formulas work in 3D and higher dimensions as well! For example, the circumcenter code will get the center of the circumsphere in 3D space.

Теги triangles, geometry, barycenter, centroid, incenter, circumcenter, orthocenter, excenter

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский Hikari9 2015-12-30 20:24:59 282 Fixed mistake on circumsphere concept
en6 Английский Hikari9 2015-12-24 01:43:04 157 Added 3D comment.
en5 Английский Hikari9 2015-12-21 17:11:26 25 Tiny change: ' altitudes, angles form 120 degrees\n do' -> ' altitudes\n do'
en4 Английский Hikari9 2015-12-20 17:08:37 3 Tiny change: 'just look it up papers' -> 'just look up papers'
en3 Английский Hikari9 2015-12-20 17:06:51 1279 Grammar edits.
en2 Английский Hikari9 2015-12-20 07:24:15 39
en1 Английский Hikari9 2015-12-20 07:13:27 4272 Initial revision (published)