iii. Triangles

Triangle centers and formulas

Centroid, incenter, circumcenter, orthocenter, excenters, area from sides, angles and medians — all $O(1)$, all built from cross, dot and `PD`. Non-degenerate triangles only (collinear input makes several of these divide by zero).

PD centroid(P a, P b, P c) { return (toPD(a) + toPD(b) + toPD(c)) * (1.0 / 3); }
 
PD circumcenter(P a, P b, P c) {
    PD ab = toPD(b - a), ac = toPD(c - a);
    double d = 2 * cross(ab, ac);
    PD o = {ac.y * norm2(ab) - ab.y * norm2(ac), ab.x * norm2(ac) - ac.x * norm2(ab)};
    return toPD(a) + o * (1.0 / d);
}
PD circumcenter(PD a, PD b, PD c) {               // same, when the vertices are already floating (e.g. mid-Welzl)
    PD ab = b - a, ac = c - a;
    double d = 2 * cross(ab, ac);
    PD o = {ac.y * norm2(ab) - ab.y * norm2(ac), ab.x * norm2(ac) - ac.x * norm2(ab)};
    return a + o * (1.0 / d);
}
 
PD orthocenter(P a, P b, P c) {
    PD o = circumcenter(a, b, c);
    return toPD(a) + toPD(b) + toPD(c) - o * 2;
}
 
PD incenter(P a, P b, P c) {
    double la = dist(b, c), lb = dist(a, c), lc = dist(a, b);
    return (toPD(a) * la + toPD(b) * lb + toPD(c) * lc) * (1.0 / (la + lb + lc));
}
 
PD excenter(P a, P b, P c) {               // opposite a
    double la = dist(b, c), lb = dist(a, c), lc = dist(a, b);
    return (toPD(b) * lb + toPD(c) * lc - toPD(a) * la) * (1.0 / (lb + lc - la));
}
 
double inradius(P a, P b, P c) {
    double la = dist(b, c), lb = dist(a, c), lc = dist(a, b);
    return fabs((double)cross(a, b, c)) / (la + lb + lc);
}
 
double circumradius(P a, P b, P c) {
    double la = dist(b, c), lb = dist(a, c), lc = dist(a, b);
    return la * lb * lc / (2 * fabs((double)cross(a, b, c)));
}
 
double heron(double a, double b, double c) {         // area from side lengths, -1 if impossible
    array<double, 3> s = {a, b, c};
    sort(s.rbegin(), s.rend());                       // x >= y >= z
    auto [x, y, z] = s;
    if (z < 0 || x > y + z) return -1;
    return sqrt(max(0.0, (x + (y + z)) * (z - (x - y)) * (z + (x - y)) * (x + (y - z)))) / 4;
}
 
double angleFromSides(double a, double b, double c) {  // angle opposite side a
    return acos(max(-1.0, min(1.0, (b * b + c * c - a * a) / (2 * b * c))));
}
 
double medianLength(double a, double b, double c) {    // median to side a
    return sqrt(max(0.0, 2 * b * b + 2 * c * c - a * a)) / 2;
}

Identity	Statement
Euler line	$O,G,H$ collinear, $H-G=2(G-O)$
Euler’s triangle formula	$O{I}^2=R(R-2r)$ (so always $R\ge 2r$, equality only for equilateral)
Area	$\mathrm{area}=rs=\frac{abc}{4R}$, $s=\frac{a+b+c}{2}$
Incenter	weighted average of vertices by the opposite side lengths

Proof: centroid, orthocenter and the Euler line

Centroid $(A+B+C)/3$ is immediate from the definition (average of the vertices), and it is the common point of the three medians because the median from $A$ meets $BC$ at its midpoint $(B+C)/2$, and $\frac{2}{3}A+\frac{1}{3}\cdot \frac{B+C}{2}\cdot 2\cdot \frac{1}{2}$… more directly: the point $\frac{1}{3}(A+B+C)$ lies on segment from $A$ to $(B+C)/2$ at parameter $t=\frac{2}{3}$ from $A$ (check: $A+\frac{2}{3}(\frac{B+C}{2}-A)=\frac{1}{3}A+\frac{1}{3}B+\frac{1}{3}C$), and symmetrically on the other two medians, so all three medians meet there, at the $2:1$ point from each vertex.

