Триангуляция (геометрия)

В геометрии триангуляция — это подразделение плоского объекта на треугольники и, в более широком смысле, подразделение геометрического объекта более высокого измерения на симплексы . Триангуляция трехмерного объема предполагает его разделение на тетраэдры, упакованные вместе.

В большинстве случаев треугольники триангуляции должны пересекаться от края к краю и от вершины к вершине.

Типы [ править ]

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

Триангуляция $T$ из $\mathbb {R} ^{d}$ является подразделением $\mathbb {R} ^{d}$ в $d$ -мерные симплексы такие, что любые два симплекса в $T$ пересекаются в общей грани (симплексе любой меньшей размерности) или не пересекаются вообще, и любое ограниченное множество в $\mathbb {R} ^{d}$ пересекается лишь конечное число симплексов в $T$ . То есть это локально конечный симплициальный комплекс , покрывающий все пространство.
, Триангуляция множества точек т. е. триангуляция дискретного набора точек. ${\mathcal {P}}\subset \mathbb {R} ^{d}$ , представляет собой подразделение выпуклой оболочки точек на симплексы такое, что любые два симплекса пересекаются в общей грани любой размерности или не пересекаются вообще, и такое, что множество вершин симплексов содержится в ${\mathcal {P}}$ . ^[1] Часто используемые и изучаемые триангуляции множества точек включают триангуляцию Делоне (для точек общего положения — множество симплексов, описанных открытым шаром, не содержащим входных точек) и триангуляцию минимального веса (триангуляцию множества точек, минимизирующую сумму длины ребер).
В картографии триангулированная нерегулярная сеть представляет собой триангуляцию набора двумерных точек вместе с высотами для каждой точки. Подъем каждой точки с плоскости на ее повышенную высоту превращает треугольники триангуляции в трехмерные поверхности, которые образуют аппроксимацию трехмерной формы рельефа.
- Триангуляция многоугольника это подразделение данного многоугольника на треугольники, пересекающиеся между краями, опять же с тем свойством, что набор вершин треугольника совпадает с набором вершин многоугольника. ^[2] Триангуляции полигонов могут быть найдены за линейное время и составляют основу нескольких важных геометрических алгоритмов, включая простое приближенное решение проблемы художественной галереи . Ограниченная триангуляция Делоне — это адаптация триангуляции Делоне от наборов точек к многоугольникам или, в более общем смысле, к плоским прямолинейным графам .
Евклидова триангуляция поверхности $\Sigma$ представляет собой множество подмножества компактов $T_{\alpha }$ из $\Sigma$ гомеоморфен невырожденному треугольнику в $\mathbb {R} ^{2}$ с помощью $f_{\alpha }$ так, что они покрывают всю поверхность, пересечение любой пары подмножеств либо пусто, либо является ребром, либо вершиной, а если пересечение, то пересечение $T_{\alpha }\cap T_{\beta }$ тогда не пусто $f_{\alpha }f_{\beta }^{-1}$ является изометрией плоскости на этом пересечении. ^[3]
В методе конечных элементов триангуляции часто используются в качестве сетки (в данном случае треугольной сетки ), лежащей в основе вычислений. В этом случае треугольники должны образовывать подразделение моделируемой области, но вместо ограничения вершин входными точками разрешено добавлять дополнительные точки Штейнера в качестве вершин. Чтобы быть подходящей в качестве сетки конечных элементов, триангуляция должна иметь треугольники правильной формы в соответствии с критериями, которые зависят от деталей моделирования методом конечных элементов (см. Качество сетки ); например, некоторые методы требуют, чтобы все треугольники были прямыми или острыми, образуя нетупые сетки . Известны многие методы построения сетки, включая алгоритмы уточнения Делоне , такие как второй алгоритм Чу и алгоритм Руперта .
В более общих топологических пространствах триангуляции пространства обычно относятся к симплициальным комплексам, гомеоморфным пространству. ^[4]

Обобщение [ править ]

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

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

^ Де Лоэра, Хесус А .; Рамбау, Йорг; Сантос, Франциско (2010). Триангуляции, структуры для алгоритмов и приложений . Полет. 25. Спрингер. ISBN 9783642129711 .
^ Берг, Марк Теодор де; Кревелд, Марк ван; Овермарс, Марк Х.; Шварцкопф, Отфрид (2000). Вычислительная геометрия: алгоритмы и приложения (2-е изд.). Берлин Гейдельберг: Springer. стр. 45–61. ISBN 978-3-540-65620-3 .
^ Пападопулос, Атанас (2007). Справочник по теории Тейхмюллера . Европейское математическое общество. п. 510. ИСБН 9783037190296 .
^ Баснер, Уильям Ф. (20 октября 2006 г.). Топология и ее приложения . Уайли. стр. 3–14. ISBN 978-0-471-68755-9 .

Внешние ссылки [ править ]

Вайсштейн, Эрик В. «Триангуляция» . Математический мир .

[1] Де Лоэра, Хесус А .; Рамбау, Йорг; Сантос, Франциско (2010). Триангуляции, структуры для алгоритмов и приложений . Полет. 25. Спрингер. ISBN 9783642129711 .

[2] Берг, Марк Теодор де; Кревелд, Марк ван; Овермарс, Марк Х.; Шварцкопф, Отфрид (2000). Вычислительная геометрия: алгоритмы и приложения (2-е изд.). Берлин Гейдельберг: Springer. стр. 45–61. ISBN 978-3-540-65620-3 .

[3] Пападопулос, Атанас (2007). Справочник по теории Тейхмюллера . Европейское математическое общество. п. 510. ИСБН 9783037190296 .

[4] Баснер, Уильям Ф. (20 октября 2006 г.). Топология и ее приложения . Уайли. стр. 3–14. ISBN 978-0-471-68755-9 .

[1]

[2]

[3]

[4]