Optimization of the algorithm for checking the Delaunay condition through the equation of the circumscribed circle and its application

I'll tell you a secret about how to quickly verify that the Delaunay condition is fulfilled for two triangles.
The actual optimization itself is described below (see “Optimization of the algorithm for checking the Delaunay condition through the equation of the circumscribed circle”), but I will talk about everything in order.

In my case, triangulation is used in image tracing, for dividing the plane into primitive sectors (triangles). As you know, it is also divided into several stages: adjustment, identification of borders, bypassing borders, sweeping contours. This is in its most general form. I would like to stop, I think, at the most difficult stage: sweeping the plane.

At the entrance

After detecting and bypassing the borders at the output, I got a lot of external contours. Each contour contour has a different color. Each known 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 many 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 single “hanging” point, and also each of the chains contains at least 3 points (Figure 1).


Picture 1

What need to do

It is necessary to sweep the figure with triangles.

Search

After reading the book [1] I did not find a single (at least one) method of constructing the Delaunay triangulation that was at least somehow suitable for my case. I did not search for other books. Yes, and this was enough, she brought my head's thoughts in order. As a result, he invented his "bicycle."

Algorithm

1) Suppose, for starters, that in the figure under consideration there is only one sequence. Then it all comes down to the successive withdrawal of triangles. We take any point and try to build a triangle with neighboring points. If the triangle could not be built (the line connecting these two points intersects with the already constructed ones or the line passes in the exclusion zone (Figure 2), we move to the next point, let's right. When the next triangle is found, put it on the list (Figure 3), and delete 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 the computational resources.

2) Repeat step 1 until we sweep the entire plane.

3) If there are several sequences, i.e. one, and inside it another one or more internal contours (Figure 1). Here it is necessary to consider each sequence separately. Take the next inner contour. From one external and one internal, we make two single circuits. To do this, find two “ports” from one circuit to another. The condition for the “ports”: they should not intersect each other (should not even touch the ends), should not intersect with the contour lines (Figure 5).


Figure 5

Figure 6
4)Then it is necessary to introduce in turn all the internal sequences in the already formed, separated from each other (paragraph 3) sequences. You need to merge 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 that everything goes smoothly.
Having found the ports (Figure 6), it is easy to build new sequences and bypass them with 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 they had already completed the task, but it remains 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 in a sequential run through the list of triangles received by item No. 5. First, we label all the triangles “dirty”. In each cycle, we check the Delaunay condition for each triangle. If the condition is not met, then do the rebuild and mark the neighbors and the current triangle “dirty”. If the condition is satisfied, then we mark it clean. In my implementation of the algorithm, each triangle has a reference to its neighbors. In this case, the 6th item is the fastest.

Read more about the fifth stage.

Now, as far as I know, there are two possible ways to determine whether the triangles satisfy the Delaunay condition or not: 1) Check the sum of the opposite angles. It should 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.

Power of calculations No. 1: 10 operations of multiplication / division and 13 operations of addition / subtraction.
Computing power No. 2: 29 operations of multiplication / division and 24 operations of addition / subtraction.

From the point of view of computing power, which is calculated for example in the book [1], option No. 1 is more profitable. He realized it, if not for ... (Figure 10). As it turned out after setting this method on the "conveyor", the resulting uncertainty. This is an option when the angle A itself is more than 180 degrees. It is considered in the book [1] as one of the separate private methods. And with it all its elegance, transparency and performance disappear. And also later it turned out that method No. 2 can be very significantly optimized.


Figure 10

Optimization of the algorithm for checking the Delaunay condition through the equation of the circumscribed circle


Next is pure math.

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 in the form:

(a ⋅ (X ^ 2 + Y ^ 2) - b ⋅ X + c ⋅ Y - d) ⋅ sign a ≥ 0

Details can be found in the magnificent book [1]. (No, I’m not its author)
So, sign a is a sign of the direction of the bypass, from the very beginning I built triangles clockwise, so that it can be omitted (it is equal to one).

Next, moving the center of coordinates to point M, we obtain (Figure 11):

A (x1 - X, y1 - Y), B (x2 - X, y2 - Y), B (x3 - X, y3 - Y);

-d> = 0

Figure 11

Just isn't it?

d <= 0

According to the book, again, [1]

(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 operations of multiplication / division and 14 operations of addition / subtraction.

Thanks for attention. 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-5

Also popular now: