Hikari9's blog

By Hikari9, history, 6 years ago, In English

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.

UPD2: Pardon for the confusion, I'm still talking about centers of 2D triangles on higher dimensional spaces. The circumcenter code is for the circumcircle, not the circumsphere because there can be many circumspheres if the figure is determined by just 3 points.

 
 
 
 
  • Vote: I like it
  • +114
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Thanks, nice! Theoretically I was aware of barycentrics coordinate but it didn't occur to me that they can be used in geometry problems in competitive programming and that seems pretty useful :).

However I see one issue with comment "// intersection of altitudes, angles form 120 degrees" intersection of altitudes is an orthocenter and point that forms 120 degrees angles is called Fermat's/Toricelli's point and these are two different points (and I don't have time now to check which of them is described by those coordinates).

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh sorry, will edit that! Thanks for pointing that out I somehow confused the two.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Hikari9 (previous revision, new revision, compare).

»
6 years ago, # |
  Vote: I like it +23 Vote: I do not like it

"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."

First sentence is indeed a worth noting observation, however I would differ with second one. Circumcenter code will give circumcenter :P. Those formulas still work in a sense that if we take a plane containing those 3 points and restrict ourselves to it and use those formulas then they will give us points on that plane with desired properties, but they do not generalize in a sense that we can take 4 points creating a tetrahedron and consider points with corresponding properties for tetrahedron. It's very likely that there exists a barycentric formula for center of circumsphere, but generalizing it won't be so straightforward.

What can I say:
1) Centroid generalizes trivially
2) Circumcenter, incenter, excenters — they always exist, however formulas are not generalizing in an easy way (mainly because in 3D we have 6 sides which is larger than numbers of points :P)
3) Orthocenter doesn't have to exist.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Of course, I'm still sticking with triangles, not tetrahedrons. I'm just saying that there is no need to alter the code for higher dimensions, no need to project onto a 2D plane from 3D or 4D before calculations.

    What im saying is we dont need to construct and intersect 3D lines as perpendicular bisectors/angle bisectors/etc. when dealing with higher dimensional triangles.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know that this was what you meant, but you wrote "For example, the circumcenter code will get the center of the circumsphere in 3D space.", however to create a uniquely determined sphere in 3D you need 4 points, not just 3, so that statement doesn't make much sense :P. We can always define something like "smallest circumsphere on 3 points", but that is rather far from standard definition :).

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh, of course! My mistake. Sorry for the confusion.