How to implement triangulation?

Question

Algorithms

Hello, I have a simple question.
Help me find a ready-made triangulation code.
The input data is a two-place array with a set of points in random order. It is desirable that the output data be in the form of a two-dimensional array with point numbers from the first array.
Input data example.
{
{5, 10}, //coordinates of points
{9, 12},
{13, 1},
...
}

Sample output.
{
{1, 3, 6}, // numbers of points from the first array
{9, 7, 5},
{6, 1, 8},
...
}

PS We need a code that triangulates (divides into triangles) a block of points having x,y coordinates and makes it so that there are no voids between the triangles (if they are applied to the plane along the coordinates and all the triangles are painted over, there are no unshaded areas inside the figure).

Thank you in advance for your response.

Answer 1

Hello.
The solution requires the creation of 6 classes. (Triangulation, Vector2, Triangle, DynamicCache, Arc, Helper).
The main program looks something like this.

List<Vector2> Points = new List<Vector2>(); // List (эквивалент массиву), суда записываются координаты точек (далее).

            int[,] array = new int[,] // Сам массив с точками (координатами).
            {
                {200, 0 },
                {0, 200 },
                {400, 200 },
                {200, 400 },
                {600, 400 },
                {200, 500 },
                {0, 600 },
                {400, 600 },
            };

            Points.Add(new Vector2(0d, 0d)); // К сожалению для библиотеку которую нашел Woldemar89 
            Points.Add(new Vector2(1000, 0d)); // требует рамки триангуляции и они включаются в саму триангуляцию.
            Points.Add(new Vector2(1000, 1000)); // Поэтому это они и есть. <-
            Points.Add(new Vector2(0d, 1000));

            for (int i = 0; i < array.GetLength(0); i++) // Внесение в List Points точки из массива.
            {
                Points.Add(new Vector2(array[i, 0], array[i, 1]));
            }

            Triangulation triangulation = new Triangulation(Points); // Использования самой триангуляции.

            for (int i = 0; i < triangulation.triangles.Count; i++) // Вывод координат получившихся треугольников.
            {
                Console.Write(triangulation.triangles[i].points[0].x + " " + triangulation.triangles[i].points[0].y + " - "); // Треугольник 1.
                Console.Write(triangulation.triangles[i].points[1].x + " " + triangulation.triangles[i].points[1].y + " - ");// Треугольник 2.
                Console.WriteLine(triangulation.triangles[i].points[2].x + " " + triangulation.triangles[i].points[2].y);// Треугольник 3.
            }

Photo output.

the classes themselves.
(I can't post everything so in chunks)

class Triangulation
    {
        public List<Vector2> points = new List<Vector2>();
        public List<Triangle> triangles = new List<Triangle>();

        private DynamicCache Cache = null;

        public Triangulation(List<Vector2> _points)
        {
            points = _points;

            //Инициализация кэша
            Cache = new DynamicCache(points[2]);

            //Добавление супер структуры
            triangles.Add(new Triangle(points[0], points[1], points[2]));
            triangles.Add(new Triangle(triangles[0].arcs[2], points[3]));

            //Добавление ссылок в ребра на смежные треугольники супер структуры
            triangles[0].arcs[2].trAB = triangles[1];
            triangles[1].arcs[0].trBA = triangles[0];

            //Добавление супер структуры в кэш
            Cache.Add(triangles[0]);
            Cache.Add(triangles[1]);

            Triangle CurentTriangle = null;
            Triangle NewTriangle0 = null;
            Triangle NewTriangle1 = null;
            Triangle NewTriangle2 = null;

            Arc NewArc0 = null;
            Arc NewArc1 = null;
            Arc NewArc2 = null;

            Arc OldArc0 = null;
            Arc OldArc1 = null;
            Arc OldArc2 = null;

            for (int i = 4; i < _points.Count; i++)
            {
                CurentTriangle = GetTriangleForPoint(_points[i]);

                if (CurentTriangle != null)
                {
                    //Создание новых ребер, которые совместно с ребрами преобразуемого треугольника образуют новые три треугольника 
                    NewArc0 = new Arc(CurentTriangle.points[0], _points[i]);
                    NewArc1 = new Arc(CurentTriangle.points[1], _points[i]);
                    NewArc2 = new Arc(CurentTriangle.points[2], _points[i]);

                    //Сохранение ребер преобразуемого треугольника
                    OldArc0 = CurentTriangle.GetArcBeatwen2Points(CurentTriangle.points[0], CurentTriangle.points[1]);
                    OldArc1 = CurentTriangle.GetArcBeatwen2Points(CurentTriangle.points[1], CurentTriangle.points[2]);
                    OldArc2 = CurentTriangle.GetArcBeatwen2Points(CurentTriangle.points[2], CurentTriangle.points[0]);

                    //Преобразование текущего треугольника в один из новых трех
                    NewTriangle0 = CurentTriangle;
                    NewTriangle0.arcs[0] = OldArc0;
                    NewTriangle0.arcs[1] = NewArc1;
                    NewTriangle0.arcs[2] = NewArc0;
                    NewTriangle0.points[2] = _points[i];

                    //Дополнительно создаются два треугольника
                    NewTriangle1 = new Triangle(OldArc1, NewArc2, NewArc1);
                    NewTriangle2 = new Triangle(OldArc2, NewArc0, NewArc2);

                    //Новым ребрам передаются ссылки на образующие их треугольники
                    NewArc0.trAB = NewTriangle0;
                    NewArc0.trBA = NewTriangle2;
                    NewArc1.trAB = NewTriangle1;
                    NewArc1.trBA = NewTriangle0;
                    NewArc2.trAB = NewTriangle2;
                    NewArc2.trBA = NewTriangle1;

                    //Передача ссылок на старые ребра
                    if (OldArc0.trAB == CurentTriangle)
                        OldArc0.trAB = NewTriangle0;
                    if (OldArc0.trBA == CurentTriangle)
                        OldArc0.trBA = NewTriangle0;

                    if (OldArc1.trAB == CurentTriangle)
                        OldArc1.trAB = NewTriangle1;
                    if (OldArc1.trBA == CurentTriangle)
                        OldArc1.trBA = NewTriangle1;

                    if (OldArc2.trAB == CurentTriangle)
                        OldArc2.trAB = NewTriangle2;
                    if (OldArc2.trBA == CurentTriangle)
                        OldArc2.trBA = NewTriangle2;


                    triangles.Add(NewTriangle1);
                    triangles.Add(NewTriangle2);

                    Cache.Add(NewTriangle0);
                    Cache.Add(NewTriangle1);
                    Cache.Add(NewTriangle2);

                    CheckDelaunayAndRebuild(OldArc0);
                    CheckDelaunayAndRebuild(OldArc1);
                    CheckDelaunayAndRebuild(OldArc2);
                }

            }

            //Дополнительный проход
            for (int i = 0; i < triangles.Count; i++)
            {
                CheckDelaunayAndRebuild(triangles[i].arcs[0]);
                CheckDelaunayAndRebuild(triangles[i].arcs[1]);
                CheckDelaunayAndRebuild(triangles[i].arcs[2]);
            }
        }

PS Thanks to Woldemar89 and ZoAs from cyberforum (very helpful).

Answer 2

Read: https://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%B8%D...