Orthocenter. Place the circumcenter $O$ temporarily at the coordinate origin, so $|A|=|B|=|C|=R$. Let $H^{\prime }=A+B+C$. Then $H^{\prime }-A=B+C$, and $(B+C)\cdot (B-C)=|B{|}^2-|C{|}^2=0$, so $H^{\prime }-A\perp B-C$: the line $A{H}^{\prime }$ is the altitude from $A$. By the same argument for $B$ and $C$, $H^{\prime }$ lies on all three altitudes, so $H^{\prime }$ is the orthocenter. Undoing the shift (origin at $O$) gives $H-O=(A-O)+(B-O)+(C-O)$, i.e. $H=A+B+C-2O$, which is exactly the code above.

Euler line. With $G=(A+B+C)/3$ and $H=A+B+C-2O$: $H-G=(A+B+C)-2O-\frac{1}{3}(A+B+C)=\frac{2}{3}(A+B+C)-2O=2(\frac{1}{3}(A+B+C)-O)=2(G-O)$. In particular $O,G,H$ are collinear (one is an affine combination of the other two along the same line) whenever $O\ne G$. $■$

Proof: inradius, circumradius, Heron, and the incenter weighted average

Inradius. The incircle touches all three sides, so it splits the triangle into three sub-triangles $IAB,IBC,ICA$ each with height $r$ (the inradius) over base $AB,BC,CA$ respectively. Summing their areas: $\mathrm{area}=\frac{1}{2}r(la+lb+lc)=rs$. Solving for $r$ with $\mathrm{area}=\frac{1}{2}|\mathrm{cross}(a,b,c)|$ gives $r=|\mathrm{cross}(a,b,c)|/(la+lb+lc)$, matching the code (the code’s denominator is $la+lb+lc=2s$, and the numerator is $2\cdot \mathrm{area}$, so the factor of 2 cancels).

Circumradius. By the law of sines, $\frac{la}{\sin A}=2R$ for every triangle (standard: inscribe the triangle in its circumcircle, the central angle subtending side $a$ is $2A$ by the inscribed angle theorem, and the chord length is $2R\sin A$). Also $\mathrm{area}=\frac{1}{2}lb\cdot lc\sin A$, so $\sin A=2\cdot \mathrm{area}/(lb\cdot lc)$. Substituting: $2R=la/\sin A=la\cdot lb\cdot lc/(2\cdot \mathrm{area})$, i.e. $R=\frac{la\cdot lb\cdot lc}{4\cdot \mathrm{area}}$, matching the code with $\mathrm{area}=\frac{1}{2}|\mathrm{cross}|$.

Heron. The classical form is ${\mathrm{area}}^2=s(s-a)(s-b)(s-c)$ with $s=(a+b+c)/2$; substituting $s$ and factoring in terms of $a,b,c$ directly (Kahan’s rearrangement, sorting $a\ge b\ge c$ first) gives exactly $16{\mathrm{area}}^2=(a+(b+c))(c-(a-b))(c+(a-b))(a+(b-c))$, algebraically the same product but grouped so that each factor is a sum of non-negative quantities when $a\ge b\ge c$ and the triangle inequality holds — avoiding the catastrophic cancellation that $s-a$, $s-b$, $s-c$ can suffer for needle-shaped triangles. The classical identity itself follows from Heron’s derivation via the law of cosines: $a^2=b^2+c^2-2bc\cos A\Rightarrow \cos A=(b^2+c^2-a^2)/(2bc)$, then $16{\mathrm{area}}^2=16\cdot \frac{1}{4}{b}^2{c}^2{\sin }^{2}A=4b^2{c}^2(1-{\cos }^{2}A)=(2bc-(b^2+c^2-a^2))(2bc+(b^2+c^2-a^2))$, which expands to the same quartic.

