Геометрия данных 2. Определение ди- и би-координат

    В первой статье определен метрический базис на элементах, — набор вершин симплекса или графа с известными значениями скалярных произведений (грамиан) или связей (лапласиан) между ними. Здесь рассмотрим, как на таком базисе определить координаты элементов.



    Дистанционные координаты


    Дистанционные координаты представляют собой значения скалярных произведений элемента и реперов — вершин базиса. Будем именовать их ди-координатами.

    Количество компонент ди-координат на единицу больше количества базовых вершин $l$ и на две единицы больше мерности пространства базиса $m=l-1$. Примером ди-координат может служить строка (или колонка) дистанционного метрического тензора (ДМТ).

    Дистанционные координаты элемента будем обозначать как $dm$, в тензорной форме — нижним индексом, указывающем на базис: $dm_a$. Если надо будет указать, к какому именно элементу относятся координаты, то используем скобки: $dm(P)$.

    Полный базис включает в себя нормаль пространства (является мажорным), — соответственно в ди-координатах можно выделить скалярную единицу (произведение элемента и нормали) и набор скалярных произведений элемента и вершин базиса $d$:

    $dm=[1; d]$.

    Набор скалярных произведений $d$ будем называть также минорными компонентами.

    Приведем примеры значений дистанционных координат. Допустим, рядом с нашим базовым треугольником есть еще три точки с известными дистанциями до вершин треугольника — P, Q и R (см. рисунок). Для расчета дистанций используем декартовы координаты точек на плоскости (XY), которые приводим для контроля и сверки:
    Матрица декартовых координат точек:
    \begin{array}{c | c c c c c c}
    XY & A & B & C & P & Q & R \\
    \hline
    X & 0 & 3 & 0 & 1 & 3 & 5 \\
    Y & 0 & 0 & 4 &-1 & 2 & 0 \\
    \end{array}

    Кортеж дистанций от точки P до точек A, B, С здесь такой: $[2, 5, 26]$. Соответственно ди-координаты точки будут такими: $dm(P)=[1; -1.0, -2.5, -13.0]$. У всех точек пространства значение скалярной компоненты ди-координат одно и то же (в рамках данной серии статей).

    Ди-координаты точек Q и R:
    $dm(Q)=[1; -6.5, -2.0, -6.5]$
    $dm(R)=[1; -12.5, -2.0, -20.5]$

    Элементы и векторы


    Разность элементов задает вектор. У ди-координат вектора скалярная компонента равна нулю — по этому признаку вектор $\vec{PQ}$ можно отличить от элемента.

    Геометрия, в которой описание координат точек и векторов отличается, называется аффинной. В такой геометрии вектор можно прибавить к какому-либо элементу (точке) и получить новый элемент. Для векторов определены операции сложения и вычитания (значение скалярной компоненты при этом остается нулевым). Но обычно нет смысла в операции сложения элементов.

    Термин <вектор> перегружен.
    В мире (линейной) алгебры обычно под векторным пространством понимают некое линейное пространство, в котором элементы характеризуются набором чисел, и определены операции сложения и вычитания.
    В таком пространстве нет различия между элементами и векторами — «все вектор».
    В нашем пространстве это не так.

    Дистанция между элементами


    Несложно показать, что метрическим тензором для дистанционных координат является лапласиан (ЛМТ). Для определения квадрата расстояния (дистанции) между элементами P и Q надо найти вектор разности элементов $\vec{pq}$ и рассчитать его норму. Норма вектора определяется через билинейную форму — умножение координат вектора слева и справа и на метрический тензор. Для дистанционных координат это записывается так:

    $q'(P,Q)=||\vec{PQ}||=dm(P-Q) \ Lm \ dm(P-Q) \quad(2.1)$

    где $dm(P-Q) = dm(P) - dm(Q)$ — ди-координаты вектора, $Lm$ — лапласовский метрический тензор.

    Проверяем. Координаты искомого вектора: $dm(P-Q) = [1; -6.5, -2.0, -6.5] - [1; -1.0, -2.5, -13.0] = [0; -5.5, 0.5, 6.5]$. Данные координаты умножаем с двух сторон на лапласовский метрический тензор (ЛМТ) и получаем ответ: $q'_{P,Q}=13$. Можно свериться с расчетом расстояния через дистанции в декартовых координатах: $q(P,Q)=3^2+2^2=13$. Ответы совпали, метрика работает.

    Для проверки расчетов приводим значение ЛМТ нашего базиса из предыдущей статьи
    \begin{array}{c | c c c c}
    Lm(A,B,C) & * & A & B & C \\
    \hline
    * & 6.25 & 0 & 0.5 & 0.5 \\
    A & 0 & 25/144 & -16/144 & -9/144 \\
    B & 0.5 & -16/144 & 16/144 & 0 \\
    C & 0.5 & -9/144 & 0 & 9/144 \\
    \end{array}


    Элемент и его проекция на базовое пространство


    Симплекс из $l$ вершин определяет $m=l-1$-мерное пространство $\mathbb{R}^l$. Базисный треугольник определяет базовую плоскость $\mathbb{R}^2$. Количество дистанционных компонент в ди-координатах элемента на единицу больше мерности пространства. Это означает, что ди-координаты позволяют задавать элементы, выходящие за пределы базового пространства и принадлежащие $\mathbb{R}^n$. В нашем примере элементы могут лежать не только в плоскости базового треугольника, но и на (под) ним.

    Координаты элемента не позволяют определить, с какой стороны базового пространства находится элемент (если он находится вне). В примере с треугольником элементы, расположенные над и под плоскостью треугольника, будут иметь одни и те же координаты.

    Если элемент не принадлежит базовому пространству, то следует различать положение элемента $P$ и его проекции на пространство $P'$. Формула дистанции между элементами (2.1) работает только в базовом пространстве (поэтому в ней дистанция помечена штрихом), то есть определяет квадрат расстояния между проекциями элементов (а не между самими элементами):

    $q'(P,Q) = q_a(P',Q') \quad(2.1')$

    Здесь через индекс $a$ обозначен базис, на пространство которого проецируется дистанция между элементами. В декартовых (и подобных им) координатах нет способа задания координат элементов, выходящих за него. Поэтому в декартовой системе координат таких нюансов нет.

    Норма элемента и дистанция до базового пространства


    Раскрывая скобки в формуле (2.1), получаем «теорему косинусов для элементов». По форме она похожа на обычную , только здесь у нас координаты элементов (а не векторов). Поэтому нет ни углов, ни косинусов. Зато получаем определения норм элементов относительно базиса:

    $q(P',Q') = n(P) + n(Q) - 2 g(P,Q) \quad(2.2)$

    $n(P) = dm(P) \ Lm \ dm(P) \quad(2.3) $

    $g(P, Q) = dm(P) \ Lm \ dm(Q) \quad(2.4) $

    Скаляр $n(P)$ будем называть нормой элемента, а скаляр $g(P, Q)$скалярным произведением элементов. Здесь скалярное произведение выражено через билинейную форму.

    Рассчитаем норму элемента $P$, изображенного на рисунке. Умножая дважды ди-координаты элемента на метрический тензор ЛМТ, получаем ноль: $n(P) = 0$. Что это значит?

    Норма элемента характеризует его положение относительно базового пространства,- равна отрицательной дистанции от элемента до пространства:

    $n(P)=-q(P,P') \quad(2.4.1) $.

    Значение нормы позволяет определить, принадлежит элемент пространству базиса или нет, и если нет, то насколько он от него удален.

    Элементы с нулевой нормой удобно называть точками пространства — это локальные элементы. Элементы с ненулевой нормой — нелокальны относительно пространства базиса.

    Скалярное произведение элементов


    Геометрический смысл скалярного произведения векторов хорошо известен — отражает косинус угла между их направлениями.

    Для интерпретации скалярного произведения элементов обратимся к формуле (2.2), (см. также рисунок проекций). Перегруппировав слагаемые, получим с учетом (2.4.1):

    $g(P,Q) = -(q(P',Q') + q(P,P') + q(Q,Q'))/2 \quad(2.5)$

    Видим, что удвоенное скалярное произведение представляет собой сумму дистанций от элементов до базового пространства и дистанции между проекциями элементов в базовом пространстве.

    Обозначим через $g(PP',QQ')$ следующую комбинацию дистанций:

    $g(PP',QQ') = -(q(P,Q) + q(P',Q') - q(P,Q') - q(P',Q))/2 \quad(2.5.1)$

    Данное выражение представляет собой скалярное произведение упорядоченных пар $(P,P')$ и $(Q,Q')$ нормалей элементов к пространству. Теперь можно выразить произведение элементов через дистанцию между ними и произведение нормалей:

    $g(P,Q) = -q(P,Q)/2 - g(PP',QQ') \quad(2.6)$

    Данная формула позволяет определять дистанции до элементов вне пространства базиса.

    Если скалярное произведение нормалей равно нулю $g(PP',QQ')=0$ (например, один из элементов принадлежит пространству базиса), то дистанция между элементами определяется их скалярным произведением:

    $q(P,Q) = -2 g(P,Q) \quad(2.6.1)$

    Формула (2.6.1) раскрывает смысл скалярного произведения элементов — оно отражает квадрат расстояния между элементами с коэффициентом (-1/2).

    Дистанция между элементами вне базисного пространства


    Если элементы находятся вне базового пространства, то для определения точной дистанции между ними помимо координат требуется дополнительная информация — а именно значение скалярного произведения нормалей на пространство $g(PP',QQ')$. Данное скалярное произведение можно вычислить при условии, что элементы принадлежат одному и тому же надпространству. В этом случае скалярное произведение между нормалями элементов — это просто произведение их длин. Тогда «магическая» формула вычисления дистанции между нелокальными элементами будет такой:

    $q(P,Q)/(-2)=g(P,Q) + sign(P,Q) \sqrt{n(P) \ n(Q)} \quad(2.7)$

    Значение скаляра $sign(P,Q)$ равно 1, если элементы расположены с одной стороны пространства и -1, если с разных. Данная формула — просто частный (но важный) случай тождества (2.6). Во многих прикладных задачах расположение элементов всегда одностороннее, поэтому формула (2.7) может быть использована для определения дистанции между объектами (находящимися, например, в воздухе) если известны их ди-координаты относительно реперов (радаров на земле).

    Непросто представить, что, например, у 3-мерного пространства тоже есть сторона, но математика говорит, что есть. В декартовых координатах сторона, которой принадлежит элемент, определяется знаком значения n-ой компоненты, которая не входит в базовые. Если тетраэдр задан в декартовых координатах x, y, z, и при этом еще существует одна компонента (например, t — время), то можно считать, что плоскость t=0 делит базовое пространство на две стороны. Элементы, у которых компонента t > 0, лежат с одной стороны базового пространства, а у которых t < 0 — с другой.

    Би-координаты


    Взаимными по отношению к дистанционным координатам являются би-координаты элемента. Термин связан с тем, что би-координаты фактически представляют собой расширение барицентрических координат. Метрическим тензором для би-координат является дистанционный тензор.

    Би-координаты элемента обозначаются в тензорной форме верхним индексом $bm^a$. Переход от ди-координат к би-координатам (и обратно) выполняется умножением на соответствующий метрический тензор базиса:

    $bm^i = Lm^{ij} dm_j, \quad dm_i=Gm_{ij} bm^j \quad(2.8)$

    Рассчитаем би-координаты элемента P относительно вершин нашего треугольника. Выполняя умножение ЛМТ на ди-координаты элемента, получаем:

    $bm^i=Lm^{ij} dm_j=[-3/2; 11/12, 1/3, -1/4]$

    Особенность барицентрических координат в том, что сумма их компонент равна 1 (в нашем примере 11/12 + 1/3 — 1/4 = 1). Каждая барицентрическая компонента — это вклад (вес) вершины базиса в координату элемента. Чем больше значение компоненты — тем ближе находится элемент к базовой вершине.

    Орбиталь элемента


    Структура би-координат может быть записана как: $bm = [w; b] $.
    Здесь $b$ — барицентрические координаты, а $w$орбиталь элемента. Орбиталь отражает скалярное произведение элемента и базисной сферы $Z$:

    $w(P) = P \cdot Z \quad(2.9) $

    В геометрии есть понятие степени точки $m(P)$ — положение точки относительно заданной сферы. Задается как разность между дистанцией от точки до центра сферы $q(P,O)$ и радиусом сферы $r$:

    $m(P,O) = q(P,O) - r(O) \quad(2.9.1)$



    На рисунке квадрат длины катета $|PT|$ треугольника $POT$ (от точки до касания сферы) равен значению степени точки P. Точки M и N на рисунке демонстрируют полезное свойство степени, а именно, что ее значение равно произведению длин отрезков $|PM|$ и $|MN|$.

    Орбиталь элемента может быть выражена через степень элемента относительно сферы базиса:

    $w(P) = -m(P, Z')/2 = -(r(P) - rs) /2 \quad(2.9.2) $.

    Если орбиталь больше нуля — элемент лежит внутри сферы базиса, если меньше — снаружи. Барицентрические координаты $b$ характеризуют положение проекции элемента в пространстве базового симплекса, а скалярная компонента — задает пространственное положение относительно сферы.

    Орбиталь вершин базиса равна нулю (поскольку элементы базиса принадлежат сфере). Би-координаты вершин базиса представляют собой единичные координаты (с единицей в своей базисной компоненте и нулем в остальных — обычно обозначаются как $ e $). Например, би-координаты вершины A треугольника будут равны [0; 1, 0, 0].

    Если элемент не принадлежит пространству базиса, то его дистанция до центра сферы $r(P)$ равна сумме дистанций от элемента до его проекции $q(P,P')$ и дистанции от проекции до центра $r(P')$. Первая равна норме элемента с обратным знаком. Тогда можно выразить орбиталь элемента через орбиталь его проекции $w_{P'}$ и норму $n(P)$:

    $w(P) = w(P') - n(P)/2 \quad(2.9.3)$

    В свою очередь орбиталь проекции можно определить через би-линейную форму барицентрических координат элемента и минорного грамиана базиса $G$:

    $w(P') = -b^i(P) G_{ij} b^j(P) /2 \quad(2.9.4)$

    В 5-й части покажем, что понятие орбитали элемента относительно сферы можно обобщить до определения взаимной орбитали элементов. Которое в свою очередь связано с понятием скалярного произведения векторов.

    Би-координаты элементов и векторов


    Как и в случае ди-координат следует отличать би-координаты элемента от би-координат вектора разности элементов (аффинная геометрия). Однако критерий отличия двух типов координат в данной системе иной. Сумма барицентрических компонент элемента равна 1, а сумма компонент вектора будет равна 0 (поскольку разность) — балансовые векторы. (Балансовые векторы используются в проводках бухгалтерского учета). Остальное аналогично. Би-векторы можно складывать и вычитать — при этом результат остается в пространстве векторов.

    Орбиталь (скалярная компонента би-координат) вектора отражает величину проекции центра сферы базиса на вектор. Не зависит от нормы (квадрата радиуса) сферы.

    Би-координаты центра базисной сферы находятся в окаймлении лапласовского метрического тензора. Вспоминая, что сумма компонент лапласиана равна нулю, можно заключить, что строки (колонки) лапласиана базиса отражают би-координаты неких векторов. Это векторы дуального базиса, здесь на них подробно не останавливаемся.

    Дистанция и нормы в би-координатах


    Скалярная компонента добавляет метрику к барицентрическим координатам. При наличии известного метрического тензора (ДМТ) можно вычислять дистанции между элементами, принадлежащими базовому пространству. Все стандартно — через билинейную форму умножения разности координат на метрический тензор. Формулы аналогичны выражениям в ди-координатах с заменой метрического тензора $Lm$ на $Gm$ и ди-координат $dm$ на би-координаты $bm$. Обозначив би-координаты вектора разности элементов как $bm(Q-P)=bm(Q) - bm(P)$, получаем:

    Дистанция между проекциями: $q'(P,Q)=bm(Q-P) \ Gm \ bm(Q-P) \quad(2.10.1)$

    Норма элемента: $n(P)=bm(P) \ Gm \ bm(P) \quad(2.10.2)$

    Скалярное произведение: $g(P,Q)=bm(P) \ Gm \ bm(Q) \quad(2.10.3)$

    Знание би-координат элементов и их положения относительно базового пространства также позволяет вычислять дистанцию между элементами вне базового пространства по формуле (2.6). И это круто. Обычно считается, что барицентрические координаты задают лишь относительное положение элементов. Оказывается, что если добавить к ним скалярную компоненту в виде орбитали, то можно определять пространственное положение не только самого элемента, но и дистанции между элементами вне базового пространства.

    Объединяем ди- и би-координаты


    Нормаль к пространству — особый вектор


    Как уже отмечалось, в полный (мажорный) набор элементов базиса входит вектор нормали пространства $\mathbf{z}$. Ди-координаты нормали имеют вид: [0; 1, 1,...]. Соответственно, би-координаты нормали взаимно обратны: [1; 0, 0,...]. Ди-координаты вектора нормали входят в структуру дистанционного метрического тензора.

    О том, что нормаль это вектор, говорит значение нуля в скалярной компоненте ди-координат и равенство нулю суммы барицентрических координат.

    Норма нормали (свертка ди- и би-координат) всегда равна нулю, поскольку проекция нормали на любое пространство всегда будет точкой.

    Как следствие, — нормаль пространства можно прибавлять к элементам. Такая операция изменяет норму элемента, но не его положение в пространстве. Зная координаты проекции элемента $P'$ и норму $n(P)$, всегда можно определить координаты самого элемента $P$. Для этого вектор нормали умножаем на полунорму элемента и прибавляем полученный вектор к координатам проекции.

    $P = P' + n(P)/2 \mathbf{z} \quad(2.11) $

    Связь параметров базиса с координатами элементов


    Если в формуле связи ди- и би-координат (2.8) раскрыть структуру умножаемых матриц и векторов, то можно получить полезные тождества для скалярной и минорной компонент координат. Для би-координат имеем:

    $ Lm\space dm = bm \space \Rightarrow \space \begin{pmatrix} rs & s^j\\ s^i & L^{ij}\end{pmatrix} \begin{pmatrix} 1 \\ d_j \end{pmatrix} = \begin{pmatrix} rs + s^j d_j\\ s^i + L^{ij} d_j\end{pmatrix} = \begin{pmatrix} w\\ b^i\end{pmatrix} \quad(2.12) $

    Здесь $d_j, b^i$ — минорные ди- и би-координаты элементов. Таким образом:

    $L^{ij} d_j = b^i - s^i \quad(2.12.1)$

    $s^i d_i = w - rs \quad(2.12.2)$

    Выражение (2.12.1) демонстрирует, что результат действия лапласиана на вектор можно интерпретировать как вектор разности элемента и центра сферы.
    Тождество (2.12.2) (при выводе использовано также (2.9) и (2.10)) показывает, как зная минорную составляющую ди-координат, получить ее степень и дистанцию до центра сферы.

    Перейдем к структуре ди-координат:
    $ Gm\space bm=dm \space \Rightarrow \space \begin{pmatrix} 0 & 1_j \\ 1_i & G_{ij} \end{pmatrix} \begin{pmatrix} w \\ b^i \end{pmatrix} = \begin{pmatrix} 1_j b^j\\ w 1_i + G_{ij} b^j \end{pmatrix} = \begin{pmatrix} 1 \\ d_i \end{pmatrix} \quad(2.13)$

    Откуда:
    $1_j b^j = 1 \quad(2.13.1)$

    $d_i = w 1_i + G_{ij} b^j \quad(2.13.2)$

    Первое тождество показывает, что сумма барицентрических компонент равна 1, это и так знали (но тут видно почему — потому что используем единичный вектор в качестве окаймления дистанционной матрицы).
    Второе показывает роль орбитали в дистанционных координатах. Дистанционный вектор $d_i$ складывается из весовой суммы дистанционных векторов вершин базиса $G_{ij} b^j$ и вектора нормали к базовому пространству, величина которого задается орбиталью элемента. Если элемент лежит на сфере базиса, то никакого дополнительного смещения в сторону нормали не требуется.

    Нормы — это свертка координат разных типов


    Используя скалярное произведение координат обоих типов (би- и ди-), можно избавиться в формулах от метрических тензоров.

    Дистанция между проекциями: $q'(P,Q) = bm^i(Q-P) \ dm_i(Q-P) \quad(2.14.1)$

    Норма элемента: $n(P)=dm_i(P) \ bm^i(P) \quad(2.14.2)$

    Скалярное произведение: $g(P,Q)=dm_i(P) \ bm^i(Q) = dm_i(Q) bm^i(P) \quad(2.14.3)$

    Собираем все вместе


    Кратко перечислим основные определения.

    $dm_i$ — ди-координаты элемента, набор скалярных произведений элемента и реперов базиса,
    $bm^i$ — би-координаты элемента, коэффициенты линейного разложения элемента по реперам базиса,

    Изменение типа координат (от ди- к би- и обратно) («жонглирование индексами») выполняется умножением на соответствующий метрический тензор:

    $bm^i=dm_j Lm^{ij}, \ dm_i=bm^j Gm_{ij} $

    Скалярное произведение элементов:

    $ g = dm_i Lm^{ij} dm_j = bm^i Gm_{ij} bm^j = bm^i dm_i $

    $\vec{PQ} = Q - P$ — вектор, разность элементов,

    Норма вектора разности — дистанция между проекциями элементов на пространство базиса:

    $ q(P',Q') = n(\vec{PQ}) = bm^i(Q-P) dm_i(Q-P) \quad(2.17.3) $

    ___
    В следующей статье рассмотрим скалярное произведение упорядоченных пар.
    • +21
    • 4,3k
    • 5
    Поделиться публикацией

    Похожие публикации

    Комментарии 5

      0
      Дистанция между точками

      Напомнило случай, когда ещё учился в ВУЗе. Возникла необходимость алгоритмически определить факт прохождения объекта через границу, вершинами которой были точки, случайно разбросанные по «карте».

      Долго ломали с другом головы. Решение придумали неожиданно простое. Да-да! Именно «неожиданно», т.к. нам казалось, что всё окажется куда сложнее. Необходимо было рассчитывать на каждом шаге расстояние от объекта до вершин, и запоминать его. Как только расстояние между одной из пар окажется минимальным, а затем начнёт расти — значит, объект прошёл между указанными точками.

      Тогда я усвоил, что знать математическую программу — это действительно полезно. С тех пор привожу этот пример людям, которые пытаются обсудить непригодность школьной программы в жизни.
        0
        Спасибо за историю ). На самом деле часто за сухими формулами скрываются чьи-то маленькие открытия, «вау-эффекты». Конечно, математика одна из наиболее практичных наук. Большинство просто пользуются ее плодами, не замечая. Но есть и те, кому приходится вникать — как там все устроено ).
          0
          Объект только по прямой двигается? А если он подъехал к границе, не пересекая её, потом развернулся на 180, и поехал обратно, критерии выполнятся, но без пересечения?
            0
            в этот случай можно добавить проверку, что поменялся знак у вектора расстояния от объекта до граничной прямой (т.е. она была «слева от прямой, а стала — справа» или наоборот)

            В принципе — лучше сразу его считать, но запоминать только знак, и ждать — пока он не изменится (или станет равным нулю).
              0
              Именно так, что нужно вводить новые сущности (граничная прямая или что-то ещё). Решение из поста выше, с расчётом только расстояний между точками, простое, но, скорее всего, неправильное в общем случае.

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое