С использованием алгоритма Ллойда для закрепленного разбиения
Я могу использовать алгоритм Ллойда для разделения многоугольника на n многоугольников. Предположим, я разделил многоугольник ниже на 5 многоугольников, используя вышеуказанный алгоритм, и я получаю это: -
Но я хотел сделать фиксированное разбиение, то есть хотел, чтобы каждый подполигон включал хотя бы одну граничную точку, например:
Существуют ли уже доступные модификации алгоритма, которые могут помочь мне достичь этого? Как обеспечить анкеровку?
Было бы очень полезно, если бы вы могли привести некоторые существующие коды Matlab/python, а не псевдокод? Код, который я использовал выше, взят из здесь, который выполняет простую ванильную реализацию.
Не могли бы вы поделиться дополнительной информацией о проблеме, которую вы пытаетесь решить с помощью этого алгоритма? Вам нужна ячейка Вороного каждой точки, чтобы граничить со стороной квадрата на каждом итеративном шаге алгоритма, или вы хотите получить конечный результат со всеми ячейками, граничащими со стороной? Потому что я думал в первом случае, на каждом шаге можно добавить одну из вершин внутренней ячейки к диаграмме Вороного, пересчитать ее и потом объединить внутреннюю ячейку с ячейкой новой точки и объявить ее новой, увеличенной ячейка внутренней точки.
Если второй сценарий более актуален, то вы можете поместить на квадрат потенциальную функцию, градиент которой при добавлении к обновлению каждой точки на шаге алгоритма немного изменит итеративную динамику, так что область в середине квадрат отталкивает точки, отталкивая их к сторонам квадрата, а стороны слегка удерживают точки внутри квадрата.
Я хочу получить конечный результат со всеми ячейками, граничащими со стороной
Ответы 1
Просто предложение: простая попытка. Определите потенциальную функцию U(x, y) на квадрате. Somethingтак. Можно подобрать параметры так, чтобы его минимум был кругом, то есть почти кругом, вписанным в квадрат. Или не стесняйтесь выбирать другой потенциал. Учитывая точки p1 = [x1; y1], p1 = [x1; y1], ... pn = [xn; yn], формируя матрицу 2 x n
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 x n GRAD.
Таким образом, ваш алгоритм на самом деле будет композицией
P_out = LA(GR(P_in));
Может быть, тогда точки будут благоприятствовать периферии квадрата, избегая средней части, и, таким образом, в конечном итоге клетки Вороного будут касаться границы? Я выбрал потенциал с предположением, что в этом случае поле векторного градиента является безвихревым, поэтому не будет возникать какая-то циркуляционная динамика, а алгоритм будет сходиться к некоторой центроидальной равновесной конфигурации (звучит правдоподобно, но я не уверен в это).
Может быть достаточно просто инициализировать точки на границе. Вы также можете проверить, какая ячейка нарушает ограничение, и переместить точки ближе к ближайшей границе, пока ячейка не коснется ее. Однако не уверен, что это сойдется к чему-то разумному.