Эквивалент алгоритма Ллойда, использующего исключительно триангуляцию Делоне.

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

Для этой части существует большое количество алгоритмов, которые могут это сделать.

Вторая часть, которую я хочу реализовать, состоит в том, чтобы выполнить релаксацию точек, т. е. позволить им смещаться в 2D-пространстве, чтобы они были одинаково удалены друг от друга.

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

Любые намеки на тип алгоритма, который мне нужен?

Заранее спасибо!


algorithm geometry delaunay
person Treebranch    schedule 26.10.2015    source источник

Ответы (2)


arrow_upward
-1
arrow_downward

Вы можете попробовать взвешенную триангуляцию Делоне. Сначала вычислите нормальную триангуляцию Делоне и центр тяжести для каждого треугольника. Затем вычислите взвешенную триангуляцию Делоне с весами из первой триангуляции. Это помогает сгладить сетку.

person Gigamegs    schedule 26.10.2015
comment
Не могли бы вы указать, как определить веса триангуляции? Спасибо! - person Treebranch; 27.10.2015
comment
@Treebranch: Вот еще: wikihow.com/Calculate -центр тяжести-треугольника. Но я думаю, вам нужен только вес. Может быть, каким-то образом преобразовать центр тяжести в число/вес. ИМО, вы можете использовать площадь треугольника:mathgoodies.com/lessons/vol1/area_triangle. html!!!!!!!!!!! - person Gigamegs; 27.10.2015

arrow_upward
1
arrow_downward

Если у вас уже есть доступ к триангуляции Делоне, то вы также — неявно — имеете представление о диаграмме Вороного.

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

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

person Darren Engwirda    schedule 26.10.2015