Приблизительный многоугольник с несколькими кругами

Question

Справочная информация. Мне нужно проводить рекламные кампании в Google, ориентированные на полигон. Я получаю этот регион (который на самом деле является областью, где люди могут быстро получить доступ через транспорт (например, автомобиль) к объекту, для которого мы проводим кампанию). В объявлениях Google, которые не поддерживают таргетинг на область многоугольника, мы можем нацеливать только на группу кругов.

Поэтому я подумал о приближении многоугольника с кругами (что в моем понимании было бы «вписано» или «вписано»). круги этого многоугольника).

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

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

Существует ли какой-либо теоретический алгоритм или какая-либо его реализация, какой-либо пакет, или я ошибаюсь из-за того, что мне нужно решить мою проблему с геотаргетингом в Google Ads?

Answer 1

Единственное решение, которое я нашел (на реализацию которого у меня ушло 2 дня), это создать с помощью turfjs ограничивающий прямоугольник вокруг моего многоугольника, затем создать сетку квадратов (turf.squareGrid), а затем превратить его в матрицу, заполненную либо 0или информация о квадрате. Затем рекурсивная функция находит самый большой квадрат в этой матрице, затем следующий и т. Д., Пока все квадраты не станут эквивалентными или большими квадратами. Затем я сделал круги вокруг этих больших квадратов (с радиусом, равным sqrt(2) (~1.41) * (perimeterOfABigSquare / 2).