Перемещение точек в триангуляции Делоне

Я только что закончил реализацию алгоритма инкрементного переворачивания Делоне. Этот алгоритм имеет временную сложность O(N log N).

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

Теперь мне нужно решить следующую задачу:

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

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

Спасибо!


optimization algorithm computational-geometry voronoi delaunay
person Valentina Ramirez    schedule 11.01.2016    source источник
comment
Непонятная проблема. Все области Вороного вместе взятые покрывают всю плоскость (или любую другую область в ней, которую они должны покрыть). Общая площадь фиксирована, однако вы перемещаете точки.   -  person n. 1.8e9-where's-my-share m.    schedule 11.01.2016
comment
dma.fi.upm.es/mabellanas/ антенны/aratm/memoria/doc_archivos/   -  person Valentina Ramirez    schedule 11.01.2016
comment
@н.м. это написано на испанском dma.fi.upm. es/mabellanas/antenas/aratm/memoria/Objetivo.html   -  person Valentina Ramirez    schedule 11.01.2016
comment
Похоже, цель состоит в том, чтобы сделать области ячеек как можно ближе друг к другу. Что именно это означает, до сих пор неясно, но вы можете, по крайней мере, сделать обоснованные предположения. Вы могли бы, например. минимизировать стандартное отклонение.   -  person n. 1.8e9-where's-my-share m.    schedule 11.01.2016
comment
@н.м. цель состоит в том, чтобы максимально соответствовать площади близлежащих регионов. Но я не могу найти никакого алгоритма, чтобы сделать это   -  person Valentina Ramirez    schedule 11.01.2016
comment
... con el objetivo de igualar lo más posible el área de sus regiones de proximidad Для меня это звучит так, как будто площади ячеек Вороного должны быть равны, если это возможно. Возможно, вам может помочь ограниченный вариант [алгоритма Ллойда] (con el objetivo de igualar lo más posible el área de sus regiones de proximidad).   -  person M Oehm    schedule 11.01.2016

Ответы (1)


arrow_upward
2
arrow_downward

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

person Gigamegs    schedule 11.01.2016
comment
www.wikihow.com/Вычисление центра гравитации треугольника - person Gigamegs; 11.01.2016
comment
Спасибо!, а что будет, если область вороного не треугольник? - person Valentina Ramirez; 11.01.2016
comment
Триангуляция Вороного двойственна триангуляции Делоне. Ребра Вороного вне выпуклой оболочки обычно бесконечны. ИМО это не нужно или не является частью вашего вопроса. - person Gigamegs; 11.01.2016
comment
Итак, если я получаю центр масс треугольника в триангуляции Делоне, то у меня есть центр масс одной области в диаграмме Вороного - person Valentina Ramirez; 11.01.2016
comment
Нет. VD — это ребро, ближайшее к сайту, чем к любому другому сайту. Об алгоритме Ллойда:www-cs-students. stanford.edu/~amitp/game-programming/ - person Gigamegs; 11.01.2016
comment
@ValentinaRamirez: Вы можете найти центр тяжести ячейки Вороного, усредняя центры тяжести всех треугольников, состоящих из ребер Вороного и опорной точки, взвешенных по их площади: cogV = sum(cog[i] * area[i]) / area[i] - person M Oehm; 11.01.2016
comment
@MOehm: Хотите уточнить? - person Gigamegs; 11.01.2016
comment
@Phpdevpad: разработать что? Это было просто (возможно, бесполезное) замечание, но что произойдет, если область Вороного не будет треугольником? - person M Oehm; 11.01.2016
comment
@MOehm:sum(cog[i]*area[i]) — это сумма всех треугольников из ячейки Вороного!? Что такое area[i] и почему это знаменатель? - person Gigamegs; 11.01.2016
comment
@MOehm Какова площадь [i] в ​​знаменателе? Индекс i находится в сумме или снаружи? и спасибо! - person Valentina Ramirez; 11.01.2016
comment
Хорошо, опечатка: в знаменателе должно быть sum(area[i]). area[i] — площадь каждого треугольника. cog[i] — это центр тяжести для каждого треугольника по приведенной выше ссылке. Извините, если я вас смутил; Я думал, что вычисление COG было проблемой. В противном случае алгоритм Ллойда прост, если у вас уже есть код триангуляции Вороного. - person M Oehm; 11.01.2016
comment
@ValentinaRamirez: Если мой ответ полезен, пожалуйста, примите его и/или проголосуйте за него. ТЫ! - person Gigamegs; 11.01.2016
comment
@ValentinaRamirez: Также стоит упомянуть, что минимальное остовное дерево является подмножеством триангуляции Делоне. - person Gigamegs; 12.01.2016