Incenter. By the angle bisector theorem, the bisector from $A$ meets $BC$ at the point $D$ with $BD:DC=AB:AC=lc:lb$, i.e. $D=(lb\cdot B+lc\cdot C)/(lb+lc)$. The incenter $I$ lies on $AD$ (it lies on every angle bisector), and by the angle bisector theorem applied in triangle $ABD$ to the bisector from $B$ — or directly by mass-point reasoning, placing mass $la$ at $A$ is inconsistent with the first ratio unless we place mass proportional to the opposite side at each vertex — one checks $I=(la\cdot A+lb\cdot B+lc\cdot C)/(la+lb+lc)$ does lie on segment $AD$: substituting $D$ above, $I=\frac{la}{la+lb+lc}A+\frac{lb+lc}{la+lb+lc}D$, a convex combination of $A$ and $D$, confirming $I\in AD$. The same check on the other two cevians (by the symmetric form of the same expression) confirms $I$ is their common point. $■$

Proof: Euler's triangle formula $O{I}^2=R(R-2r)$

Let $M$ be the second intersection of line $AI$ (the bisector from $A$) with the circumcircle — the midpoint of arc $BC$ not containing $A$. The incenter-excenter lemma: $M$ is equidistant from $B$, $C$, and $I$, i.e. $MI=MB=MC$. (Proof of the lemma: $\angle MBC=\angle MAC=A/2$ since both subtend arc $MC$; and $\angle IBM=\angle IBC+\angle CBM=B/2+A/2$ is the external angle of triangle $IBA$ at… more directly, $\angle BIM$ is an exterior angle of triangle $ABI$ equal to $\angle BAI+\angle ABI=A/2+B/2$, while $\angle IBM=\angle IBC+\angle CBM=B/2+A/2$ using $\angle CBM=\angle CAM=A/2$ (inscribed angle on arc $CM$); so $\angle BIM=\angle IBM$, making triangle $BIM$ isosceles with $MB=MI$, and symmetrically $MC=MI$.)

Now apply the power of the point $I$ with respect to the circumcircle along the chord through $A,I,M$: $\mathrm{pow}(I)=R^2-O{I}^2=-IA\cdot IM$ (negative since $I$ is inside the circle, with the two intersection lengths measured as positive $IA,IM$ on opposite sides… using the signed/unsigned convention $R^2-O{I}^2=IA\cdot IM$ for $I$ inside). So $O{I}^2=R^2-IA\cdot IM$.

Compute $IA=r/\sin (A/2)$ (drop the perpendicular of length $r$ from $I$ to side $AB$; the angle at $A$ in that right triangle is $A/2$). Compute $IM=MB=2R\sin (A/2)$ (chord $MB$ subtends inscribed angle $\angle MAB=A/2$… using $\angle MCB=A/2$ subtending the same arc $MB$, chord $MB=2R\sin (\angle MCB)=2R\sin (A/2)$ by the extended law of sines). Then $IA\cdot IM=\frac{r}{\sin (A/2)}\cdot 2R\sin (A/2)=2Rr$.

Hence $O{I}^2=R^2-2Rr=R(R-2r)$. Since $O{I}^2\ge 0$, this also proves Euler’s inequality $R\ge 2r$, with equality iff $O=I$ iff the triangle is equilateral. $■$

Tested: circumcenter/incenter/centroid/orthocenter coincide for an equilateral triangle; orthocenter satisfies the Euler line relation on 10${}^5$ random triangles; inradius/circumradius satisfy area = inradius * s = circumradius-based abc/(4R) matching the shoelace area; heron matches the shoelace area; medianLength matches the direct distance from a vertex to the opposite midpoint; angleFromSides matches the atan2(|cross|,dot) angle of Primitives; Euler’s formula $O{I}^2=R(R-2r)$ checked numerically on random triangles.