Неевклидовы дистанционные диаграммы Вороного

Question

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

Чтение учебникаЯ сталкивался с примером диаграммы Вороного, где сайты на 2D-плоскости представляют футболистов, и если мяч оказался в области Вороного определенного игрока, это означало, что он должен идти к нему, так как он ближе всего к нему.Теперь, что если вместо того, чтобы просто учитывать евклидово расстояние между игроками, мы также учитываем их скорость: более быстрые игроки имеют большую ячейку Вороного.

Может ли тот факт, что мы потеряем пополам, разрушить структуру самой диаграммы Вороного?

Answer 1

Взгляните на Диаграммы мощности и Весовые диаграммы Вороного .Это обобщенные диаграммы Вороного с весами (радиус круга в случае диаграмм мощности), ассоциированными с каждым участком.

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

В случае футболистов, новыйФункция расстояния от точки p до места p_i со скоростью игрока v_i равна:

d(p, p_i) = EuclideanDistance(p, p_i) / v_i

, что можно лучше интерпретировать как время, необходимое для достиженияточка, если игрок бежит со скоростью v_i.Это может привести к диаграммам, подобным этому, где отображаемые числа являются весами 1/v_i: