Barycentric point location, affine interpolation, and nearest-site queries

Let $T$ be a nondegenerate triangle with ordered vertices $p_0,p_1,p_2\in {\mathbb{D}}^2$. For $x\in {\mathbb{R}}^2$, its barycentric coordinates are the unique scalars ${\lambda }_0,{\lambda }_1,{\lambda }_2$ satisfying ${\sum }_i{\lambda }_i=1$ and $x={\sum }_i{\lambda }_i{p}_i$. They are exact for dyadic $x$: they are obtained by solving the invertible $2\times 2$ system with columns $p_1-p_0,p_2-p_0$. The point is in $T$ exactly when all ${\lambda }_i\ge 0$.

Given vertex data $f_0,f_1,f_2\in \mathbb{R}$, the barycentric affine interpolant on $T$ is $I_{T}f(x)={\sum }_i{\lambda }_i{f}_i$. A point-location result is a containing triangle of the triangulation, with a shared-edge or shared-vertex result allowed when the point lies on a face; outside the convex hull its status is outside-hull and no containing triangle is returned.

For a nonempty finite unweighted indexed site set $P$, the nearest-site query returns a site minimizing $\mathrm{\parallel }x-p{\mathrm{\parallel }}^2$, breaking ties by the least stable identifier. Its hull status is inside-hull for $x\in \mathrm{conv}P$ and outside-hull otherwise. The minimizer is returned in either case.