Изменения

Перейти к: навигация, поиск

Триангуляция Делоне

1529 байт убрано, 01:17, 19 мая 2015
Существование триангуляции Делоне
Окружность, спроецированная на параболоид, находится в одной плоскости. Все точки, лежащие внутри окружности, будут лежать под этой плоскостью. Точки, лежащие вне окружности, будут лежать над плоскостью.
|proof=
Докажем данное утверждение для nРассмотрим окружность с центром в точке <tex>(a, b)</tex> и радиуса <tex>r</tex>, она описывается уравнением: <tex>(x -мерного случаяa)^2 + (y - b)^2 = r^2</tex>.
Возьмём <tex>a_1Раскроем скобки в уравнении окружности, a_2, ..., a_{n+1}</tex> аффинно независимых точек и опишем вокруг них окружность с центром в точке <tex>O</tex> и радиусом <tex>R</tex>. Возьмём произвольную точку получим <tex>x^2 - 2ax + a^2 + y^2 - 2by + b^2 = r^2</tex>, лежащую на расстоянии <tex>tR</tex> от <tex>O</tex>, и посмотрим, как параметр <tex>t</tex> влияет на положение её проекции на параболоид.
Представим <tex>\vec{a_i}</tex> как <tex>\vec O + \vec{r_i}</tex>Рассмотрим параболоид, а пускай его уравнение имеет вид <tex>\vec x</tex> — как <tex>\vec O ^2 + \vec{r_x}y^2 = Cz</tex>. Тогда проекции точек на параболоид будут выглядеть так:
При проецировании, для проекции окружности на параболоид верны оба уравнения: и окружности, и параболоида, поэтому в уравнение окружности вместо <tex>b_i = (\vec O x^2 + \vec{r_i}y^2</tex> можно подставить <tex>Cz</tex>, получится <tex>(\vec O -2a)x + \vec{r_i})^2(-2b) = (\vec O y + \vec{r_i}, \vec O^2 Cz + \vec{r_i}(a^2 + 2\vec O \vec {r_i}) = (\vec O + \vec{r_i}, \vec Ob^2 + R- r^2 + 2\vec O \vec {r_i})= 0</tex>
Заметим, что получившееся уравнение является уравнением плоскости: <tex>b_x = (\vec O Ax + \vec{r_x}, (\vec O By + \vec{r_x})^2) = (\vec O Cz + \vec{r_x}, \vec O^2 + \vec{r_x}^2 + 2\vec O \vec {r_x}) D = (\vec O + \vec{r_x}, \vec O^2 + (tR)^2 + 2\vec O \vec {r_x})0</tex>, то есть, все точки окружности будут лежать в одной плоскости.
{{Acronym|Так как Рассмотрим любую точку внутри данной окружности. Через нее можно привести окружность с центром в точке <tex>(a, b)</tex> и радиусом <tex>\{r_i\}r' < r</tex> аффинно независимы, то тогда плоскость, проходящая через проекцию этой окружности на параболоид будет иметь формулу <tex>r_xAx + By + Cz + D' = 0</tex> можно представить как , т.е., обе плоскости будут параллельны и вторая плоскость будет лежать под плоскостью окружности (поскольку <tex>r_x = \sum_{i=1}^{n+1}k_i r_ir' < r</tex>, причём то <tex>\sum_{iD' =1}(a^2 + b^2 - r'^2) > (a^{n2 +1}k_i b^2 - r^2) = 1D</tex>|Общеизвестный факт}}).
Запишем определительАналогично доказывается, показывающий положение что точки <tex>x</tex> на параболоиде относительно плоскости, заданной точками <tex>\{b_i\}</tex>:лежащие вне окружности лежат над плоскостью.
<tex>
\begin{vmatrix}
O + r_1 & O^2 + R^2 + 2Or_1 & 1 \\
\vdots & \vdots & \vdots \\
O + r_{n+1} & O^2 + R^2 + 2Or_{n+1} & 1 \\
O + r_x & O^2 + (tR)^2 + 2Or_x & 1
\end{vmatrix}
</tex>
 
Умножим первые <tex>n+1</tex> строк на <tex>k_i</tex> и вычтем из последней:
 
<tex>
\begin{vmatrix}
O + r_1 & O^2 + R^2 + 2Or_1 & 1 \\
\vdots & \vdots & \vdots \\
O + r_{n+1} & O^2 + R^2 + 2Or_{n+1} & 1 \\
r_x - \sum_{i=1}^{n+1}k_i r_i & (tR)^2 - R^2 + 2O(r_x - \sum_{i=1}^{n+1}k_i r_i) & 0
\end{vmatrix}
=
\begin{vmatrix}
O + r_1 & O^2 + R^2 + 2Or_1 & 1 \\
\vdots & \vdots & \vdots \\
O + r_{n+1} & O^2 + R^2 + 2Or_{n+1} & 1 \\
0 & R^2(t^2 - 1) & 0
\end{vmatrix}
=
R^2(t^2-1)
\begin{vmatrix}
O + r_1 & 1 \\
\vdots & \vdots \\
O + r_{n+1} & 1
\end{vmatrix}
</tex>
 
Из определителя видно, что знак определителя зависит от ориентации исходных точек <tex>\{a_i\}</tex> и от знака <tex>t^2-1</tex>. Для определённости будем считать, что точки <tex>\{a_i\}</tex> ориентированы так, что предикат поворота положителен. Тогда если <tex>t > 1</tex> (точка <tex>x</tex> лежит вне окружности), то определитель положителен, то есть точка <tex>x</tex> лежит выше плоскости, заданной точками <tex>\{b_i\}</tex>. Если же <tex>t < 1</tex> (точка <tex>x</tex> лежит внутри окружности), то определитель отрицателен, и точка <tex>x</tex> лежит ниже плоскости. Если же точка лежит на окружности, то она попадает на ту же плоскость.
}}
{{Теорема
3
правки

Навигация