Hyperbolic Triangles

Useful Facts for Implementing Intrinsic Hyperbolic Edge Flips

Horocycle Distances

Ideal Triangles


Poincaré Disk

Klein Disk

$\ell_1$:   $\ell_2$:   $\ell_3$:

Coordinate Transformations


To Poincaré: $(x, y) \mapsto \left(\displaystyle\frac{2x}{x^2 + (1+y)^2}, \displaystyle\frac{x^2+y^2-1}{x^2 + (1+y)^2}\right)$
To Klein: $(x, y) \mapsto \left(\displaystyle\frac{2x}{1 + x^2 + y^2}, \displaystyle\frac{x^2 + y^2 - 1}{x^2 + y^2 + 1}\right)$


To Halfspace: $(x, y) \mapsto \left(\displaystyle\frac{2x}{x^2 + (1-y)^2}, \displaystyle\frac{1 - x^2 - y^2}{x^2 + (1-y)^2}\right)$
To Klein: $(x, y) \mapsto \left(\displaystyle\frac {2x}{1 + x^2 + y^2}, \displaystyle\frac {2y}{1 + x^2 + y^2}\right)$


To Halfspace: $(x, y) \mapsto \left(\displaystyle\frac{x}{1-y}, \displaystyle\frac{\sqrt{1-x^2-y^2}}{1 - y}\right)$
To Poincaré: $(x, y) \mapsto \left(\displaystyle\frac {x}{1 + \sqrt{ 1 - x^2 - y^2}}, \displaystyle\frac {y}{1 + \sqrt{1 - x^2 - y^2}}\right)$
Poincaré <-> Halfspace maps are standardized to fix $(\pm1, 0)$ and send the north pole to $\infty$ (also sends $(0, 0)$ to $(0, 1)$)



\[h = \text{base distance} \tfrac{\ell_2 \ell_3}{\ell_1}.\]
The (Euclidean) horocycle height $h$ is given by the above equation since the length, $\alpha$, along the horocycle satisfies equations $\alpha := e^{\frac 12 (\lambda_1 - \lambda_2 - \lambda_3)}$ and $\frac{\text{base distance}} h = \alpha$.

Why do the horocycles line up?

Two adjacent ideal hyperbolic triangles in the halfspace model.

For convenience, we'll continue working in the halfspace model. Consider these two ideal triangles. We assign horocycles to the vertices of each triangle so that the triangles have the desired edge lengths. But a priori, there's no reason that the triangles have to pick the same horocycle for their shared vertices. One could imagine a scenario like the one pictured, where we pick different horocycles for the shared vertices.

It turns out that the two triangles must agree on the horocycles picked for their shared vertices. First, we can always standardize the triangles so that one has vertices at $0$, $1$, and $\infty$. We will call the position of the final vertex of the second triangle $w$.

From earlier, we know that the horocycles must have lengths $\alpha = e^{\frac 12 (\lambda_a - \lambda_b - \lambda_c)}$ and $\beta = e^{\frac 12 (\lambda_d - \lambda_b - \lambda_e)}$. Since we can also write $\alpha$ as $\int_0^1 \frac 1y dx$, this means that the right horocycle must be at height $e^{-\frac12(\lambda_a - \lambda_b - \lambda_c)}$. Similarly, the left hococyle must be at height $|w| e^{-\frac 12(\lambda_d - \lambda_b - \lambda_e)}$.

What would have to be true for these heights to be equal? We would need \[e^{-\frac 12(\lambda_a - \lambda_b - \lambda_c)} = |w| e^{-\frac 12(\lambda_d - \lambda_b - \lambda_e)}.\] Separating terms, this is equivalent to requiring that \[|w|= e^{\frac 12(\lambda_d - \lambda_e + \lambda_b - \lambda_a)} = \text{length cross ratio}.\] Recall that the complex cross ratio of four points is precisely where the fourth one goes when the first 3 are sent to $0$, $1$, and $\infty$. Thus $|w|$ is precisely our length cross ratio!

Hyperbolic Delaunay Triangulations

Horocyclic Arcs

