Optimization of the algorithm for checking the Delaunay condition through the circumcircle equation and its application
I'll tell you a secret about how to quickly check the Delaunay condition for two triangles.
Actually, the optimization itself is described a little lower (see “Optimization of the algorithm for checking the Delaunay condition through the circumcircle equation”), but I’ll tell you about everything in order.
In my case, triangulation is used in image tracing to divide the plane into primitive sectors (triangles). As you know, it is also divided into several stages: adjustment, identifying boundaries, walking around boundaries, sweeping out contours. It's in the very general view. I would really like to stop, I think difficult stage: sweeping the plane.
At the entrance
After detecting and traversing the boundaries, I got a lot of outer loops at the output. Each touching contour has different colors. Each such circuit also contains a known number of internal circuits.Thus, from the point of view of “sweeping the plane,” if we consider the external contours separately, we have a set of points, each of which has one neighbor to the right and left. Those. all points are closed in a chain, there is not a single “hanging” point, and each chain contains at least 3 points (Figure 1).
Picture 1
What need to do
You need to cover the figure with triangles.Search
After reading the book, I did not find a single (at least one) method of constructing a Delaunay triangulation that was at least somewhat suitable for my case. I didn't look for other books. And this was enough, it put the thoughts in my head in order. As a result, he invented his own “bicycle”.Algorithm
1) Let's assume, for starters, that there is only one sequence in the figure under consideration. Then it all comes down to sequentially taking triangles. We take any point and try to construct a triangle with neighboring points. If it was not possible to build a triangle (the line connecting these two points intersects with those already built or the line passes in the exclusion zone (Figure 2), we move to the next point, say to the right. When the next triangle is found, we add it to the list (Figure 3), and We remove the point from which it was built (Figure 4).
Figure 2
Figure 3
Figure 4
One more thing: when saving the next triangle, it is necessary to record the vertices in a clockwise traversal (in the right coordinate system). This will be useful in the future to reduce computing resources.
2) Repeat step 1 until we have swept the entire plane.
3) If there are several sequences, i.e. one, and inside it there is one or more internal contours (Figure 1). Here it is necessary to consider each sequence separately. Let's take another internal contour. From one external and one internal we will make two single circuits. To do this, you need to find two “ports” from one circuit to another. Condition for “ports”: they should not intersect with each other (even their ends should not touch), and should not intersect with contour lines (Figure 5).
Figure 5
Figure 6
4)
Next, you should enter one by one all the internal sequences into the already formed sequences, separated from each other (point 3). You need to merge it with the one that contains the new one. By definition, no internal sequence touches or intersects with others (both one external and all possible internal ones), so everything will go smoothly.
Having found the ports (Figure 6), it is easy to construct new sequences and bypass them using points 1 and 2 of the current algorithm (Figure 7). 
Figure 7
5)
After the 4th stage we have a list of triangles (Figure 8). It’s as if the task has already been completed, but all that remains is to make the picture beautiful: check that the Delaunay condition is fulfilled (Figure 9). 
Figure 8
Figure 9
6) Looking ahead, I’ll tell you about the sixth point. It consists of sequentially running through the list of obtained triangles using step No. 5. First, we mark all the triangles as “dirty”. In each cycle we check the Delaunay condition for each triangle. If the condition is not met, then we rebuild and mark the neighbors and the current triangle as “dirty”. If the condition is met, then we mark it clean. In my implementation of the algorithm, each triangle has a link to its neighbors. In this case, point 6 works the fastest.
More about the fifth stage
Now, as far as I know, there are two possible ways determine whether triangles satisfy the Delaunay condition or not: 1) Check the sum of opposite angles. It must be less than 180. 2) Calculate the center of the circumscribed circle and calculate the distance to the 4th point. Everyone knows that the Delaunay condition is satisfied if the point is outside the circumscribed circle.Computing power #1: 10 multiply/divide and 13 add/subtract.
Computing power #2: 29 multiplication/division operations and 24 addition/subtraction operations.
From the point of view of computing power, which is calculated for example in the book, option No. 1 is more profitable. I would have implemented it, if not... (Figure 10). As it turned out after the production this method onto the “conveyor belt”, the result was uncertainty. This is an option when angle A itself is more than 180 degrees. It is considered in the book as one of the individual private methods. And with this, all its elegance, transparency and performance disappears. And it also later turned out that method No. 2 can be very significantly optimized.
Figure 10
Optimization of the algorithm for checking the Delaunay condition through the circumcircle equation
Next is pure mathematics.So we have:
Checking the condition for the point M(X, Y) by the equation of a circle passing through the points A(x1, y1), B(x2, y2), C(x3, y3) can be written as:
(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ sign a ≥ 0
Details can be found in the excellent book. (No, I'm not the author)
So, sign a is the traversal direction sign, from the very beginning I built the triangles clockwise, so it can be omitted (it is equal to one).
A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);
D>=0 
Figure 11
Simple isn't it?
According to the book, again,
(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (y1*x2 - x1*y2)<= 0
We have: 15 multiplication/division operations and 14 addition/subtraction operations.
Thank you for your attention. I'm waiting for criticism.
Bibliography
1. Skvortsov A.V. Delaunay triangulation and its application. – Tomsk: Publishing house Tom. University, 2002. – 128 p. ISBN 5-7511-1501-5GRID models are models of regular cells.
Let the coordinate system be introduced 
And 
And 
. User sets 
and sampling steps 
.
,
- physical coordinates of the point.
We calculate 
And 
,
- bit grid.
- quantized values. Real:
- algorithm parameter – number of points, 
- weight. The closer the point, the greater the weight.
- degree of distance (1 or 2).
Normalization factor: 
How 
closer to 1, the more points with higher weights are taken into account.
This is the IDW method - long, for each t it is necessary to find neighbors. The set of neighbors can be efficiently found - nearest. Each point produces a “peg” of a certain height. Much depends on the irregularity of setting the point, for this they take 
or 
those. divided into sectors and build points in the vicinity.
Advantage– simplicity
Flaw:
------Ticket 14. Tin model. Delaunay triangulation algorithms------
1) Triangulation (tin).
Triangulation– construction of a function in the form of a set of piecewise linear functions
Triangulation– interpolation within a convex region.
Triangulation– a planar graph, all of whose internal edges are triangles; a way of representing space in the form of triangles adjacent to each other without overlap. Triangulation is built on a set of points in several ways.
An algorithm is needed to construct optimal triangulation.
A plane passing through 3 points.
1) Find a triangle that 
;
2)
- construct an equation of the plane.
To check whether the points are inside the triangle or not, you need to substitute the value into the equation of the lines - the edges of the triangle. If all 3 equations > 0, then inside.
Presentation structure:
Each triangulation contains the same number of triangles.
, Where 
– number of internal points, 
- amount of points.
Greedy triangulation.
We connect all the points with edges, select the minimum, and add them to the triangulation. Next, we take the next minimum that does not intersect with the previous ones, etc. The result is greedy triangulation.
Delaunay triangulation.
The inside of a circle circumscribed around any triangle does not include the points of other triangles. It is built in the only way.
A flip is a transfer of edges. It allows you to move from conventional triangulation to Delaunay triangulation. To check whether a point belongs to a circle: substitute if< R, то внутри.
Delaunay condition.
Equation of a circle passing through three points:
If less than zero, then external, otherwise - internal.
– Delaunay condition.
Algorithm for constructing Delaunay triangulation:
1) Adding dots under investigation– a simple iterative algorithm:
There is a set 
add to the triangle, construction is carried out 
triangle splitting 
rebuilding. At the zero stage, we add 3-4 fictitious points, which obviously cover our envelope, all the points inside. Then we throw the point, look at which triangle it hits, divide it into 3, for each triangle we check the Delaunay condition and perform a flip transfer of edges. The average number of lane changes is three.
Theoretical complexity 
2) Acceleration methods. Based on statistically dependent points. The seed triangle is the triangle into which the previous point fell. Then we connect two points - the previous one and the new one.
We move from the first point to another.
Optimization of the algorithm for checking the Delaunay condition through the circumcircle equation and its application
- Image processing ,
- Programming
I'll tell you a secret about how to quickly check the Delaunay condition for two triangles.
Actually, the optimization itself is described a little lower (see “Optimization of the algorithm for checking the Delaunay condition through the circumcircle equation”), but I’ll tell you about everything in order.
In my case, triangulation is used in image tracing to divide the plane into primitive sectors (triangles). As you know, it is also divided into several stages: adjustment, identifying boundaries, walking around boundaries, sweeping out contours. This is in the most general terms. I would like to stop, I think, at the most difficult stage: sweeping the plane.
At the entrance
After detecting and traversing the boundaries, I got a lot of outer loops at the output. Each touching outline has a different color. Each such circuit also contains a known number of internal circuits.Thus, from the point of view of “sweeping the plane,” if we consider the external contours separately, we have a set of points, each of which has one neighbor to the right and left. Those. all points are closed in a chain, there is not a single “hanging” point, and each chain contains at least 3 points (Figure 1).
Picture 1
What need to do
You need to cover the figure with triangles.Search
After reading the book, I did not find a single (at least one) method of constructing a Delaunay triangulation that was at least somewhat suitable for my case. I didn't look for other books. And this was enough, it put the thoughts in my head in order. As a result, he invented his own “bicycle”.Algorithm
1) Let's assume, for starters, that there is only one sequence in the figure under consideration. Then it all comes down to sequentially taking triangles. We take any point and try to construct a triangle with neighboring points. If it was not possible to build a triangle (the line connecting these two points intersects with those already built or the line passes in the exclusion zone (Figure 2), we move to the next point, say to the right. When the next triangle is found, we add it to the list (Figure 3), and We remove the point from which it was built (Figure 4).
Figure 2
Figure 3
Figure 4
One more thing: when saving the next triangle, it is necessary to record the vertices in a clockwise traversal (in the right coordinate system). This will be useful in the future to reduce computing resources.
2) Repeat step 1 until we have swept the entire plane.
3) If there are several sequences, i.e. one, and inside it there is one or more internal contours (Figure 1). Here it is necessary to consider each sequence separately. Let's take another internal contour. From one external and one internal we will make two single circuits. To do this, you need to find two “ports” from one circuit to another. Condition for “ports”: they should not intersect with each other (even their ends should not touch), and should not intersect with contour lines (Figure 5).
Figure 5
Figure 6
4)
Next, you should enter one by one all the internal sequences into the already formed sequences, separated from each other (point 3). You need to merge it with the one that contains the new one. By definition, no internal sequence touches or intersects with others (both one external and all possible internal ones), so everything will go smoothly.
Having found the ports (Figure 6), it is easy to construct new sequences and bypass them using points 1 and 2 of the current algorithm (Figure 7).
Figure 7
5)
After the 4th stage we have a list of triangles (Figure 8). It’s as if the task has already been completed, but all that remains is to make the picture beautiful: check that the Delaunay condition is fulfilled (Figure 9).
Figure 8
Figure 9
6) Looking ahead, I’ll tell you about the sixth point. It consists of sequentially running through the list of obtained triangles using step No. 5. First, we mark all the triangles as “dirty”. In each cycle we check the Delaunay condition for each triangle. If the condition is not met, then we rebuild and mark the neighbors and the current triangle as “dirty”. If the condition is met, then we mark it clean. In my implementation of the algorithm, each triangle has a link to its neighbors. In this case, point 6 works the fastest.
More about the fifth stage
Now, as far as I know, there are two possible ways to determine whether triangles satisfy the Delaunay condition or not: 1) Check the sum of opposite angles. It must be less than 180. 2) Calculate the center of the circumscribed circle and calculate the distance to the 4th point. Everyone knows that the Delaunay condition is satisfied if the point is outside the circumscribed circle.Computing power #1: 10 multiply/divide and 13 add/subtract.
Computing power #2: 29 multiplication/division operations and 24 addition/subtraction operations.
From the point of view of computing power, which is calculated for example in the book, option No. 1 is more profitable. I would have implemented it, if not... (Figure 10). As it turned out, after putting this method on the “conveyor”, uncertainty resulted. This is an option when angle A itself is more than 180 degrees. It is considered in the book as one of the individual private methods. And with this, all its elegance, transparency and performance disappears. And it also later turned out that method No. 2 can be very significantly optimized.
Figure 10
Optimization of the algorithm for checking the Delaunay condition through the circumcircle equation
Next is pure mathematics.So we have:
Checking the condition for the point M(X, Y) by the equation of a circle passing through the points A(x1, y1), B(x2, y2), C(x3, y3) can be written as:
(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ sign a ≥ 0
Details can be found in the excellent book. (No, I'm not the author)
So, sign a is the traversal direction sign, from the very beginning I built the triangles clockwise, so it can be omitted (it is equal to one).
A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);
D>=0
Figure 11
Simple isn't it?
According to the book, again,
(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (y1*x2 - x1*y2)<= 0
We have: 15 multiplication/division operations and 14 addition/subtraction operations.
Thank you for your attention. I'm waiting for criticism.
Bibliography
1. Skvortsov A.V. Delaunay triangulation and its application. – Tomsk: Publishing house Tom. University, 2002. – 128 p. ISBN 5-7511-1501-5Basic definitions and properties
A triangulation is a planar graph whose interior regions are all triangles.
Properties:
· The Delaunay triangulation corresponds one-to-one to the Voronoi diagram for the same set of points.
· As a consequence: if no four points lie on the same circle, the Delaunay triangulation is unique.
· Delaunay triangulation maximizes the minimum angle among all angles of all constructed triangles, thereby avoiding “thin” triangles.
· Delaunay triangulation maximizes the sum of the radii of inscribed spheres.
· Delaunay triangulation minimizes the discrete Dirichlet functional.
· Delaunay triangulation minimizes the maximum radius of the minimum ambient sphere.
· The Delaunay triangulation on the plane has the minimum sum of the radii of the circles described around the triangles among all possible triangulations.
Figure 1. Triangulation.
A convex triangulation is a triangulation for which the minimum polygon enclosing all the triangles is convex. A triangulation that is not convex is called non-convex.
The problem of constructing a triangulation from a given set of two-dimensional points is the problem of connecting given points by non-intersecting segments so that a triangulation is formed.
A triangulation is said to satisfy the Delaunay condition if none of the given triangulation points falls inside the circle circumscribed around any constructed triangle.
A triangulation is called a Delaunay triangulation if it is convex and satisfies the Delaunay condition.
Figure 2. Delaunay triangulation.
Delaunay empty ball method. Construction in the general case
Let's use an empty ball, which we will move, changing its size so that it can touch the points of the system (A), but always remain empty.
So, let us place an empty Delaunay ball in the system of points (A). This is always possible if you choose a ball small enough. Let's begin to increase its radius, leaving the center of the ball in place. At some point the surface of the ball will meet some point i of the system (A). This will definitely happen, because there are no infinitely large voids in our system. We will continue to increase the radius of the empty ball so that point i remains on its surface. To do this, you will have to move the center of the ball from point i. Sooner or later the ball will reach with its surface another point in the system (A).
Fig.3
Delaunay simplexes fill space without gaps or overlaps.
The described sphere of any simplex does not contain other points of the system within itself.
Let this be point j. Let's continue to increase the radius of our ball, keeping both points on its surface. As the ball increases, it will reach some third point of the system, point k. In the two-dimensional case, our “empty circle” will be fixed at this moment, i.e. It will become impossible to further increase its radius while keeping the circle empty. At the same time, we identify an elementary two-dimensional configuration of three points (i, j, k), defining a certain triangle, the peculiarity of which is that there are no other points of the system (A) inside its circumcircle. In three-dimensional space, a ball is not defined by three points. Let's continue to increase its radius, keeping all three points found on its surface. This will be possible until the surface of the ball meets the fourth point l of the system. After this, the movement and growth of the empty ball will become impossible. The found four points (i,j,k,l) define the vertices of the tetrahedron, which is characterized by the fact that inside its circumscribed sphere there are no other points of the system (A). Such a tetrahedron is called a Delaunay simplex.
In mathematics, a simplex is the simplest figure in a space of a given dimension: a tetrahedron - in three-dimensional space; triangle - in two dimensions. An arbitrary three (four) of points of the system that do not lie in the same plane always defines a certain simplex. However, it will be a Delaunay simplex only if its described sphere is empty. In other words, Delaunay simplices are determined by a special choice of triplets (quadruples) of points in system (A).
We have constructed one Delaunay simplex, but by placing the empty ball in different places and repeating the same procedure, we can define others. It is stated that the set of all Delaunay simplices of system (A) fills the space without overlaps and gaps, i.e. implements the division of space, but this time into tetrahedrons. This partition is called Delaunay tiling(Fig. 3).
Application of Delaunay triangulation
Delaunay triangulations are often used in Euclidean space. The Euclidean minimum spanning tree is guaranteed to lie on the Delaunay triangulation, so some algorithms use triangulation. Also, through Delaunay triangulation, the Euclidean traveling salesman problem is approximately solved.
In 2D interpolation, Delaunay triangulation splits the plane into the thickest triangles possible, avoiding too sharp and too obtuse angles. Using these triangles, you can build, for example, bilinear interpolation.
Another frequently encountered problem in geoinformatics is the construction of slope exposures. Here it is necessary to determine the dominant directions of the slopes by cardinal direction and divide the surface into regions in which a certain direction dominates. Since determining the exposure does not make sense for horizontal areas of the surface, areas that are horizontal or have a slight slope are allocated to a separate region, for example<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.
Fig.4.
The problem of calculating slope exposures is usually used to analyze the illumination of the Earth. In this regard, there is often a need to additionally take into account the current position of the Sun, i.e. exposure is calculated as the direction between the normal to the triangle and the direction to the Sun.
Thus, each triangulation triangle can be classified according to the principle of belonging to a particular region. After this, you just need to call the region selection algorithm.
Triangulation is the approximation of the surface of a modeled object by triangular plates spaced from it at a distance not exceeding a certain specified value 6. All triangular plates must be joined together. Their tops lie on the surface. A set of triangular plates is easier to work with than a general surface. We will call triangular plates triangles. For a triangle, the distance to a given point or the point of intersection with a given line in space is quickly calculated. Triangulation of the faces is performed for visual perception of the geometric model, so the sides of the triangles are selected so that the eye cannot notice the kinks.
When displaying geometric objects by triangles on parametric planes of surfaces, a spatial triangulation of the faces of the body must be constructed by calculating an array of points in space and an array of normals to the faces of the body at these points using an array of two-dimensional points. To quickly display bodies, their faces are approximated by triangular plates built on Normal points are required to determine the behavior of light rays interacting with the faces of a body. The tone drawings in the previous chapters and in this chapter are made using triangulation.
As a result of surface triangulation, we want to have an array of two-dimensional points on a parametric plane and an array of triplets of integers, which are the numbers of points in the first mentioned array. Thus, each triangle will be represented by three numbers of its vertices in the parameter array. For each two-dimensional point of the parametric domain, a spatial point on the surface and the surface normal in it can be calculated. Spatial points and normals can be stored in arrays similar to a 2D point array.
Let's look at some methods of triangulation. For flat surfaces, there are cost-effective triangulation methods in which triangles are constructed at the boundary points of the surface and there is no need to search for points inside the parametric region.
Delaunay triangulation.
Let's consider some area on the plane. We will call an area convex if, when moving along its boundary, you have to turn only in one direction (only to the left or only to the right). The Delaunay algorithm can be used to triangulate convex planar regions. We won't be able to directly apply this algorithm to triangulate free-form surfaces, but we will use its method for constructing triangles.
Rice. 9.7.1. Convex region with given points inside
Let some convex two-dimensional region bounded by a closed broken line and a set of points inside this region be given (Fig. 9.7.1).
It is required to divide the specified area into triangles, the vertices of which are the given points inside the area and the vertices of the broken line bounding it. The triangles must not overlap each other, and their sides can only intersect at the vertices.
Several different sets of triangles can be constructed to fill a specified area. In all cases, the number of triangles is equal to , where K is the number of vertices of the bounding polyline, I is the number of given points inside the region.
Rice. 9.7.2. Selecting the third point of the Delaunay algorithm
A triangulation of a region will be a Delaunay triangulation if there are no vertices of other triangles inside the circle described around each triangle. Delaunay triangulation builds triangles as close to equiangular as possible (does not allow the construction of unreasonably elongated triangles).
It can be called balanced. A Delaunay triangulation will be unique if no four vertices lie on the same circle.
Let's consider the Delaunay triangulation. We will call the vertices of the polyline bounding the region and the given points inside the region the vertices of the triangulation. We will call the sides of triangles edges. Among the edges, we select segments of the bounding polyline, which we will call boundary edges. Let's orient all the boundary edges so that the convex region lies to the left of each edge. Let it be necessary to construct a triangle, the side of which is the boundary edge AB, shown in Fig. 9.7.2.
Through vertices A, B and any vertex that does not lie on the same line with them, a circle can be drawn. As the third vertex of the triangle, we choose vertex V, the corresponding circle does not contain other vertices on the same side relative to the segment AB on which point V lies. For a boundary edge, in the general case, one such vertex can be found. We will call it the closest one. The center of a circle passing through points A, B and V lies at the intersection of perpendiculars to the midpoints of segments AB, BV and VA. The position of the center of the circle will be characterized by the parameter t of the segment MN, perpendicular to the edge AB, equal in length and passing through the middle of the edge AB.
Rice. 9.7.3. Delaunay triangulation process
For all vertices lying to the left of segment AB, the nearest vertex has the smallest parameter t. The circle corresponding to the nearest vertex does not contain other vertices to the left of the segment AB. Let vertices A, B and V be described by two-dimensional radius vectors, respectively. The radius vectors of the midpoints of segments AB and BV will be equal
The value of the parameter t of the line, corresponding to the position on it of the center of the circle passing through points A, B and V, is equal to
For the vertex closest to the left of the segment AB, the parameter t has a minimum value.
Let's orient all the boundary edges so that the area to be triangulated lies to the left of each of them. We start constructing triangles from any boundary edge. Let us find the closest vertex for it, the corresponding circle of which does not contain other vertices. Let the nearest vertex V be found for the boundary edge AB. Then we construct a triangle ABV and transfer the edge AB to the category of inactive. We will call inactive edges and vertices that do not participate in the triangulation algorithm. If there is no edge BV among the boundary edges, then we construct a new boundary edge on the segment VB. If among the boundary edges there is an edge BV, then we transfer it and vertex B to the category of inactive. If there is no edge VA among the boundary edges, then we will construct a new boundary edge on the segment AV. If among the boundary edges there is an edge VA, then we transfer it and vertex A to the category of inactive. The triangulation process is shown in Fig. 9.7.3.
Rice. 9.7.4. Delaunay triangulation
We finish triangulation when all vertices and edges become inactive. The result of triangulation of a given area is shown in Fig. 9.7.4.
Triangulation by correction method.
Let's consider the triangulation of a certain surface with a rectangular domain for defining parameters. Let's divide the domain for defining surface parameters into rectangular cells with two-dimensional lines. These lines form a rectangular grid. Let us take the parametric distances between adjacent lines in accordance with formula (9.4.7) to be equal
Let us take the parametric distances between adjacent lines in accordance with formula (9.4.8) to be equal
By constructing diagonals in all rectangular cells, we obtain a triangulation of the surface (we obtain a set of triangles that meets the requirements). In Fig. 9.7.5 shows the triangulation of the surface of revolution using the described method.
Let us consider the triangulation of a surface with an arbitrary boundary. We will build the triangulation method on the correction by boundary contours of the surface triangulation described above with a rectangular area for determining the parameters.
Rice. 9.7.5. Triangulation of a surface with a rectangular domain for defining parameters
Let the surface boundary in the parameter definition domain be described by several non-intersecting two-dimensional contours (2.12.7). One of the contours is external and contains the remaining contours. For the positive direction for each contour we will take the direction along which, when moving along, the surface definition area is always to the left of the contour, when looking towards the surface normal. Let's construct polygons in the positive direction of the boundary contours of the surface definition area. To construct boundary polygons, you need to walk along the boundary contours of the surface with some variable step and fill in an array of two-dimensional points, the coordinates of which are the surface parameters. We will build a polygon from points on a parametric plane, but the step when moving from one point to another will be determined from spatial geometry, namely, from the condition that the deflection of the curve arc between adjacent points is no more than a given value. We calculate the parametric steps for constructing a polygon for the surface boundary contour curve using formula (9.4.4).
Each polygon consists of an ordered set of two-dimensional points. Each section of a polygon can be considered as a two-dimensional straight line segment built on two adjacent points. We will use such areas as boundary edges, and the points of the polygons on which the edges are based will be used as triangulation vertices. Since the area for determining the surface parameters lies to the left of the boundary polygons, when constructing triangles for each boundary triangulation edge, you should look for the third vertex of the triangle to the left of the edge.
Let's determine which nodes lie inside the boundary polygons, and which lie on the border or outside the surface definition area. Using this information, we sort the rectangular grid cells into two groups. The first group includes cells that lie entirely within the area where the surface parameters are determined (the cells should not touch the boundary polygons). The second group includes the remaining cells (lying outside the surface definition area or intersected by boundary polygons).
Rice. 9.7.6. Unfinished surface triangulation
Inside each cell of the first group, using a diagonal, we will construct two triangles. Thus we get an unfinished triangulation. An example of constructing triangles in cells of the first group for a surface of revolution limited by contours is shown in Fig. 9.7.6.
We will construct boundary edges on the unintersected sides of the cells of the second group and direct them so that the corresponding cell is to the left of the edge. Around the cells of the first group, we will construct a closed broken line (possibly several closed lines) so that when moving along it, the part of the area that is not divided into triangles lies on the left, when looking towards the surface normal. We will also use the straight sections of this broken line as boundary edges. We will consider all edges to be equal. To complete the triangulation, we need to construct triangles between the boundary edges. For each edge we will look for a vertex that lies to the left of it and can be used to construct a triangle. We will search for a vertex only among those vertices that lie in the same cell with the edge. To select a vertex, we use the Delaunay method described above and illustrated in Fig. 9.7.2. If such a vertex is found, then you should check whether two new edges of the triangle intersect with any boundary edge. Let the nearest vertex V be found for the boundary edge AB and check that the segments BV and VA do not intersect other boundary edges. Then we will construct triangle ABV and transfer edge AB to the inactive category. If there is no edge BV among the boundary edges, then we will construct a new boundary edge on the segment VB, but if there is an edge BV among the boundary edges, then we will transfer it and vertex B to the category of inactive. If there is no edge VA among the boundary edges, then we will construct a new boundary edge on the segment AV, but if there is an edge VA among the boundary edges, then we will transfer it and vertex A to the category of inactive.
If a segment or VA intersects other boundary edges, then we move on to searching for the nearest vertex for another boundary edge. Triangulation will be completed after all edges and vertices are classified as inactive.
Rice. 9.7.7. Triangulation by correction method
In Fig. 9.7.7 shows surface triangulation by the method of correcting triangles in cells intersected by boundary contours. In Fig. 9.7.8, using the resulting triangulation, the surface itself is displayed.
If the boundary polygons and the surface have some symmetry, then triangulation by the correction method will have a similar symmetry.
Triangulation by absorption method.
Let's consider another triangulation method. In terms of speed, it is inferior to Delaunay triangulation and its modifications. To begin the triangulation procedure, it is necessary to represent the surface boundary in the form of closed polygons. During the triangulation process, we will need to determine steps based on surface parameters. With a known direction of movement, these steps are determined by formulas (9.4.6). Approximate steps for surface parameters can be found as follows. Let us define a region on the parameter plane around a certain point in such a way that any spatial segment from point to point in this region would be no further than a given value S from the surface.
To do this, we calculate the permissible increments of parameters along the coordinate lines
where are the coefficients of the first and second quadratic forms of the surface at point . As the boundary of the desired region, we take an ellipse with a center at a point and semi-axes . This ellipse has the equation
If you want to find a point on the plane next to a point in the direction given by the angle with the and axis, then its parameters will be
First, let's consider a simpler case when the area of surface parameters is limited to one external contour. We approximate the surface boundary by a closed polygon on the parametric domain. When constructing triangulation, we will use the working polygon, which in this case we will take as the polygon of the external contour. We will add the polygon points to the resulting array of two-dimensional points. We will build triangles from the edge of the working area, narrowing it until there are only three points left in the working area.
Let's find a vertex in the working polygon at which it turns into the region. Such a point always exists and the angle of rotation at it is smaller. Let us denote this point by O, and its parameters by Near this point we will construct one or two triangles, depending on the angle of rotation. If the angle is smaller, then we will build one triangle on these three points (Fig. 9.7.9). Otherwise, we will construct two triangles on this, two neighboring and one new points (Fig. 9.7.11). The new point is designated by P. We will look for point P on the diagonal of the parallelogram B OS P. If the vertex of the parallelogram lies inside the ellipse (Fig. 9.7.10), then we will take it as point P. Otherwise, we will take the intersection of the ellipse and the diagonal of the parallelogram as point P . In the latter case, it is not at all necessary to look for the intersection of the ellipse and the segment.
The coordinates of point P are determined through the coordinates of points O BC
The angle of the segment OP with the horizontal is determined by the equality
(9.7.8)
These data make it possible to determine the position of point P relative to the ellipse (9.7.5).
In the case shown in Fig. 9.7.9, let’s construct a triangle (remember the numbers of its vertices) and delete point O in the working area. In the case shown in Fig. 9.7.11, we will construct two triangles and in the working area we will replace point O with point P and place the latter in the resulting array of points. In Fig. Figure 9.7.12 shows the polygon obtained after constructing two triangles and eliminating point O. In both cases, point O will be removed from the working polygon and the working polygon will narrow. Note that triangles can be constructed only when the working area, after narrowing, does not intersect itself.
Rice. 9.7.9. Construction of a triangle
Rice. 9.7.10. Result polygon
Rice. 9.7.11. Construction of two triangles
Rice. 9.7.12. Result polygon
Such situations are shown in Fig. 9.7.13. They can occur when the sides of the constructed triangles intersect the sides of the working area that are not adjacent to them. Before constructing a new triangle as in the case shown in Fig. 9.7.9, and in the case shown in Fig. 9.7.11, a check must be made to ensure that the resulting polygon does not intersect itself.
Moreover, when determining the position of point P, it is important that it is at a sufficient distance from other points of the working area and does not come close to the segments connecting the points of the area. Otherwise, difficulties may arise in the future when constructing triangles. Therefore, before narrowing the working polygon, you should check the resulting polygon for self-intersection. If it is impossible to construct a triangle (triangles) near point O, then instead you should find another point at which the polygon wraps inside the contour more than in others, and perform the described actions at it.
Next, with the modified working area, we will perform the same actions that we just described. Let's find a point in the working polygon at which it turns inside the area more than at other points, check for the possibility of narrowing the polygon in it by constructing one or two triangles and narrow the polygon.
Rice. 9.7.13. You cannot build triangles in this corner.
Continuing this process, we will expand the array of two-dimensional points and the array of triangles, and at the same time we will narrow the working polygon, reducing the area it covers and the number of its points. At some stage of these actions we will receive a working polygon consisting of three points. Let's build the last triangle at these points, eliminate the working area and finish the triangulation. In the described triangulation method, the area limited by the working area is, as it were, eliminated by cutting off triangles from it.
Let's consider the general case when the area of surface parameters is limited by one external contour and several internal contours that lie entirely inside the external contour. We approximate the surface boundary by closed polygons on the parametric domain. For each contour we will build our own polygon. Just like for contours, for polygons built on them, the rule of their mutual orientation must be fulfilled. The orientation of the inner polygons must be opposite the orientation of the outer polygon. Let's start constructing the triangulation with the outer contour polygon. Let's put its points into the resulting array of two-dimensional points, and make the polygon itself a working one.
We will construct triangles in the same way as in the case of a simply connected region. Let's find point O in the working area, check for the possibility of narrowing the working area there, and narrow the area. If there are internal contours, it becomes more difficult to check the possibility of narrowing the working area at a selected point. In addition to the described checks for the intersection of the sides of triangles with the sides of the working area, it is necessary to check for the intersection of the sides of triangles with the sides of all internal polygons.
Let us check the possibility of constructing two triangles at point O (Fig. 9.7.11), and find that the new point P, once constructed, will fall inside one of the internal polygons or will be in unacceptable proximity to its segments. In this case, we will not construct point P, but instead will include this internal polygon in the working polygon by constructing the two triangles shown in Fig. 9.7.14.
In order to include the points of one of the internal polygons in the working polygon, we find among the points of the internal polygon the point closest to point C (adjacent to point O) of the working polygon.
Let's construct triangles at points OCF and CEF and between points O and C of the working area insert points of the internal polygon, starting from point F and ending with point E. Thus, we will break the working area on the segment OS, break the internal polygon on the segment EF and unite them with segments OF and the EU.
Rice. 9.7.14. Construction of two triangles
Rice. 9.7.15. Merging external and internal polygons
The result of the merger is shown in Fig. 9.7.15. Of course, before merging the outer and inner polygons, checks must be made to ensure the correctness of this operation.
Next, we will continue to narrow the working area in the described way until we find ourselves in close proximity to another internal area and include it in the working area. As a result, all internal polygons will be included in the working polygon, which should be narrowed to the last three points. As a result, the entire multiply connected region for determining surface parameters will be covered with triangles.
Rice. 9.7.16. You cannot build triangles in this corner.
There may be situations when it is impossible to construct a single triangle on the given polygons. In Fig. 9.7.16 shows an area limited by two polygons, each of which consists of four segments. For the outer polygon, we cannot continue triangulation because the inner polygon is in the way. In this case, we will find two neighboring points B and C of the polygon, for which we can construct a triangle HRV. Point P is projected onto the middle of side BC and is located at such a distance from it that the new triangle does not intersect the polygons.
Other methods of triangulation.
There are other ways of triangulation. For example, after constructing the polygons of the external and internal contours of the surface definition area, a different strategy for constructing triangles can be chosen. Another option is to combine the outer and inner polygons into one polygon before starting triangulation. You can “sketch” points inside the parameter definition area using a certain algorithm and perform Delaunay triangulation using them and the points of the boundary contour polygons. There are algorithms that first construct large triangles and then divide them into manageable sizes.
Body triangulation.
The triangulation of a body is a set of triangles obtained by triangulating the surfaces of its faces. Triangulation of individual surfaces differs from triangulation of body faces in that in the latter case, boundary polygons for adjacent faces must be consistent (Fig. 9.7.17).
Rice. 9.7.17. Body Face Boundary Polygon Consistency
Sections of polygons of adjacent faces passing along common edges will be consistent if their points coincide in space.
Application of triangulation.
The triangles constructed as a result of triangulation are used to obtain tone images. In Fig. 9.7.18 and 9.7.19 show triangulations of the face of a sheet body, the tone image of which is shown in Fig. 6.5.1.
Rice. 9.7.18. Triangulation of a body face using the correction method
Partitioning the domain of determining surface parameters into triangles can be used in integrals (8.6.2), (8.6.3), (8.6.12), (8.7.17)-(8.7.22) when calculating the geometric characteristics of bodies. During numerical integration, the parametric step for curves should be calculated using formula (8.11.5), and for surfaces, parametric steps should be calculated using formulas (8.11.1) and (8.11.2).
