Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Разбиение плоского объекта на треугольники
Subdivision of a planar object into triangles
В геометрии триангуляция — это разбиение плоского объекта на треугольники, а в более общем случае — разбиение геометрического объекта более высокой размерности на симплексы. Триангуляция трехмерного объема предполагает его разбиение на тетраэдры, плотно прилегающие друг к другу. В большинстве случаев треугольники триангуляции должны соприкасаться сторонами и вершинами.
In geometry, a triangulation is a subdivision of a planar object into triangles, and by extension the subdivision of a higher dimension geometric object into simplices. Triangulations of a three dimensional volume would involve subdividing it into tetrahedra packed together. In most instances, the triangles of a triangulation are required to meet edge to edge and vertex to vertex.
Типы
Можно определить различные типы триангуляций в зависимости как от геометрического объекта, подлежащего разбиению, так и от способа определения разбиения. Триангуляция – это разбиение на симплексы размерности *d*, такие, что любые два симплекса пересекаются либо по общей грани (симплексу меньшей размерности), либо не пересекаются вовсе, и любое ограниченное множество в *R<sup>d</sup>* пересекается лишь с конечным числом симплексов. Иными словами, это локально конечный симплициальный комплекс, покрывающий всё пространство. Триангуляция набора точек, то есть триангуляция дискретного набора точек, представляет собой разбиение выпуклой оболочки этих точек на симплексы, такие, что любые два симплекса пересекаются либо по общей грани любой размерности, либо не пересекаются вовсе, и множество вершин симплексов содержится в исходном наборе точек. Часто используемые и изучаемые триангуляции набора точек включают триангуляцию Делоне (для точек в общем положении – набор симплексов, описанных открытым шаром, не содержащим входных точек) и триангуляцию минимального веса (триангуляция набора точек, минимизирующая сумму длин ребер). В картографии треугольная нерегулярная сеть – это триангуляция набора двумерных точек вместе с высотами для каждой точки. Поднятие каждой точки с плоскости на её высоту поднимает треугольники триангуляции в трёхмерные поверхности, формирующие приближение трёхмерного рельефа. Триангуляция многоугольника – это разбиение заданного многоугольника на треугольники, соприкасающиеся сторонами, при этом множество вершин треугольников совпадает с множеством вершин многоугольника. Триангуляции многоугольников можно построить за линейное время и они лежат в основе нескольких важных геометрических алгоритмов, включая простое приближённое решение задачи об охраннике в галерее. Ограниченная триангуляция Делоне – это адаптация триангуляции Делоне от наборов точек к многоугольникам или, в более общем случае, к планарным прямолинейным графам. Триангуляция поверхности состоит из сети треугольников с точками на заданной поверхности, покрывающей её частично или полностью. В методе конечных элементов триангуляции часто используются в качестве сетки (в данном случае, треугольной сетки), лежащей в основе вычислений. В этом случае треугольники должны образовывать разбиение области, подлежащей моделированию, но вместо ограничения вершин входными точками допускается добавление дополнительных точек Штейнера в качестве вершин. Для того чтобы быть пригодной в качестве сетки конечных элементов, триангуляция должна содержать хорошо сформированные треугольники, в соответствии с критериями, зависящими от деталей моделирования конечных элементов (см. качество сетки); например, некоторые методы требуют, чтобы все треугольники были прямоугольными или остроугольными, формируя нетупые сетки. Известно множество методов построения сеток, включая алгоритмы уточнения триангуляции Делоне, такие как второй алгоритм Чу и алгоритм Рупперта. В более общих топологических пространствах триангуляция пространства обычно относится к симплициальным комплексам, гомеоморфным этому пространству.
Different types of triangulations may be defined, depending both on what geometric object is to be subdivided and on how the subdivision is determined. A triangulation of is a subdivision of into dimensional simplices such that any two simplices in intersect in a common face (a simplex of any lower dimension) or not at all, and any bounded set in intersects only finitely many simplices in That is, it is a locally finite simplicial complex that covers the entire space. A point set triangulation, i. e., a triangulation of a discrete set of points , is a subdivision of the convex hull of the points into simplices such that any two simplices intersect in a common face of any dimension or not at all and such that the set of vertices of the simplices are contained in Frequently used and studied point set triangulations include the Delaunay triangulation (for points in general position, the set of simplices that are circumscribed by an open ball that contains no input points) and the minimum weight triangulation (the point set triangulation minimizing the sum of the edge lengths). In cartography, a triangulated irregular network is a point set triangulation of a set of two dimensional points together with elevations for each point. Lifting each point from the plane to its elevated height lifts the triangles of the triangulation into three dimensional surfaces, which form an approximation of a three dimensional landform. A polygon triangulation is a subdivision of a given polygon into triangles meeting edge to edge, again with the property that the set of triangle vertices coincides with the set of vertices of the polygon. Polygon triangulations may be found in linear time and form the basis of several important geometric algorithms, including a simple approximate solution to the art gallery problem. The constrained Delaunay triangulation is an adaptation of the Delaunay triangulation from point sets to polygons or, more generally, to planar straight line graphs. A triangulation of a surface consists of a net of triangles with points on a given surface covering the surface partly or totally. In the finite element method, triangulations are often used as the mesh (in this case, a triangle mesh) underlying a computation. In this case, the triangles must form a subdivision of the domain to be simulated, but instead of restricting the vertices to input points, it is allowed to add additional Steiner points as vertices. In order to be suitable as finite element meshes, a triangulation must have well shaped triangles, according to criteria that depend on the details of the finite element simulation (see mesh quality); for instance, some methods require that all triangles be right or acute, forming nonobtuse meshes. Many meshing techniques are known, including Delaunay refinement algorithms such as Chew's second algorithm and Ruppert's algorithm. In more general topological spaces, triangulations of a space generally refer to simplicial complexes that are homeomorphic to the space.
Обобщение
Понятие триангуляции также может быть несколько обобщено до разбиений на фигуры, связанные с треугольниками. В частности, псевдотриангуляция множества точек — это разбиение выпуклой оболочки точек на псевдотреугольники — многоугольники, которые, как и треугольники, имеют ровно три выпуклых вершины. Как и в случае триангуляции множества точек, псевдотриангуляции должны иметь свои вершины в заданных входных точках.
The concept of a triangulation may also be generalized somewhat to subdivisions into shapes related to triangles. In particular, a pseudotriangulation of a point set is a partition of the convex hull of the points into pseudotriangles—polygons that, like triangles, have exactly three convex vertices. As in point set triangulations, pseudotriangulations are required to have their vertices at the given input points.