Граница между местностями местности в 3D стратегии игры

Question

Я хочу создать динамически сгенерированную границу между областями противника на равнинной местности с некоторыми точками («базами») (например, инопланетными и человеческими базами) в трехмерной стратегии. Каждая база имеет свою «страну влияния», поэтому граница должна проходить на соответствующем расстоянии между конфликтующими базами. Если вы играли в Settlers I, II и т. Д., Вам следует понять, что я имею в виду.

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

Пожалуйста, можете ли вы предложить мне какое-либо решение для этого (может быть, некоторые алгоритмы или даже готовые пакеты).

Пример желаемой границы:

Answer 1

Звучит так, как будто вы хотите Диаграмма Вороного . Ниже приведена 2D-диаграмма, но тот же алгоритм работает и в 3D.

Answer 2

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

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

Я предполагаю, что это потому, что самая красная точка северо-западного направления оказывает влияние, как показано стрелкой.

«Обзор», связанный с этой страницы википедии, и результаты поиска изображений Google для взвешенной диаграммы Вороного предполагают, что такого рода влияние, приводящее к границам округления, достижимо, хотя очевидно, что дальнейшие исследования ожидают вы.