Кратко — метод и связь с задачами минимизации.
1) Барицентрические координаты.
- Пусть вершины тетраэдра $A_1,A_2,A_3,A_4$, объём тетраэдра $V$. Для точки $P$ внутри существуют невырожденные barycentric-координаты ${\lambda }_i\ge 0,{\sum }_{i=1}^4{\lambda }_i=1$ такие, что
$$P=\sum _{i=1}^4{\lambda }_i{A}_i.$$ - Эти координаты можно получить либо решив систему линейных уравнений по координатам, либо через отношения объёмов
$${\lambda }_i=\frac{V(P,A_1,\dots ,A_i,\dots ,A_4)}{V},$$ где числитель — объём тетраэдра, в котором $A_i$ заменён на $P$.
2) Расстояния до граней через барицентрические координаты.
- Обозначим грань, противоположную $A_i$, как $F_i$, её площадь $S_i$ и высоту (расстояние вершины $A_i$ до $F_i$) как $h_i$. Тогда
$$V=\frac{1}{3}{S}_i{h}_i,V_i=\frac{1}{3}{S}_i{d}_i,$$ где $V_i$ — объём тетраэдра с вершиной $P$ и основанием $F_i$, а $d_i$ — искомое расстояние от $P$ до $F_i$. Из ${\lambda }_i=V_i/V$ следует простая формула
$$d_i={\lambda }_i{h}_i.$$ - Альтернативно, $h_i=\frac{3V}{S_i}$, поэтому
$$d_i={\lambda }_i\frac{3V}{S_i}.$$ (Для точки внутри все ${\lambda }_i>0$ и все $d_i>0$.)
3) Вычислительные шаги (рекомендуемая процедура).
- Найти $V$ (например через смешанное произведение векторов) и площади граней $S_i$.
- Найти ${\lambda }_i$ (либо через объёмы с точкой $P$, либо решить систему $P=\sum {\lambda }_i{A}_i,\sum {\lambda }_i=1$).
- Вычислить $d_i={\lambda }_i{h}_i$ или $d_i={\lambda }_i\frac{3V}{S_i}$.
4) Связь с задачами минимизации сумм взвешенных расстояний.
- Пусть нужно минимизировать функция
$$f(P)=\sum _{i=1}^4{w}_i{d}_i,$$ где $w_i\ge 0$ — веса. Подставляя $d_i={\lambda }_i{h}_i$ получаем линейную функцию по барицентрическим координатам:
$$f(P)=\sum _{i=1}^4(w_i{h}_i){\lambda }_i.$$ Так как множество допустимых $\lambda$ — симплекс $\{{\lambda }_i\ge 0,\sum {\lambda }_i=1\}$, задача сводится к минимизации линейной функции на симплексе. Следствия:
- минимум достигается в крайней точке (вершине симплекса), то есть в одной из вершин тетраэдра $A_j$ с индексом
$$j=\arg \underset{i}{\min }(w_i{h}_i);$$ значение минимума равно ${\min }_i(w_i{h}_i)$.
- единственность достигается, если минимум строгий; если все коэффициенты $w_i{h}_i$ равны, функция постоянна на симплексе.
- Для других функций (например, сумма квадратов расстояний)
$$g(P)=\sum _{i=1}^4{w}_i{d}_i^2=\sum _{i=1}^4{w}_i{h}_i^2{\lambda }_i^2$$ задача уже квадратичная и может иметь внутренний (внутри симплекса) оптимум; тогда применяют лагранжевы множители или стандартные методы квадратичного программирования.
Итого: барицентрические координаты дают простую линейную связь $d_i={\lambda }_i{h}_i$, что сводит задачи минимизации линейных (взвешенных) сумм расстояний до граней к тривиальной задаче оптимизации на симплексе; для нелинейных сумм потребуются дополнительные (квадратичные или нелинейные) методы.