Vemmy Mar 24 2019 at 13:44

Алгоритм триангуляции Делоне методом заметающей прямой

7 min

59K

Programming*Algorithms*

Tutorial

+25

Comments 19

sshikov Mar 24 2019 at 14:34

Для тех, кто не совсем в теме (а я думаю таких не мало), тут не хватает описания цели. Т.е. для чего вообще все это нужно.

Vemmy Mar 24 2019 at 14:52

Согласен, это действительно стоит добавить в рассказ. Спасибо

a-l-e-x Mar 25 2019 at 00:01

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

Rhombus Mar 25 2019 at 13:51

Например используется для построения сеток при расчетах методом конечных элементов. Я так волноводы рассчитывал.

UFO just landed and posted this here

freeExec Mar 24 2019 at 14:52

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

Vemmy Mar 24 2019 at 15:30

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

AngReload Mar 25 2019 at 08:09

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

AngReload Mar 25 2019 at 07:20

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

Vemmy Mar 25 2019 at 13:40

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

Zenitchik Mar 25 2019 at 15:04

А как можно обобщить его на сферу? Расширяющимся кругом (пересечением с равномерно движущейся плоскостью)?

wataru Mar 25 2019 at 15:54

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

a-l-e-x Mar 25 2019 at 18:42

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

Vemmy Mar 25 2019 at 21:30

Да, я еще в статье подметил, что алгоритм работает в режиме оффлайн, то есть все точки должны быть добавлены до начала работы алгоритма. Тут это очень существенно, все верно. Если точек не так много, и изменения редкие, то можно и заново перестроить

0serg Mar 25 2019 at 23:58

Соответственно предлагается хранить ребро с двумя вершинами в множестве и выполнять поиск по ребру (упорядоченной паре вершин).

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

А вообще по названию я подумал что речь идет о Fortune's algorithm. Он строит дуальную диаграмму Вороного и работает за гарантированные nlog(n). В правильно выбранной структуре данных типа DCEL дуальный граф строится тривиально за (n) шагов. Он тоже сравнительно простой. Более сложные варианты строят Делоне за n log(log(n)) в среднем (и nlog(n) в худшем) случае.

DimaTheGreat Mar 31 2019 at 12:13

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

wataru Mar 31 2019 at 13:31

Будет ли работать алгоритм для структурированного множества точек, например, для матрицы NxN?

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

Vemmy Mar 31 2019 at 12:28

Спасибо за замечания, я их прокомментирую:
1. Да, описанный в статье метод хранения триангуляции не самый удобный в использовании, но он однозначно задает триангуляцию. За один проход по множеству из ребер с «противолежащими» точками можно без проблем преобразовать триангуляцию в удобный вид, что работает O(N). Лишь бы памяти хватило во время перестроения.
2. Если смотреть на конечный результат, то он, конечно, единственный и не зависит от алгоритма. А вот по ходу построения действительно в алгоритме из статьи строятся длинные узкие треугольники, которые быстро перестраиваются. Это важное замечание, потому что точность может пострадать.
3. Не очень понял, что подразумевается под структурированным множеством точек

DimaTheGreat Apr 3 2019 at 13:23

например:

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);
	}
}

Show the best of all time