Генератор триангуляции Делоне

Генератор триангуляции Делоне превращает любой набор двумерных точек в уникальную триангуляцию, которая максимизирует наименьший внутренний угол — золотой стандарт для моделирования рельефа, построения сеток конечных элементов, интерполяции методом ближайшего соседа и занятий по вычислительной геометрии. Вставьте координаты (или выберите готовый шаблон), и инструмент запустит алгоритм Бойера-Ватсона на стороне сервера, окрасит каждый треугольник в соответствии с его качеством, а также покажет свойство пустой описанной окружности, выпуклую оболочку и диаграмму Вороного по запросу.

Как читать построенную сетку

Чем отличается этот генератор триангуляции Делоне

Что такое триангуляция Делоне?

Для заданного набора двумерных точек обычно существует множество способов объединить их в триангуляцию (полное покрытие их выпуклой оболочки треугольниками без перекрытий и зазоров). Триангуляция Делоне, названная в честь российского математика Бориса Делоне (1934), удовлетворяет свойству пустой описанной окружности: для каждого треугольника в сетке окружность, проходящая через три его вершины, не содержит других входных точек. Это единственное свойство имеет замечательное следствие: среди всех триангуляций одного и того же набора точек триангуляция Делоне максимизирует наименьший внутренний угол. Простыми словами, она создает максимально «толстые» и «сбалансированные» треугольники.

Как работает алгоритм Бойера-Ватсона

1. Окружить все входные точки очень большим супертреугольником.
2. Вставлять по одной входной точке за раз. Для каждой новой точки найти каждый существующий треугольник, чья описанная окружность содержит эту точку — это «плохие» треугольники.
3. Удалить плохие треугольники. Оставшаяся после них полость имеет многоугольную границу.
4. Соединить новую точку с каждым ребром этой границы, формируя новые треугольники.
5. После вставки всех точек удалить все треугольники, которые все еще соприкасаются с вершинами супертреугольника. То, что осталось, и есть триангуляция Делоне для исходного набора точек.

Где применяется триангуляция Делоне

• Моделирование рельефа (ГИС): замеры высот (обычно расположенные неравномерно, например, метеостанции) объединяются в нерегулярную триангуляционную сеть (TIN) для запросов высот, затенения и 3D-визуализации.
• Анализ методом конечных элементов: треугольники Делоне правильной формы обеспечивают стабильные численные решения дифференциальных уравнений в частных производных в механике, теплопередаче и электродинамике.
• Компьютерная графика: генерация сеток для рендеринга, риггинга персонажей и процедурного рельефа — гарантия отсутствия узких треугольников в триангуляции Делоне позволяет избежать артефактов растяжения текстур.
• Интерполяция методом естественного соседа: гладкие поверхности восстанавливаются по разбросанным точкам путем вычисления естественных соседей для каждой запрашиваемой точки с помощью двойственной диаграммы Вороного.
• Занятия по вычислительной геометрии: канонический алгоритм, имеющий глубокие связи с выпуклыми оболочками, диаграммами Вороного, локализацией точек и принципом «разделяй и властвуй».
• Слайсеры для 3D-печати и траектории станков с ЧПУ: двумерная триангуляция Делоне (и ее трехмерный аналог — тетраэдризация Делоне) лежит в основе многих стратегий нарезки и заполнения.

Делоне vs Вороного: две стороны одной медали

Диаграмма Вороного разбивает плоскость на ячейки — по одной на каждую входную точку, где каждая ячейка содержит все области, находящиеся ближе к этой точке, чем к любой другой. Если соединить точки, чьи ячейки имеют общую границу, вы получите в точности триангуляцию Делоне. И наоборот, центры описанных окружностей соседних треугольников Делоне, соединенные отрезками, образуют ребра Вороного. Включите «Диаграмма Вороного» в этом инструменте, чтобы увидеть оранжевые пунктирные линии, наложенные на ту же диаграмму: каждое ребро Делоне пересекает ровно одно ребро Вороного под прямым углом.

Качество, узкие треугольники и улучшение сетки

Триангуляция Делоне максимизирует глобальный минимальный внутренний угол, но она не может исправить изначально плохое распределение точек. Если ваши входные точки расположены почти на одной линии, сгруппированы в кластеры или оставляют большие пустые области, некоторые треугольники все равно будут узкими (минимальный угол ниже 20°). Решением является вставка точек Штейнера: такие алгоритмы, как алгоритм Рупперта и второй алгоритм Чью, итеративно добавляют новые точки в центры описанных окружностей узких треугольников, каждый раз перестраивая триангуляцию, пока каждый треугольник не будет соответствовать целевому ограничению качества. Этот генератор показывает вам, какие треугольники являются узкими, чтобы вы знали, где добавить точки Штейнера, если вам нужна более точная сетка.

Практический пример

Нажмите на шаблон «Окружность с центром». Инструмент разместит 18 точек по окружности и 1 точку в центре, а затем построит их триангуляцию. В результате получится идеальный веер из 18 равнобедренных треугольников, сходящихся в центре — каждый из них имеет углы 10° на краю и 80°–80° в центре. Худший минимальный угол равен 10°, все треугольники отмечены как узкие, а гистограмма показывает, что все элементы находятся в диапазоне 0°–10°. Этот пример — отличный учебный случай: даже оптимальная триангуляция Делоне может содержать узкие треугольники, когда этого требуют входные данные. Теперь нажмите «Случайное облако» — тот же алгоритм создаст треугольники правильной формы, так как точки распределены равномерно, и гистограмма сместится вправо.

Частые заблуждения

• «Триангуляция Делоне уникальна»: обычно да, но если четыре входные точки лежат на одной окружности, для этой группы существуют две допустимые триангуляции Делоне. Генератор последовательно выбирает одну из них.
• «Больше точек всегда означает лучшее качество»: добавление неудачно расположенных точек может привести к появлению новых узких треугольников. Алгоритмы точек Штейнера размещают новые точки аккуратно — в центрах описанных окружностей, благодаря чему качество гарантированно улучшается.
• «Триангуляция Делоне — это то же самое, что выпуклая оболочка»: нет. Выпуклая оболочка — это внешняя граница; триангуляция Делоне заполняет внутреннюю область треугольниками.
• «Все триангуляции выглядят примерно одинаково»: разница колоссальна. Всего одно переключение («flip») ребра в сторону от Делоне может превратить треугольник с углом 25° в треугольник с углом 5°. Тепловая карта качества нашего инструмента делает эту разницу наглядной.

Часто задаваемые вопросы