Триангуляция (геометрия) - Triangulation (geometry)
В геометрии , A триангуляции является подразделение плоского объекта на треугольники, и расширением подразделения более высокой размерности геометрического объекта в симплексах . Триангуляции трехмерного объема потребуют разбиения его на тетраэдры, упакованные вместе.
В большинстве случаев требуется, чтобы треугольники триангуляции пересекались между ребрами и вершинами.
Типы
Могут быть определены различные типы триангуляции, в зависимости от того, какой геометрический объект должен быть разделен, и от того, как это подразделение определяется.
- Триангуляцией из является подразделением в n - мерных симплексов таких , что любые два симплекса в пересекаются в общей грани (симплекс любого меньшей размерности) или нет вообще, и любое ограниченное множество в пересекается лишь конечное множество симплексов в . То есть это локально конечный симплициальный комплекс , покрывающий все пространство.
- Точка-множество триангуляции , то есть, триангуляция дискретного множества точек , является подразделением выпуклой оболочки точек на симплексы такие , что любые два симплекса пересекается в общей грани любой размерности или нет вообще , и таким образом, что множество вершин симплексов содержится в . Часто используемые и изучаемые триангуляции наборов точек включают триангуляцию Делоне (для точек в общем положении набор симплексов, описанных открытым шаром, не содержащий входных точек) и триангуляцию с минимальным весом (триангуляция набора точек, минимизирующая сумму длины кромок).
- В картографии , A триангулированная нерегулярная сеть представляет собой множество точек триангуляции из множества двумерных точек вместе с возвышениями для каждой точки. Поднятие каждой точки с плоскости на ее повышенную высоту поднимает треугольники триангуляции на трехмерные поверхности, которые образуют приближение трехмерной формы рельефа.
- Многоугольник триангуляция является подразделением данного многоугольника на треугольники , отвечающих от края до края, опять - таки с тем свойством , что множество вершин треугольника совпадает с множеством вершин многоугольника. Триангуляции многоугольников могут быть найдены за линейное время и составляют основу нескольких важных геометрических алгоритмов, включая простое приближенное решение проблемы художественной галереи . Ограниченно триангуляция Делона является адаптацией триангуляции Делона от точечных множеств до полигонов или, в более общем плане , для плоских графов прямой линии .
- Триангуляция поверхности состоит из сетки треугольников с точками на данной поверхности , покрывающей поверхность частично или полностью.
- В методе конечных элементов триангуляции часто используются в качестве сетки (в данном случае треугольной сетки ), лежащей в основе вычислений. В этом случае треугольники должны образовывать подразделение моделируемой области, но вместо ограничения вершин входными точками разрешается добавлять дополнительные точки Штейнера в качестве вершин. Чтобы быть подходящей в качестве конечно-элементной сетки, триангуляция должна иметь треугольники правильной формы в соответствии с критериями, которые зависят от деталей моделирования методом конечных элементов (см. Качество сетки ); например, некоторые методы требуют, чтобы все треугольники были прямыми или острыми, образуя неупругие сетки . Многие методы Meshing известны, в том числе уточняющего Делона алгоритмов , такие как второй алгоритм Чу в и алгоритме Ruppert в .
- В более общих топологических пространствах триангуляции пространства обычно относятся к симплициальным комплексам, гомеоморфным пространству.
Обобщение
Концепция триангуляции также может быть в некоторой степени обобщена на подразделения на формы, связанные с треугольниками. В частности, псевдотриангуляция множества точек - это разбиение выпуклой оболочки точек на псевдотреугольники, многоугольники, которые, как и треугольники, имеют ровно три выпуклые вершины. Как и в случае триангуляции наборов точек, псевдотриангуляции должны иметь свои вершины в заданных входных точках.