Слияние соседних полигонов с равным суммарным значением атрибута

Вопросы по свободной ГИС QGIS. Сообщения об ошибках, предложения по улучшению, локализация.
Ответить
nikpolit
Новоприбывший
Сообщения: 1
Зарегистрирован: 06 фев 2023, 19:34
Репутация: 0
Откуда: Вологда

Слияние соседних полигонов с равным суммарным значением атрибута

Сообщение nikpolit » 06 фев 2023, 20:19

Давно уже задавали здесь такую задачу, но к решению так и не пришли. Есть сплошные полигоны с целочисленными значениями атрибута. Необходимо слить полигоны в меньшее число полигонов так, чтобы у новых больших полигонов было примерно равное суммарное значение атрибута.
Прилагаю картинку с изображением задачи.

Изображение

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

gamm
Гуру
Сообщения: 4046
Зарегистрирован: 15 окт 2010, 08:33
Репутация: 1050
Ваше звание: программист
Откуда: Казань

Re: Слияние соседних полигонов с равным суммарным значением атрибута

Сообщение gamm » 07 фев 2023, 18:27

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

Решения однозначного у таких задач обычно нет, и решаются они стохастическим методом типа artificial annealing. Начальное приближение строится исходя из критерия оптимальности, а потом поехали перекидывать полигончики соседям. Толковому программисту нужно будет недели две-три на прикидку (формат данных, построение матрицы или графа соседства, начальное приближение, методика перекидки частей соседям, формулирование энергии и процедуры "отжига"), потом как повезет, но обычно работает достаточно хорошо, параметры клиент обычно доводит сам под свою задачу. Либо искать готовое, это проще и дешевле (если найдется).

Ответить

Вернуться в «QGIS»

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 14 гостей