Задача разместить квадраты в замктнутом полигоне

[rhot]

Есть большой, неправильной формы, полигон. Требуется разместить n-нное количество квадратов 1х1 км так чтобы они не выходили за границы полигона.

Встречал кто-нибудь функцию/инструмент, которая бы это выполняла?

[gamm]

Есть большой, неправильной формы, полигон. Требуется разместить n-нное количество квадратов 1х1 км так чтобы они не выходили за границы полигона.

Встречал кто-нибудь функцию/инструмент, которая бы это выполняла?

делал когда-то подобную мульку. Это классический алгоритм "укладки рюкзака", он же "раскройки шкуры".

Можно сделать "жадный" (субоптимальный) алгоритм, для начал построив "ядро" (эдакий буфер, но внутрь), радиусом половина стороны (здесь могут располагаться центры), сделать регулярную сетку (центров квадратов) с шагом стороны, вписать ее в это ядро ("подвигав" туда-сюда), двигая и сетку, и ряды/строки (тут какая-нибудь стохастика сгодится). Как-то так.

В ГИС есть подобные алгоритмы размещения не перекрывающихся меток

P.S. непонятно, что такое n-нное, я привел алгоритм для максимизации числа квадратов. Если n задано, то просто выбираем случайно узлы вписанной сетки

[gimran]

Квадратная сетка в итоге или "замостить квадратами по максимуму"?
Можно сгенерировать регулярную сетку, а затем линии в полигоны.
PS. Если не секрет, строите сеть регулярного мониторинга?

[ Сообщение с мобильного устройства ]

[rhot]

Да, число квадратов задаю я.

Замостить по максимуму, делаю обычный разовый сэмплинг.

[gamm]

1) Да, число квадратов задаю я.
2) Замостить по максимуму, делаю обычный разовый сэмплинг.

(1) и (2) несовместимы, это разные задачи ...

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

[rhot]

почему же?

[gamm]

почему же?

потому, что разные - либо вы число знаете заранее (например, три), либо "по максимуму"

[rhot]

тогда да, число заранее известно

[Игорь Белов]

В QGIS получается так.

Нам понадобится контур полигона. Создадим его заранее:
[Vector] → [Geometry Tools] → [Polygons to lines]

Построим сетку квадратов, используя размеры полигона в качестве шаблона:
[Vector] → [Research Tools] → [Vector grid] : "Output grid as polygons"
Можно подвигать квадраты вверх-вниз и вправо-влево.

Выделим пересечение квадратов с полигоном:
[Vector] → [Research Tools] → [Select by location] : "creating new selection"

Снимем выделение с квадратов, пересекаемых контуром:
[Vector] → [Research Tools] → [Select by location] : "removing from current selection"

Готово! Осталось сохранить выборку.

[gimran]

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

[ Сообщение с мобильного устройства ]

[Игорь Белов]

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

Виноват, был невнимателен, проскочил вопросы-ответы в середине обсуждения.