# Algorithms - Right Triangular Irregular Network

May 25, 2020

## Right-triangulated irregular networks

The numerical simulations we use are executed on triangular meshes or multidimensional arrays (aka “raster” or “texture” data). For optimizing visualization and on-the-fly calculations in the browser we instead use specialized meshes like the right-triangulated irregular network (RTIN).

This is a hierarchal data structure for representing a regular rectilinear grid as a triangulation. For the purposes of visualization, the height values at the grid points are assumed to be exactly correct.

This is a form of multi-resolution surface rendering which forms right isosceles triangles from a subset of the points. Multiple partitioning schemes within the representation allow for changing the resultion dynamically.

The algorithm to decompose a square into triangles is:

- first divide along NW-SE
- form partitions by splitting triangles larger than the minimum size
- split T from right angle to midpoint of hypoenuse
- if edge point causes neighbor (R) to become a quad, propagate
- if equal size stop, else if R larger continue to propagate

This is also called a `4*8^2`

Laves net. Laves nets are tessellation methods where every subdivision has a similar shape. The numbers are the maximum splits that occur along each side of the reference shape. Squares are `4^4`

, 30-60-90 triangles are `4.6.12`

and equilateral triangles are `6^3`

.

Squares and equilateral triangles cannot form a continuous non-uniform partition, because any split with recursively divide all cells. The `4.8^2`

will change at most 2 of each size triangle, while `4.6.12`

change 12 or fewer of each equal and larger size.

In practice, this is implemented as a binary tree, with triangles as leaves. The root node is the square. Each half of a split polygon is labelled `left`

/`right`

according to the side of splitting ray that it is on.

Splits are from the hypotenuse to the `right`

vertex. From a parent ordered counter clockwise with the right-angled vertex labeleld v_3, the `left`

partition is (v_3, v_1, m), and `right`

is (v_2, v_3, m)