Two-liners for triangle centers using Barycentric coordinates
Разница между en4 и en5, 25 символ(ов) изменены
Recently, I created a [blog entry](http://codeforces.me/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 &mdash; 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.

История

 
 
 
 
Правки
 
 
  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)