Почему важно свойство пустой описанной окружности?

Триангуляция является Делоне тогда и только тогда, когда описанная окружность каждого треугольника не содержит других сайтов. Этот критерий максимизирует минимальный угол среди триангуляций множества точек и помогает избегать «тощих» треугольников в сетках.

Как Вороной и Делоне двойственны?

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

Что делает Бойер–Уотсон при добавлении точки?

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

Delaunay & Voronoi

Bowyer–Watson triangulation and dual Voronoi tessellation; click to add seeds, drag to move.

О модели

Для множества семян на плоскости диаграмма Вороного относит каждую точку плоскости к ближайшему семени, а триангуляция Делоне соединяет семена, чьи ячейки Вороного имеют общее ребро — эквивалентно треугольникам, чьи описанные окружности пусты от других семян. Симулятор строит триангуляцию инкрементальным алгоритмом Бойера–Уотсона и рисует двойственную диаграмму Вороного. Клик добавляет новые семена, перетаскивание двигает их; сетка и ячейки обновляются вживую. Модель — евклидова геометрия ближайших соседей на плоскости без взвешенных сайтов Вороного, constrained-триангуляций и кривых метрик. Добавляйте и двигайте точки, чтобы видеть перестроения по критерию пустой описанной окружности и изменение границ ячеек.

Для кого: Вычислительная геометрия, генерация сеток, ГИС и курсы алгоритмов среднего уровня.

Ключевые понятия

Триангуляция Делоне
Диаграмма Вороного
Алгоритм Бойера–Уотсона
Описанная окружность
Тесселяция
Ближайший сосед

Как это работает

The Voronoi diagram of N seeds partitions the plane into cells of points closer to seed i than to any other. Its dual graph is the Delaunay triangulation: connect two seeds whenever their Voronoi cells share an edge. Delaunay maximises the minimum angle of all triangles (no other triangulation does as well) and has the empty-circumcircle property — toggle the option to verify that no other seed lies inside any circumcircle. Implemented with the Bowyer–Watson incremental algorithm.

Основные формулы

V(sᵢ) = { x : ‖x − sᵢ‖ ≤ ‖x − sⱼ‖ ∀ j }

Delaunay edge ⇔ V(sᵢ) and V(sⱼ) share an edge

empty-circle: no seed is strictly inside circumcircle of any triangle

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

Почему важно свойство пустой описанной окружности?: Триангуляция является Делоне тогда и только тогда, когда описанная окружность каждого треугольника не содержит других сайтов. Этот критерий максимизирует минимальный угол среди триангуляций множества точек и помогает избегать «тощих» треугольников в сетках.
Как Вороной и Делоне двойственны?: Каждое ребро Делоне соответствует двум соседним ячейкам Вороного; вершины Вороного лежат в центрах описанных окружностей треугольников Делоне. Одна структура определяет комбинаторику другой.
Что делает Бойер–Уотсон при добавлении точки?: Он находит треугольники, чьи описанные окружности содержат новый сайт, удаляет их и заново триангулирует образовавшуюся дыру к новой точке — восстанавливая свойство Делоне инкрементально.

Другие симуляторы в этой категории — или все 85.

Вся категория →

НовоеУниверситет / научные

Слизевик Physarum (агенты)

Запустить симулятор

~4500 агентов следуют за отложенным хемоаттрактантом: депозит + диффузия + распад + три сенсорных луча — самоорганизуются в сетки путей.

НовоеШкольные

Сглаживание Савицкого–Голэя

Запустить симулятор

Зашумлённый косинус и свёртка SG(7,2) — фильтр лучше сохраняет пики по сравнению с широким прямоугольным окном.

НовоеШкольные

Цепь Маркова (Погода)

Запустить симулятор

Двухсостоянияя цепь Солнце/Дождь: матрица P, стационарное распределение π, эмпирическое и теоретическое.

НовоеШкольные

Градиентный спуск (2D)

Запустить симулятор

Линии уровня функции f(x,y) и траектория (x,y) ← (x,y) − η∇f; чаша или эллиптическая впадина.

НовоеУниверситет / научные

Диаграмма Минковского

Запустить симулятор

Световой конус и повёрнутые оси в 1+1 измерениях; γ от v.

НовоеШкольные

Парадокс близнецов

Запустить симулятор

Мировые линии «туда и обратно»; собственное время τ = T/γ против земного времени T.

Delaunay & Voronoi

О модели

Как это работает

Основные формулы

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

Ещё из «Визуализация математики»

Слизевик Physarum (агенты)

Сглаживание Савицкого–Голэя

Цепь Маркова (Погода)

Градиентный спуск (2D)

Диаграмма Минковского

Парадокс близнецов

Delaunay & Voronoi

О модели

Как это работает

Основные формулы

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