A horocyclic arc α opposite edge l1 and adjacent to edges l2 and l3.
The horocyclic arc has hyperbolic length \[\alpha = \frac{\ell_1}{\ell_2 \ell_3},\] where $\ell_i$ are the euclidean lengths of the triangle's edges.

Hyperbolic Delaunay Condition

Two adjacent triangles with shared horocyclic arcs β, β', γ, γ', and opposite holocyclic arcs α and α'.

The hyperbolic local Delaunay condition is \[\alpha + \alpha' \leq \beta + \beta' + \gamma + \gamma'.\] We flip if this is not true.

Equivalently, we can require that \[\beta + \beta' + \gamma + \gamma' - \alpha - \alpha' \geq 0.\]

Hyperbolic Delaunay Flips

Two adjacent triangles with shared horocyclic arcs β, β', γ, γ', and opposite holocyclic arcs α and α'.

The Ptolemy flip formula is \[\ell_f = \frac{\ell_a \ell_c + \ell_b \ell_d}{\ell_e} \]

Iterating Around Vertices

Two adjacent triangles with shared horocyclic arcs β, β', γ, γ', and opposite holocyclic arcs α and α'.

Random Formulas

Houdini halfedges are oriented clockwise, but geometry-central halfedges are oriented counterclockwise

Cross-Ratio preserving point

cocircular triangle diagram

Suppose we are given triangle $B$ and we want to find $v_3$ so that the two triangles have a desired cross-ratio $\mathfrak c$. By some theorem, we know that $\delta = \pi - \gamma$, so $\delta$ is fixed. Now, the law of cosines tells us that $x^2 + y^2 - 2xy \cos \delta = d^2$. Combining this with the constraint that $\frac {xv}{yu} = \mathfrak c$, we can solve in Mathematica to find that the (positive) solution is given by \[\begin{aligned} x &= \frac{\mathfrak c d u}{\sqrt{\mathfrak c ^2 u^2 + v^2 - 2 \mathfrak c u v \cos\delta}} \\ y &= \frac{d v}{\sqrt{\mathfrak c ^2 u^2 + v^2 - 2 \mathfrak c u v \cos\delta}} \end{aligned}\] The other solution is given by negating both $x$ and $y$.

Initially, I was concerned that I might find the edge lengths corresponding to placing the new vertex in the wrong half of the circle. But it turns out that I won't. The angle between the two edges on the side I want is $\delta$, whereas the angle between the two edges on the other side is $\gamma$. So as long as $\gamma \neq \delta$ (i.e. $\gamma \neq \frac\pi2$), I'm fine. But if $\gamma = \frac\pi2$, then I have a slight problem. But it's not too bad.

Now, the law of sines tells us that $\frac{\sin \delta}d = \frac{\sin \phi} y$. Now we know $\phi, \alpha$ and $x$, so we can compute the position $v_3$. Note that in this picture, it looks like the angle between the line $\overline{v_2v_3}$ and the horizontal is $-(\alpha - \phi)$, but in some orientations we need to add $\phi$ instead. We solve this in the code by trying both and picking the one that works. Also, in the code $\alpha$ is a signed angle, so the expressions that we try are actually $\alpha \pm \phi$. This also helps resolve the ambiguity of the $\gamma = \frac \pi2$ case. In this case, the $\pm$ ambiguity corresponds exactly to the two choices of where to place our point. So if both choices are valid, then we just pick the choice which is farther from the base point.

Scale Factors

cocircular triangle diagram
We want to find scale factors $\varphi_i$ such that $\ell_{de} = \varphi_1\varphi_2 \ell_{ab}$ etc. Note that $\varphi_1\varphi_2 = \frac{\ell_{de}}{\ell_{ab}}$, etc. Let $c_{12} := \varphi_1\varphi_2 = \frac{\ell_{de}}{\ell_{ab}}$. Then \[\varphi_1 = \frac{c_{12} c_{31}} {c_{23}}\]

Ptolemy Flips

cocircular triangle diagram

Tracing across faces

cocircular triangle diagram

Barycentric Coordinate Convention

On a halfedge $ab$, the barycentric coordinate $t$ indicates the point $ta + (1-t)b$.