Почему триангуляция Делоне имеет значение?

Она является основой для моделирования рельефа (TIN), построения сеток конечных элементов, компьютерной графики, интерполяции методом ближайшего соседа и слайсеров для 3D-печати. Избегая узких треугольников, она обеспечивает стабильные численные результаты и гладкие интерполированные поверхности.

Как диаграмма Вороного связана с триангуляцией Делоне?

Они являются двойственными графами. Диаграмма Вороного строится путем соединения центров описанных окружностей соседних треугольников Делоне. Каждая ячейка Вороного содержит ровно одну входную точку и представляет собой область плоскости, ближайшую к этой точке. Включите «Показать двойственную диаграмму Вороного», чтобы наложить ее поверх.

Что такое узкий треугольник и зачем их считать?

Узким называется треугольник, чей наименьший внутренний угол меньше 20 градусов. Узкие треугольники вызывают численные проблемы при анализе методом конечных элементов и видимые артефакты на интерполированных поверхностях. Триангуляция Делоне сводит к минимуму их появление, но не может устранить их полностью, если сами входные точки расположены почти на одной линии или распределены неравномерно.

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

Постройте триангуляцию Делоне из любого набора 2D-точек и наблюдайте за её формированием, с цветовой кодировкой по качеству треугольников. Оцените свойство пустой окружности, наложите двойственную диаграмму Вороного и изучайте статистику худших углов и вытянутых треугольников — без таблиц и библиотек.

Выберите шаблон:

Ваши точки — по одной x, y на строке Разделители между x и y: запятая, табуляция, точка с запятой, вертикальная черта или пробел. Числа могут включать разделители тысяч (1,234) или европейские десятичные знаки (1.234,56). Строки, начинающиеся с #, игнорируются. До 150 точек.

Окраска треугольников

Описанные окружности

Диаграмма Вороного

Метки точек

Алгоритм Бойера-Ватсона, полностью на стороне сервера — без клиентских библиотек.

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

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

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

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

▲

Закрашенные треугольники: сетка Делоне. В режиме качества зеленый цвет означает правильную форму (большой минимальный угол), красный — узкую форму (малый минимальный угол).

◯

Пунктирные окружности (опционально): описанная окружность каждого треугольника. Согласно свойству Делоне, ни одна входная точка не лежит строго внутри них.

⋯

Оранжевые пунктирные отрезки (опционально): диаграмма Вороного, двойственный граф. Каждая ячейка Вороного содержит часть плоскости, ближайшую к одной из входных точек.

⌬

Толстый синий контур: выпуклая оболочка — внешняя граница триангуляции, образованная только теми ребрами, которые принадлежат одному треугольнику.

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

Тепловая карта качества вместо каркаса Каждый треугольник окрашен в зависимости от его минимального внутреннего угла. Вы сразу видите, какие треугольники имеют правильную форму (зеленые), а какие являются узкими (красными) — именно этот показатель важен для точности построения сеток и интерполяции.

Встроенная двойственная диаграмма Вороного Один переключатель накладывает диаграмму Вороного, вычисленную на основе той же структуры данных. Посмотрите, как триангуляция Делоне и ячейки Вороного представляют собой два взгляда на одну и ту же геометрию.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Это уникальная триангуляция набора двумерных точек, при которой ни одна точка не лежит внутри описанной окружности любого треугольника. Это свойство заставляет алгоритм максимизировать наименьший внутренний угол среди всех возможных триангуляций, создавая треугольники наиболее правильной формы.

Почему триангуляция Делоне важна для построения сеток?

Численные методы, такие как анализ методом конечных элементов, чувствительны к узким треугольникам — они приводят к плохо обусловленным матрицам, медленной сходимости и видимым артефактам. Метод Делоне избегает узких треугольников насколько позволяют входные данные, поэтому он является отправной точкой по умолчанию почти для любого процесса генерации сеток.

Какой алгоритм использует этот генератор?

Инкрементный алгоритм Бойера-Ватсона. Создается супертреугольник, содержащий все входные точки, затем каждая точка вставляется по одной за раз: треугольники, чья описанная окружность содержит новую точку, удаляются, а новые треугольники формируются путем соединения новой точки с каждым ребром границы образовавшейся полости.

Что такое свойство пустой описанной окружности?

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

Как связана диаграмма Вороного?

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

Что считается узким треугольником?

По соглашению треугольник с минимальным внутренним углом менее 20° считается «узким». Треугольник «правильной формы» имеет минимальный угол 30° или выше. Равносторонний треугольник имеет все углы по 60° — это теоретический максимум. Гистограмма и тепловая карта в данном инструменте используют именно эти пороговые значения.

Какой формат входных данных принимает генератор?

Вставьте по одной точке на строку в формате x, y. Среди разделителей: запятая, табуляция, точка с запятой, вертикальная черта или пробел. Числа могут содержать разделители тысяч (1,234) или европейские десятичные запятые (1.234,56). Строки, начинающиеся с #, обрабатываются как комментарии, а полные дубликаты точек объединяются автоматически.

Что такое выпуклая оболочка, показанная на диаграмме?

Толстый синий контур обозначает выпуклую оболочку — самую внешнюю границу триангуляции. Ребра выпуклой оболочки принадлежат ровно одному треугольнику (каждое внутреннее ребро принадлежит двум). Они также являются ребрами Делоне, чьи двойственные ребра Вороного уходят в бесконечность.

Могу ли я скачать диаграмму?

Да. Кнопка «SVG» позволяет скачать четкий векторный файл, который масштабируется до любого размера для печати и отчетов. «PNG» скачивает растровое изображение в разрешении 2× для слайдов и чатов. «Скопировать CSV» копирует структуру по каждому треугольнику (индексы, вершины, углы) и полный список точек в формате CSV.

Сколько точек я могу использовать?

До 150 точек за один раз. Сверх этого алгоритм Бойера-Ватсона на чистом Python начинает занимать заметное время, а изображение SVG становится слишком плотным для чтения. Если вам нужны более крупные сетки, экспортируйте данные в специализированные инструменты, такие как Triangle или scipy.spatial.Delaunay.

Ссылайтесь на этот контент, страницу или инструмент так:

"Генератор триангуляции Делоне" на сайте https://ru.miniWebtool.com/генератор-триангуляции-делоне/ от MiniWebtool, https://MiniWebtool.com/

команда miniwebtool. Обновлено: 2026-05-20

Вы также можете попробовать наш AI Решатель Математических Задач GPT, чтобы решить ваши математические проблемы с помощью вопросов и ответов на естественном языке.