О барицентрических координатах на пальцах
Привет.
Наверняка всем доводилось быть свидетелями оценки на глазок степени сходства ребенка с родителями: что-нибудь типа «вылитый папа, но на маму тоже похож!!!»
(взято отсюда)
Как в примере на изображении, можно оценить степень похожести в процентах. Можно задействовать еще родственников, для более точного описания лица малыша в виде взвешенной суммы лиц родни…
И будет это выглядеть и восприниматься вполне естественно для «обычного» человека, не связанного с антропологией, или, например, криминалистикой. Для профессионала в области анализа и распознавания лиц, человеческое лицо представляется, скорее, набором параметров. То есть, точкой (набор координат) в некотором пространстве с базисом (оси, соответствующие параметрам). И если описывать лицо ребенка в сравнении с его родственниками, то скорее всего, точка, соответствующая лицу ребенка окажется в этом пространстве параметров внутри выпуклой оболочки облака точек, соответствующих лицам ближайших родственников (но это не точно).
Собственное, к чему я это все… Эти два подхода к описанию лиц соответствуют двум системам координат:
- барицентрической, описание точки в пространстве (в нашем примере: лица) через взвешенную смесь других точек;
- аффинной, описание точки в пространстве через координаты в некотором базисе.
Так что же такое барицентрические координаты?
Пусть в
В случае одномерного пространства (линия), нам необходимы 2 не совпадающие точки, случае двумерного пространства — невырожденный треугольник, в случае трехмерного — тетраэдр.
Тогда любая точка пространства
Набор
Чем барицентрические координаты лучше/хуже аффинных?
Пожалуй, начнем с относительных недостатков:
- в барицентрическом представлении нам необходимо на одну координату больше, чем в аффинном;
- расстояние между точками, заданными барицентрически, нельзя напрямую вычислять в этих координатах.
Отчасти первый недостаток компенсируется тем, что не смотря на необходимость использования
Что касается второго недостатка, если есть необходимость вычисления расстояния между точками, представленными барицентрически, то имеет смысл посчитать скалярные произведения
Каковы же бонусы от использования барицентрических координат?
- Барицентрические координаты инвариантны к аффинным преобразованиям пространства. Это свойство используется, например, для линейной интерполяции в компьютерной графике. Пусть в вершинах треугольного элемента поверхности определены текстурные координаты
и нормали ( ), тогда каждая точка этого участка поверхности будет обладать барицентрическими координатами , ее текстурные координаты и нормаль могут быть вычислены как:
- По барицентрическим координатам легко определить, принадлежит ли точка
части пространства, ограниченной многогранником с вершинами : это выполняется только в том случае, если . Равенство i-й барицентрической координаты 1 означает, что точка совпадает с . Если несколько барицентричесих координат равны 0, то это означает, что точка принадлежит подпространству, натянутому на радиус-вектора остальных точек, соответствующие координаты которых больше 0.
Наверное, они очень сложно вычисляются?
Не сложнее, чем любое линейное преобразование системы координат. Потому что по сути вычисление барицентрических координат таковым преобразованием и является.
Перепишем радиус-вектора точек в следующем виде:
Тогда формулу (1) можно переписать в следующем виде:
Раскроем скобки в сумме:
Согласно свойства (2):
Соответственно:
где
Учитывая (2), ограничимся вычислением первых n барицентрических координат. Представим переход в барицентрические координаты как линейное преобразование:
где
Учитывая свойства барицентрического представления, если в качестве
Если матрицу
где
Из (10) находим
Таким образом, имея набор из точек с радиус-векторами
Используя эту матрицу, мы можем получить первые
Вновь воспользовавшись соотношением (2), получим последнюю барицентрическую координату:
Заключение
Может с первого взгляда барицентрика и кажется неуклюжей и сложной. Но на самом деле, это очень удобный и незаменимый во многих задачах инструмент, к которому довольно быстро привыкаешь. Потому, что тут нет никакой магии, это линейная алгебра в чистом виде!