Recently, I created a [blog entry](http://mirror.codeforces.com/blog/entry/22175) 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](http://www.dummies.com/how-to/content/how-to-find-the-incenter-circumcenter-and-orthocen.html) 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](http://zacharyabel.com/papers/Barycentric_A07.pdf) 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 <u>center of mass</u> 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, angles form 120 degrees↵
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](http://mathworld.wolfram.com/BarycentricCoordinates.html) 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](http://zacharyabel.com/papers/Barycentric_A07.pdf)), 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.
↵
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](http://www.dummies.com/how-to/content/how-to-find-the-incenter-circumcenter-and-orthocen.html) 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](http://zacharyabel.com/papers/Barycentric_A07.pdf) 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 <u>center of mass</u> 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](http://mathworld.wolfram.com/BarycentricCoordinates.html) 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](http://zacharyabel.com/papers/Barycentric_A07.pdf)), 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.
