Я обычно использую QGIS. Я объясняю свою проблему на примере: есть лес (неправильная геометрия1) и одно дерево (geomery2). Я хочу знать максимальное количество деревьев, которое может содержать лес. Кроме того, я хочу получить шейп-файл с лучшим расположением этих деревьев в лесу.
gencirclesinpolys (Generate Circles In Polygons)
инструмент, который может быть полезен.Ответы:
Попробуйте это приложение онлайн svgnest.com/
шаги: 1. svg создает файл (как на рисунке 1); 2. Перейдите по ссылке и загрузите svg; 3. Выберите мышью контейнер многоугольника; 4. начать
после нескольких итераций вы можете заблокировать и загрузить файл SVG (см. рисунок 2)
NB: многоугольник и круги должны быть в одном файле SVG
источник
Интересная проблема!
Я сделал то же самое с неправильными полигонами (в этом случае здания были упакованы так, чтобы не перекрываться)
Используются postgresql и postgis, и python. Грубый алгоритм был
Я не могу гарантировать, что это даст глобальный оптимум, для этого вам понадобится алгоритм «круговой упаковки» (как уже упоминали другие).
Это будет продолжаться вечно, поэтому вам нужно будет добавить код, чтобы решить, когда выйти, например
Согласно Circle Packing в Википедии, наилучшая плотность упаковки достигается с помощью шестиугольной сетки. Может быть возможно создать такую сетку, используя MMQGIS, чей интервал зависит от размера ваших деревьев, которые, как я полагаю, идентичны. Затем поместите дерево в каждую вершину. Но тогда у вас есть проблема, чтобы узнать, где разместить сетку, чтобы максимизировать количество деревьев.
источник