Давно уже задавали здесь такую задачу, но к решению так и не пришли. Есть сплошные полигоны с целочисленными значениями атрибута. Необходимо слить полигоны в меньшее число полигонов так, чтобы у новых больших полигонов было примерно равное суммарное значение атрибута.
Прилагаю картинку с изображением задачи.
Подскажите, пожалуйста, возможное решение или хотя бы свои мысли по этому поводу
Слияние соседних полигонов с равным суммарным значением атрибута
-
- Новоприбывший
- Сообщения: 1
- Зарегистрирован: 06 фев 2023, 19:34
- Репутация: 0
- Откуда: Вологда
-
- Гуру
- Сообщения: 4064
- Зарегистрирован: 15 окт 2010, 08:33
- Репутация: 1061
- Ваше звание: программист
- Откуда: Казань
Re: Слияние соседних полигонов с равным суммарным значением атрибута
задачка довольно стандартная (так, например, в штатах формируют избирательные округа из переписных кварталов). Но постановка задачи слишком мутная, поскольку должны быть заданы критерии оптимальности - число или площадь итоговых полигонов, компактность (например близость к окружности или квадрату), желаемая сумма значений, и т.д., иначе тривиальным решением является объединение всех полигонов в один. Еще многое в методе решения зависит от числа исходных полигонов.
Решения однозначного у таких задач обычно нет, и решаются они стохастическим методом типа artificial annealing. Начальное приближение строится исходя из критерия оптимальности, а потом поехали перекидывать полигончики соседям. Толковому программисту нужно будет недели две-три на прикидку (формат данных, построение матрицы или графа соседства, начальное приближение, методика перекидки частей соседям, формулирование энергии и процедуры "отжига"), потом как повезет, но обычно работает достаточно хорошо, параметры клиент обычно доводит сам под свою задачу. Либо искать готовое, это проще и дешевле (если найдется).
Решения однозначного у таких задач обычно нет, и решаются они стохастическим методом типа artificial annealing. Начальное приближение строится исходя из критерия оптимальности, а потом поехали перекидывать полигончики соседям. Толковому программисту нужно будет недели две-три на прикидку (формат данных, построение матрицы или графа соседства, начальное приближение, методика перекидки частей соседям, формулирование энергии и процедуры "отжига"), потом как повезет, но обычно работает достаточно хорошо, параметры клиент обычно доводит сам под свою задачу. Либо искать готовое, это проще и дешевле (если найдется).
Кто сейчас на конференции
Сейчас этот форум просматривают: нет зарегистрированных пользователей и 3 гостя