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

Разбиение плоского объекта на треугольники

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

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

Типы

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

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

Обобщение

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

Ссылки

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

Внешние ссылки

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