используя алгоритм Ллойда для привязанного разделения - PullRequest
Новая
       77

используя алгоритм Ллойда для привязанного разделения

1 голос
/ 27 мая 2019

Я могу использовать алгоритм Ллойда для разбиения многоугольника на n многоугольников. Предположим, я разделил указанный ниже многоугольник на 5 многоугольников, используя приведенный выше алгоритм, и я получил это: -

enter image description here

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

enter image description here

Существуют ли уже модификации алгоритма, которые могут помочь мне достичь этого? Как обеспечить крепление?

Было бы очень полезно, если бы вы могли привести некоторые существующие коды Matlab / python вместо псевдокода? Код, который я использовал выше, взят из здесь , что делает простую ванильную реализацию.

1 Ответ

1 голос
/ 05 июня 2019

Просто предложение: простая попытка.Определите потенциальную функцию U(x, y) на квадрате.Нечто подобное . Вы можете выбрать параметры таким образом, чтобы его минимум представлял собой круг, почти равный кругу, вписанному в квадрат.Или не стесняйтесь выбирать другой потенциал.С учетом точек p1 = [x1; y1], p1 = [x1; y1], ... pn = [xn; yn], образующих матрицу 2 xn 

P = [p1 p2 ... pn];

, пусть функция для одного шага алгоритма Ллойда будет 

P_out = LA(P_in)

, т.е. с учетом точек P_in = [p1_in p2_in ... pn_in] она генерирует ихДиаграмма Вороного, затем вычисляется центроид каждой ячейки Вороного p1_out, p2_out, ..., pn_out и перемещается входные точки к новому выходу, точки центроида P_out = [p1_out p2_out ... pn_out].
Затем вы можете применить перепозиционирование вдоль минус-градиента потенциала, т.е. 

function  P_out = GR(P_in)
   P_out = P_in - gradU(P_in); 
end

где GRAD = gradU(P_in) - это функция, которая вычисляет векторы градиента для каждого вектора-столбца P_in(:,j) и создает 2-граничную матрицу GRAD градиентов.

Таким образом, ваш алгоритм на самом деле будет композицией 

P_out = LA(GR(P_in));

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

...