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

[slavav]

Грань принадлежит графу Делоне только тогда, тогда внутренность её описанной окружности не пересекается с исходным множеством точек. Если точки в общем положении (никакие четыре не лежат на одной окружности), то граф Делоне является триангуляцией. Иначе не обязательно.
Пример: произвольное множество точек на окружности порождает граф Делоне из единственной грани - выпуклого многоугольника вписанного в окружность. На этом же множестве точек можно построить несколько триангуляций Делоне (любая триангуляция - триангуляция Делоне в этом случае).

[Munin]

А, спасибо. В общем случае, можно спать спокойно :-)

[Andrey_Kireew]

slavav хотелось бы уточнить ещё один момент. Сообщите пожалуйста, если не сложно, после выполнения релаксации Ллойда гарантируется ли сохранение условия Делоне для исходной триангуляции. Или же сетку каждый раз нужно перестраивать. Интуиция мне подсказывает, что должно сохраняться, но точно я не уверен.

[slavav]

Нет не гарантируется. Пример тут: https://en.wikipedia.org/wiki/Lloyd%27s_algorithm
Сравните картинки для итераций 1 и 2. На итерации 1 левая верхняя ячейка имеет трёх соседей. На итерации 2 - только двух. Структура диаграммы Вороного изменилась. Соответственно поменяется и структура триангуляции Делоне.
Сетку надо перестраивать каждый раз. Но есть способы делать это быстро если учесть что граф Делоне "мало" поменяется при перемещении одной точки.

[Andrey_Kireew]

Большое спасибо slavav!

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

Если Вас не затруднит, ответьте пожалуйста ещё на один вопрос. При перестройке сетки я ищу "неправильные" треугольники путём сравнения расстояния от центра описанной окружности до всех узлов сетки (если хотя бы один узел попадает внутрь описанной окружности - значит условие Делоне нарушено). Потом я меняю диагональ у пары смежных треугольников и таким образом улучшаю сетку. Есть ли гарантия, что я получу триангуляцию Делоне после первого прохода. Т.е. не могут ли после некоторых "флипов" появиться новые "плохие" треугольники, которые придётся перестраивать ещё 1 раз, а может и не один?

[slavav]

Алгоритм edge-flip может занять экспоненциальное время.
Отсутпление в сторону: "неправильные" треугольники искать не надо. Это долго. Надо искать "нелегальные" рёбра. "Нелегальным" называется ребро между двумя треугольниками, такое, что эти треугольники образуют выпуклый четырёхугольник и окружность описанная вокруг одного треугольника содержит этот четырёхугольник. Этот тест делается за константное время. Можно показать, что последовательно устраняя нелегальные рёбра вы придёте к триангуляции Делоне. За экспоненциальное время в худшем случае.
Я бы предложил посмотреть на рандомизированый алгоритм построения триангуляции Делоне. В его основе перестроение триангуляции при добавлении новой точки. В вашей задаче если вы желаете подвинуть точку, то делаете это в два шага: удаляете точку (и перестраиваете триангуляцию) и добавляете точку в новом месте (и перестраиваете триангуляцию). В среднем это отнимет у вас логарифмическое время на одну точку. Но может оказаться и быстрее, особенно когда вы уже близки к финальной конфигурации.
Или стисните зубы и перестраивайте триангуляцию после того как подвинули все точки.

[Andrey_Kireew]

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

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

Чтобы быстро искать рёбра нужно ещё построить матрицу смежности, которая в каждой строке содержит номера двух смежных треугольников. Тогда да, число сравнений будет только в 1.5 раза больше числа треугольников, а не $o(N^2)$ как у меня. Но эту матрицу нужно ещё как то построить, я пока не соображу как эффективно это сделать исходя из матрицы триангуляции, каждая строка которой содержит ссылки на координаты узлов соответствующего ей треугольника.

Предложенный Вами вариант

Цитата:

рандомизированый алгоритм построения триангуляции Делоне

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

Ответ на второй вопрос не внушает оптимизма, получается нет никаких гарантий, что после 1-го прохода edge-flip будет получена триангуляция Делоне. Просто с каждым новым проходом число "неправильных" треугольников (или "нелегальных" рёбер) будет уменьшаться

[slavav]

Рёбра против треугольников: Прошу прощения. Мои ответы предполагали другую структуру для триангуляции, не список треугольников. Это мы уже обсуждали раньше.

Рандомизированный алгоритм один из самых быстрых (я имею в виду константу). Для переноса $N$ точек он потратит $N\log N$ операций. Это тоже самое что построить триангуляцию с нуля. Но большинство переносов точек не будет менять триангуляцию. Такие переносы потребуют константное время на точку. Можно предположить, что в конце работы алгоритма вы будете тратить $N$ операций на перенос $N$ точек. Это даст заметный выигрыш.

Edge-flip: к сожалению количество "нелегальных" рёбер может расти во время работы алгоритма. Для доказательства его завершения используется другой полуинвариант - занимательный, но сложный.

[Andrey_Kireew]

Наконец то реализовал алгоритм:
после каждой релаксации Ллойда строится новая триангуляция Делоне (функция delaunay из matlab).

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

Так, что какой из этих методов лучше - однозначно сказать нельзя, всё зависит от приложения.

Кроме всего прочего, обнаружилась одна неприятность:
Хотя про метод Ллойда сказано, что он не запутывает сетку, я обнаружил такую вещь. Если число внутренних узлов велико и некоторые из них расположены близко от границы, то центры описанных окружностей некоторых треугольников выходят за пределы границы расчётной области. Эти треугольники с каждой новой релаксаций прижимаются к границе и в конце концов вырождаются. Если продолжить итерации, то число конечных элементов сетки уменьшается, внутренние узлы попадают на границу, а потом, часть внутренних узлов выходит за границу и весь процесс терпит неудачу.

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

вот пример исходной триангуляции


а вот, что с ней стало после 10 релаксаций Ллойда


Один узел вышел за пределы границы, некоторые приграничные треугольники совсем "сплющились"

[slavav]

Здорово, что вы реализовали алгоритм. Хорошая работа.

Отказ от гарантии: в этой области я уже не специалист. Всё ниже - только моё мнение.

Про "выдавливание" узлов: нет гарантии что узел останется в пределах выпуклой оболочки. Центроид замкнутой ячейки Вороного может находится вне оболочки, что приведёт к "выдавливанию". Чтобы этого не было нужно чтобы расстояния между вершинами на границе не были больше расстояний между вершинами внутри. Это примерный критерий.
С другой стороны, можно выбрасывать точки которые "выдавлены" или подобрались близко к границе. В результате вы получите действительно равномерную сетку с почти правильными треугольниками.