@mIka01

Как реализовать триангуляцию?

Здраствуйте, у меня простой вопрос.
Помогите найти готовый код триангуляции.
Входные данные, двухместный массив с набором точек в случайном порядке. Желательно что бы выходные данные были в виде двухмерного массива с номерами точек из первого массива.
Пример входных данных.
{
{5, 10}, //координаты точек
{9, 12},
{13, 1},
...
}

Пример выходных данных.
{
{1, 3, 6}, // номера точек из первого массива
{9, 7, 5},
{6, 1, 8},
...
}

P.S. Нужен код который триангулирует (разобьёт на треугольники) облоко точек имеющие координаты x,y и сделает это так, чтобы между триугольниками небыло пустот (если их нанести на плоскость по координатам и закрасить все треугольники, внутри фигуры не осталось не закрашеных участков).

Заранее благодарю за ответ.
  • Вопрос задан
  • 178 просмотров
Решения вопроса 1
@mIka01 Автор вопроса
Здраствуйте.

Для решения требуются создать 6 классов. (Triangulation, Vector2, Triangle, DynamicCache, Arc, Helper).

Основная программа выглядит как то так.
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.
            }


Фото вывода.
60374b0a22307886070503.png

Сами классы.
(не могу опубликовать все поэтому кусками)
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]);
            }
        }


P.S. Благодарю Woldemar89 и ZoAs с форума киберфорум (очень помогли).
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы