Релаксации Ллойда

[Andrey_Kireew]

Здравствуйте уважеемые участники форума. Недавно наткнулся на информацию про этот метод сглаживания треугольной сетки. Судя по иллюстрациям - работает он очень неплохо, но у меня есть некоторые вопросы:
1. В чём его преимущество перед сглаживанием Лапласса? быстрее ли он сходится, или даёт более качественную сетку? Об этом никакой информации найти не смог.
2. По поводу реализации. Правильно ли я понимаю, что если у меня есть триангуляция Делоне, то диаграмма Вороного мне не нужна в явном виде? Просто нужно найти центры описанных окружностей треугольников (это и есть вершины диаграммы Вороного). Уточнённая позиция узла сетки тогда находится как среднеарифметическое значение координат центров описанных окружностей всех треугольников, примыкающих к данному узлу.

Если я всё понял правильно, то релаксации Ллойда реализуются сложнее сглаживания Лапласса, вопрос в том насколько лучше будет результат, и будет ли вообще он лучше?

Буду благодарен за любую информацию по данному вопросу

[slavav]

1. Не знаю.
2. Правильно реализованная диаграмма Вороного не отличима от графа Делоне. Ищите РСДС (рёберный список с двойными связями) или DCEL (double connected edge list). В нём диаграмма Вороного записывается в виде вершин ($V_v$), рёбер ($E_v$) и граней ($F_v$). В свою очередь граф Делоне записывается как грани ($F_d$), рёбра ($E_d$) и вершины ($V_d$). Между ними есть однозначное соответствие:
$V_v \leftrightarrow F_d$,
$E_v \leftrightarrow E_d$,
$F_v \leftrightarrow V_d$.

[Andrey_Kireew]

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

[slavav]

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

[Andrey_Kireew]

Цитата:

Я хотел только сказать, что диаграмма Вороного и граф Делоне являются двойственными планарными графами

Спасибо, но я об этом осведомлён. К стати триангуляция Делоне не всегда единственна, так что и взаимо однозначное соответствие наблюдпется то же не всегда. Но не суть важно. Вопрос у меня всё больше про релаксации Ллойда. Правильно ли я планирую их реализовать на основе триангуляции Делоне, алгоритм построения для которой у меня уже имеется (не сказать что идеальный, но работает устойчиво. В оригинальном же алгоритме Ллойда используется диаграмма Вороного и я хочу обойтись без её явного построения.

[slavav]

Граф Делоне единственен в отличие от триангуляции. Граф Делоне можно восстановить из триангуляции за линейное время. Диаграмму Вороного (или нужные вам её части) можно восстановить из графа Делоне за линейное время. Алгоритмы несложны но потребуют от вас известной тщательности.
Я не знаю можно ли запустить Ллойда на триангуляции напрямую. Кажется нет, так как надо найти нетреугольные грани графа Делоне.

[Andrey_Kireew]

Вообще то в первом посте п.2. я написал как планирую это сделать.

[slavav]

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

[Andrey_Kireew]

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

[Andrey_Kireew]

Может кому пригодится, нашел в англоязычной Wiki https://en.wikipedia.org/wiki/Lloyd%27s_algorithm (перевод мой, вольный):
В отличие от сглаживания методом Лапласса, в котором узлы перемещаются в барицентры своего ближайшего окружения, алгоритм Ллойда позволяет получать треугольники, более близкие по форме к равносторонним. Кроме того, в отличие от сллаживания Лапласса, релаксации Ллойда никогда не приводят к запутыванию сетки.
Недостаток метода Ллойда - приминимость только к треугольным элементам (сглаживание Лапласса более универсально и применимо к любым сеткам).

Таким образом мои предположения подтверждаются. Для треугольной сетки алгоритм Ллойда - это наилучший вариант (если не учитывать повышенную вычислительную сложность).

Теперь попытаюсь его реализовать по триангуляции Делоне.

[slavav]

Andrey_Kireew в сообщении #1239582 писал(а):

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

В своей цитате я имел ввиду "центров описанных окружностей всех граней графа Делоне ...". Жирным выделены пропущенные слова. Прошу прощения за недоразумение.

[svv]

(Оффтоп)

slavav в сообщении #1239575 писал(а):

Граф Делоне

Le comte Delaunay

[Andrey_Kireew]

Я понял, Вы наверное про тот случай, когда на писанную вокрух треугольника окружность попадают другие узлы. Тогда триангуляция неоднозначна и эти узлы на окружности нужно объединять в полигоны. Это и будут грани графа Делоны, отличающиеся от треугольников. Но мне думается, что среднеарифметическое центров описанных окружностей треугольников как раз и будет центром описанной окружности образованного ими полигона. Так что вычисления наверное дадут тот же самый результат.

[slavav]

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

[Munin]

(Оффтоп)

Andrey_Kireew в сообщении #1239572 писал(а):

К стати триангуляция Делоне не всегда единственна

slavav в сообщении #1239575 писал(а):

Граф Делоне единственен в отличие от триангуляции.

Извините за офтопик, а нельзя ли это пояснить и привести примеры?