На данном этапе работы были рассмотрены некоторые методы построения двумерных конечно-элементных сеток и за основу был взят метод триангуляции Делоне.
Введём несколько определений:
1. Триангуляцией
называется планарный граф, все внутренние области которого являются
треугольниками
2. Задачей построения триангуляции по заданному
набору двумерных точек называется задача соединения заданных точек
непересекающимися отрезками так, чтобы образовалась триангуляция.
3. Выпуклой
триангуляцией называется такая триангуляция, для которой минимальный
многоугольник, охватывающий все треугольники, будет выпуклым. Триангуляция, не
являющаяся выпуклой, называется невыпуклой.
4. Говорят, что триангуляция удовлетворяет
условию Делоне, если внутрь окружности, описанной вокруг любого построенного
треугольника, не попадает ни одна из заданных точек триангуляции.
5. Триангуляция
называется триангуляцией Делоне, если она является выпуклой и удовлетворяет
условию Делоне.
Структуры для представления триангуляции
Выбор структуры для представления триангуляции оказывает существенное влияние на теоретическую трудоёмкость алгоритмов, а также на скорость конкретной реализации. Кроме того, выбор структуры может зависеть от цели дальнейшего использования триангуляции. В триангуляции можно выделить 3 основных вида объектов: узлы (точки, вершины), рёбра (отрезки) и треугольники.
Детализация триангуляции
Во многих алгоритмах анализа требуется, чтобы
треугольники были достаточно маленькими. Наиболее остро эта проблема встает при
использовании различных методов конечных элементов и при визуализации рельефа.
Такая задача, обратная к упрощению триангуляции, называется задачей детализации
триангуляции.
Задача:
Визуализация двумерных конечно-элементных сеток в
браузере.
Для решения данной задачи была взята библиотека d3-delaunay. Немного о ней:
Это библиотека для вычисления диаграммы Вороного
набора двумерных точек. Она основана на Delaunator, быстрой библиотеке для
вычисления триангуляции Делоне с использованием алгоритмов развертки.
На входе он принимает набор точек:
и производит на выходе триангуляцию:
Триангуляция представлена в виде компактных массивов целых чисел. Это менее удобно, чем другие представления, но именно поэтому библиотека работает быстро.
Результат выполнения данной задачи на примере триангуляции прямоугольника с использованием библиотеки d3-delaunay
Дальнейшие требования к решаемой задаче:
1.Как
можно точнее приблизить границу области
2.Треугольники должны быть ближе к равносторонним и, желательно, одного размера
Вывод
Ключевой метод для построения двумерных конечно-элементных сеток – триангуляция Делоне. А библиотека d3-delaunay позволяет быстро вычислить триангуляцию Делоне по набору двумерных точек.