Как покрыть множество кругов на плоскости непересекающимися кругами постоянного радиуса?

Question

Итак, у вас есть лист / область заданного размера, и внутри этой области есть отверстия (их центральная точка (x, y) и радиус указаны). Проблема в том, что вы должны закрыть эти отверстия патчами. Эти круглые пятна имеют фиксированный радиус (т. Е. Радиус 5) и не могут перекрываться друг с другом (но могут касаться). Вам разрешено использовать столько, сколько вам нужно, цель не в том, чтобы найти наиболее оптимальное число, а в том, чтобы увидеть, можно ли закрыть каждую дыру.

Я решил аналогичную проблему с деревом KD, но из-за трехмерного характера отверстий в этой задаче я не уверен, как к нему подойти. Просто ищу указатель в правильном направлении, а не кодированное решение:)

Answer 1

В зависимости от размеров патчей и отверстий решение может не быть.

Решение с массивом самых компактных патчей:

Нет решения, потому что отверстие больше, чем пятна, что позволяет открывать участки:

Нет решения, потому что отверстия слишком близко:

Для общей конструкции вы начинаете с патча с центром в отверстии. Затем переведите и поверните (вокруг центра непрерывного участка) участок, как требуется:

Answer 2

Вы, вероятно, ищете аналитическое или хотя бы детерминированное решение для этого.Но я боюсь, что это слишком сложно, чтобы иметь один. Метаэвристика , как EA s, с другой стороны, может справиться с такого рода проблемами из-за их стохастической природы.Вы должны изменить свою проблему на задачу оптимизации , когда вы решите принять такой подход.

Я пытался решить эту проблему, используя базовую форму DE алгоритм .Чтобы определить задачу оптимизации, я предположил, что вектор решения - это массив 2*N переменных с плавающей запятой, где N - количество дырок.Этот массив представляет X и Y координаты патчей, так как N патчи необходимы не более, чтобы покрыть N дыр.

Функция стоимости (которая необходима для минимизации) определяется какследует:

Find closest patch to each hole
Find A1 as sum of uncovered areas of holes by their closest patchs
Find A2 as sum of intersection areas of active(!) patches
return max(A1, A2)

В этой функции активный патч - это патч, ближайший к хотя бы одному отверстию.Это определение добавлено к проблеме, чтобы охватить ситуацию, которую вы упомянули в своем комментарии к ответу Ripi2 (когда патч закрывает две дыры, так что есть другой патч, который бесполезен).Для большей наглядности предположим, что есть патч P1, который не является ближайшим ни к одному из отверстий.H1 является ближайшим отверстием к этому патчу, но его ближайший патч - P2.Таким образом, мы можем с уверенностью сказать, что площадь пересечения H1 и P1 меньше или равна области пересечения H1 и P2.Поскольку это верно для ближайшего отверстия, оно будет таким же для всех остальных отверстий, поэтому давайте подумаем, что оно не существует!

Это пример:

Просто имейте в виду, что эти алгоритмы никогда не гарантируют нахождения глобального оптимума, однако они дадут [набор] неоптимальных решений под рукой.