Как стать автором
Обновить

Комментарии 19

Для тех, кто не совсем в теме (а я думаю таких не мало), тут не хватает описания цели. Т.е. для чего вообще все это нужно.
Согласен, это действительно стоит добавить в рассказ. Спасибо
Не могу написать за автора, но я использовал триангуляцию Делоне в 1994 — 96 годах для построения модели поверхности (земли) по оцифровке геодезических карт. Это использовалось для нахождения тальвигов и водоразделов, что требовалось для вычисления рангов рек, и площадей водсборов. чтобы оценить аллювиальные отложения. Если я правильно помню терминологию, и идею…
Например используется для построения сеток при расчетах методом конечных элементов. Я так волноводы рассчитывал.
Как вариант. Построение расчетных сеток для МКЭ/CFD/прочих программ использующих численные методы.

В условиях говорилось про отсутствие точек в окружности, но не одной картинки с окружностями я не увидел

Есть такое. Я рассчитывал на то, что их можно примерно представить. Хотя на картинках около места, где я это упомянул, стоит добавить пару окружностей. Займусь

Для каждого треугольника можно построить окружность проходящую через его точки. Внутри окружностей не должно быть других точек.
Delaunay circumcircles vectorial

Жалко, что код не опубликовали.
А не думали об похожем алгоритме, но для точек в трёх измерениях с тетраэдрами?

Добавил ссылку на репозиторий с кодом, нужно было хотя бы комментариев добавить)
Вообще про три измерения следующие мысли: если сортировать вдоль прямой, то последняя добавленная точка останется видимой, от нее можно будет легко найти видимые грани, как в алгоритме заворачивания подарка для выпуклой оболочки 3D, рекурсивно и без проверки всех граней, а только смежных (и то, сразу не очевидно, может быть даже этот шаг уже будет выполняться в худшем случае суммарно за O(N^2)). Далее нужна стереометрия, чтобы понять, верны ли аналоги утверждений из 2D случая. Если это так, то алгоритм вполне переносится на большую размерность
А как можно обобщить его на сферу? Расширяющимся кругом (пересечением с равномерно движущейся плоскостью)?

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

Насколько я понимаю, одной из особенностей данного алгоритма является необходимость сортировки точек перед расчётом. У этого дела, на мой взгляд, есть недостаток — не понятно как посторить итерационный процесс — сделал триангуляцию, нашел места, где невязка слишком большая, добавил там точек, обновил триангуляцию… В случае пресортировки — триангуляция каждый раз считается заново… Но может быть так всё равно будет лучше, так как есть оценка сверху.
Да, я еще в статье подметил, что алгоритм работает в режиме оффлайн, то есть все точки должны быть добавлены до начала работы алгоритма. Тут это очень существенно, все верно. Если точек не так много, и изменения редкие, то можно и заново перестроить
Соответственно предлагается хранить ребро с двумя вершинами в множестве и выполнять поиск по ребру (упорядоченной паре вершин).

Это вариация на тему которая обычно называется half-edge или doubly-connected edge list (DCEL).

А вообще по названию я подумал что речь идет о Fortune's algorithm. Он строит дуальную диаграмму Вороного и работает за гарантированные nlog(n). В правильно выбранной структуре данных типа DCEL дуальный граф строится тривиально за (n) шагов. Он тоже сравнительно простой. Более сложные варианты строят Делоне за n log(log(n)) в среднем (и nlog(n) в худшем) случае.
Автору спасибо за статью. Однако, хочу добавить свои <5 копеек>:
1. Для большинства реальных задач (численных методов и инженерных расчетов), помимо списка ребер, нужен список элементов (треугольник --> индексы трех вершин), а также матрица жесткости (треугольник --> соседние треугольники с общими ребрами).
2. Далее, на практике нужно стремиться, чтобы триангуляция была как можно однороднее, т.е. размер (площадь) и форма (углы) треугольников была бы примерно одинаковы. Критично избегать элементы с острыми углами (<30 град).
3. Будет ли работать алгоритм для структурированного множества точек, например, для матрицы NxN?
Будет ли работать алгоритм для структурированного множества точек, например, для матрицы NxN?

Там много групп из 4-х точек на одной окружности, поэтому ответ будет не единственным, так что какие диагонали в квадратах будут взяты зависит от реализации. Но ответ будет корректным. Однако, для такого набора точек нет смысла гонять общий алгоритм, можно триангуляцию захардкодить и построить вообще за O(n).

Спасибо за замечания, я их прокомментирую:
1. Да, описанный в статье метод хранения триангуляции не самый удобный в использовании, но он однозначно задает триангуляцию. За один проход по множеству из ребер с «противолежащими» точками можно без проблем преобразовать триангуляцию в удобный вид, что работает O(N). Лишь бы памяти хватило во время перестроения.
2. Если смотреть на конечный результат, то он, конечно, единственный и не зависит от алгоритма. А вот по ходу построения действительно в алгоритме из статьи строятся длинные узкие треугольники, которые быстро перестраиваются. Это важное замечание, потому что точность может пострадать.
3. Не очень понял, что подразумевается под структурированным множеством точек
например:
delta = 0.1; x0 = 0.0; x1 = 1.0; y0 = 0.0; y1 = 1.0;
nx = round( (x1 - x0) / delta); 
ny = round( (y1 - y0) / delta);
points.shrink_to_fit();
for (int i = 0; i < nx; ++i){
	double y = y0 + i*delta;
	for (int j = 0; j < nx; ++j){
		double x = 0.0 + j*delta;
		points.emplace_back(x, y);
	}
}

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.