Кусочно-линейное продолжение

Симплициальное продолжение , или кусочно-линейное продолжение (Аллгауэр и Георг), ^{[1] [2]} - это метод однопараметрического продолжения, который хорошо подходит для малых и средних пространств вложения. Алгоритм был обобщен для вычисления многомерных многообразий (Allgower и Gnutzman) ^[3] и (Allgower and Schmidt). ^[4]

Алгоритм рисования контуров представляет собой алгоритм симплициального продолжения, и, поскольку его легко визуализировать, он служит хорошим введением в алгоритм.

Построение контура [ править ]

Задача построения контура состоит в том, чтобы найти нули (контуры) ( гладкой скалярнозначной функции) в квадрате ,${\ Displaystyle е (х, у) = 0 \,}$${\ Displaystyle е (\ cdot) \,}$${\ Displaystyle 0 \ Leq Икс \ Leq 1,0 \ Leq Y \ Leq 1 \,}$

Квадрат разделен на малые треугольники, как правило , путем введения точек по углам регулярной квадратной сетки , , что делает таблицу значений в каждом углу , а затем разделив каждый квадрат на два треугольника. Значение в углах треугольника определяет уникальный кусочно-линейный интерполянт для каждого треугольника. Один из способов записать этот интерполянт на треугольнике с углами - это система уравнений${\ displaystyle ih_ {x} \ leq x \ leq (i + 1) h_ {x} \,}$${\ Displaystyle jh_ {y} \ leq y \ leq (j + 1) h_ {y} \,}$${\ displaystyle f (x_ {i}, y_ {j}) \,}$${\ Displaystyle (я, j) ​​\,}$${\ displaystyle f (x_ {i}, y_ {j}) \,}$${\ Displaystyle lf (х, у) \,}$${\ Displaystyle е (\ cdot) \,}$${\ Displaystyle (x_ {0}, y_ {0}), ~ (x_ {1}, y_ {1}), ~ (x_ {2}, y_ {2}) \,}$

${\ displaystyle (x, y) = (x_ {0}, y_ {0}) + (x_ {1} -x_ {0}, y_ {1} -y_ {0}) s + (x_ {2} -x_ {0}, y_ {2} -y_ {0}) t \,}$

${\ displaystyle 0 \ leq s \,}$

${\ Displaystyle 0 \ Leq т \,}$

${\ Displaystyle S + T \ Leq 1 \,}$

${\ displaystyle lf (x, y) = f (x_ {0}, y_ {0}) + (f (x_ {1}, y_ {1}) - f (x_ {0}, y_ {0})) s + (f (x_ {2}, y_ {2}) - f (x_ {0}, y_ {0})) t \,}$

Первые четыре уравнения могут быть решены для (это отображает исходный треугольник в прямоугольный единичный треугольник), тогда оставшееся уравнение дает интерполированное значение . На всей сетке треугольников этот кусочно-линейный интерполянт непрерывен.${\ displaystyle (s, t) \,}$${\ Displaystyle е (\ cdot) \,}$

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

Контур кусочно-линейного интерполянта - это набор кривых, составленных из этих отрезков. Любая точка на краю соединения и может быть записана в виде${\displaystyle (x_{0},y_{0})\,}$${\displaystyle (x_{1},y_{1})\,}$

${\displaystyle (x,y)=(x_{0},y_{0})+t(x_{1}-x_{0},y_{1}-y_{0}),\,}$

с in , а линейный интерполянт по краю равен${\displaystyle t\,}$${\displaystyle (0,1)\,}$

${\displaystyle f\sim f_{0}+t(f_{1}-f_{0})\,}$

Итак, установка ${\displaystyle f=0\,}$

${\displaystyle t=-f_{0}/(f_{1}-f_{0})\,}$ и ${\displaystyle (x,y)=(x_{0},y_{0})-f_{0}*(x_{1}-x_{0},y_{1}-y_{0})/(f_{1}-f_{0})\,}$

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

Кусочно-линейное продолжение [ править ]

Кусочно-линейное продолжение похоже на построение контуров (Добкин, Леви, Терстон и Уилкс) ^[5], но в более высоких измерениях. Алгоритм основан на следующих результатах:

Лемма 1 [ править ]

Если F (x) отображается в , существует единственный линейный интерполянт на '(n-1)' -мерном симплексе, который согласуется со значениями функций в вершинах симплекса.${\displaystyle \mathbb {R} ^{n}}$${\displaystyle \mathbb {R} ^{n-1}}$

'(N-1)' -мерный симплекс имеет n вершин, и функция F присваивает каждой 'n' -вектор. Симплекс является выпуклым , и любая точка внутри симплекса представляет собой выпуклую комбинацию вершин. То есть:

Если x находится внутри (n-1) -мерного симплекса с n вершинами , то существуют положительные скаляры такие, что${\displaystyle v_{i}}$${\displaystyle 0<\alpha _{i}}$

Если вершины симплекса линейно независимы, неотрицательные скаляры уникальны для каждой точки x и называются барицентрическими координатами x. Они определяют значение уникального интерполянта по формуле:${\displaystyle \alpha }$

Лемма 2 [ править ]

По сути, есть два теста. Тот, который был использован первым, помечает вершины симплекса вектором знаков (+/-) координат вершины. Например, вершина (.5, -. 2,1.) Будет помечена (+, -, +). Симплекс называется полностью помеченным, если существует вершина, метка которой начинается со строки знаков «+» длины 0,1,2,3,4, ... n. Полностью помеченный симплекс содержит окрестность начала координат. Это может быть удивительно, но в основе этого результата лежит то, что для каждой координаты полностью помеченного симплекса существует вектор со знаком «+» и другой со знаком «-». Другими словами, самый маленький куб с ребрами, параллельными осям координат и покрывающий симплекс, имеет пары граней на противоположных сторонах нуля (то есть «+» и «-». для каждой координаты).

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

Лемма 3 [ править ]

Существует триангуляция (триангуляция Кокстера-Фрейденталя-Куна [1]), которая инвариантна относительно операции поворота.${\displaystyle P_{v_{i}}(v_{0},v_{1},...,v_{n}):=(v_{0},v_{1},...,v_{i-1},{\tilde {v}}_{i},v_{i+1},...,v_{n})}$ где ${\displaystyle {\tilde {v}}_{i}=\left\{{\begin{array}{lcl}v_{1}+v_{n}-v_{0}&&i=0\\v_{i+1}+v_{i-1}-v_{i}&\qquad \qquad &0\\v_{n-1}+v_{0}-v_{n}&&i=n\\\end{array}}\right.}$

Ссылки [ править ]