Полагаю, вы можете найти a точку в пространстве на территории. Назовите это Z. (Так как у вас есть несколько городов, вы можете выбрать среднее местоположение города как центральное.)
Учитывая исходную точку Z, я хотел бы создать набор лучей наружу из этой точки, причем каждый луч имеет нижнюю и верхнюю границу размера, а число увеличивается, чтобы получить детализацию. Я набросал схему ниже. Ничего об этом не проверено; не стесняйтесь предлагать улучшения.
Каждый луч представлен углом тета и имеет начало Z. Вместо одной длины у каждого луча есть две связанные длины, внутренняя и внешняя, с которыми мы собираемся сходиться. Начальное значение Inside установлено равным 0, а outside - значением, превышающим радиус любой возможной территории («Горизонт»); мы сжимаем Снаружи, пока он не окажется внутри территории, и будем расти Внутри, пока он не окажется совсем за пределами территории, используя бинарный поиск (log2 N в диаметре вашего игрового пространства). Мы также собираемся увеличить количество лучей по мере расширения конечных точек, чтобы получить детализацию границ территории. Предполагается, что конечным результатом будет набор лучей, которые устанавливают границу вокруг территории, конечные точки которой не более чем «расстояние» друг от друга.
Вы можете начать с одного луча (тета = север (0), внутри = 0, снаружи = горизонт).
Давайте назовем набор лучей R. Предположим, что набор лучей R отсортирован по тета,
и если у нас есть луч r от R, то следующим (r) будет следующий луч в отсортированном множестве,
со следующим (r) для последнего луча в R, являющегося первым лучом в наборе. поскольку
Вы знаете городские локации, вы можете посеять сет лучами, в которых города - это точки внутри.
Это должно работать в любом случае.
Дополнительный параметр «Порог» дает вам степень точности вашего ответа.
R = empty
add_to_R(0,0,Horizon)
repeat until done
done = true
for each ray r in R
guess = average(Inside(r),Outside(r))
if guess>threshold
then done = false
if interritory(Z+(Theta(r),guess))
then Inside(r)=guess
else Outside(r)=guess
for each ray r in R
if (distance(Inside(r),Inside(next(r)))> spacing
then add_to_R(average(Theta(r),Theta(next(r)),
min(Inside(r),Inside(next(r)),
max(Outside(r),Outside(next(r))
end
Эксплуатационная стоимость должна составлять 2 при максимальном диаметре территории, при этом множитель должен иметь отношение к окружности территории, деленной на выбранный интервал конечной точки луча.
Эта схема не идеальна; он потерпит неудачу в присутствии полуостровов территории, где луч пересечется, если не взять пробы на полуострове. Если полуострова произвольно тонкие, для их обнаружения потребуется произвольно много образцов. Возможно, вы можете выбрать минимальную ширину полуострова, а затем настроить алгоритм на шаг наружу, когда он, наконец, найдет сходящийся луч, по ширине полуострова, чтобы убедиться, что он не дурак.