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

Question

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

Радиус круга, размер и форма области задаются произвольно. Область должна быть покрыта как можно меньшим количеством кругов. Круги могут перекрываться.

Есть ли алгоритм, который справится с этим?

Answer 1

Надеюсь, я правильно понял ваш вопрос ...

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

Примечание: это похоже на плотную упаковку атомов в элементарной ячейке .

РЕДАКТИРОВАТЬ: Мой предыдущий метод охватывает как можно большую часть области, без наложения. Если допускается перекрытие, то (я считаю, что) следующий метод будет охватывать всю область с минимальным перекрытием.

Как вы, вероятно, знаете, существует только 3 тесселяции двумерного пространства с правильными многоугольниками - с использованием квадратов, треугольников или шестиугольников. Стратегия состоит в том, чтобы создать мозаику с использованием одного из этих многоугольников, а затем описать окружность для каждого многоугольника. При использовании этого метода шестиугольник будет растрачивать минимальную площадь.

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

Примечание: Эрик Бейнвилл предложил аналогичный метод.

-- Flaviu Cipcigan

Answer 2

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

1. мои входные данные были радиус круга в метрах и координаты границ области
2. сначала я нашел прямоугольник границ, покрывающий данную область
3. затем, начиная с левого нижнего края, я перемещаю точку на расстояние, равное двойной высоте треугольника, использованного для построения шестиугольника (его сторона равна радиусу моего круга), и с учетом 0 градусов по формулам Винсенти
4. для каждой найденной точки я проверяю, пересекается ли она с моей областью ввода, сохраняю ли я ее, иначе пропускаю
5. когда я добрался до края, я сделал еще одну проверку, чтобы убедиться, что я получу все очки в пределах
6. Я смещаю точку на 60 градусов, проверяю ее, затем на 120 градусов, проверяю снова
7. вернитесь к 3-му шагу, но теперь я перемещаю точки на 180 градусов
8. и край снова еще одна проверка, а затем как в шаге 6, но сначала 120 градусов, затем 60 градусов
9. продолжайте, пока не дойдете до верхнего края прямоугольника

Как и на данном изображении, конечно, вы можете увеличить точность, уменьшив радиус круга

Я знаю, что это не лучший вариант, но он работает для меня очень хорошо.

Надеюсь, это вполне понятно и поможет любому.

Answer 3

Я знаю, что вопрос требует алгоритма, но у меня была похожая проблема, чтобы покрыть США кружками, и я быстро нашел решение, используя этот бесплатный онлайн-инструмент . Поэтому я смиренно предполагаю, что если площадь и радиус не меняются, это можно сделать примерно через 3 минуты. Очевидно, что этот ответ не является обобщенным, но часто проблемы не таковы.

Answer 4

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