У меня есть слой многоугольника, который описывает ограничение; Я хочу добавить очки в этой области. Я хочу добавить как можно больше точек, но между ними должно быть минимальное расстояние. Возможно ли это сделать с помощью ГИС?
Чтобы уточнить, было бы лучше, если бы была сгенерирована упорядоченная сетка, так как это гарантировало бы наибольшее количество баллов. Однако ограничение редко позволяло бы это, и может быть предпочтительным удалить точки, чтобы смещение лучше соответствовало ограничению.
Ответы:
Я думаю, что это можно рассматривать как проблему «упаковки».
Если это так, вы можете попробовать Генетический алгоритм, возможно, такой же, как в О генетических алгоритмах для упаковки полигонов .
источник
Я не знаю ни одного инструмента ГИС для этого, но у меня есть идея по алгоритму.
Во-первых, аппроксимация максимального числа точек может быть получена с помощью этой формулы:
(где
Aплощадь многоугольника иdминимальное расстояние).Затем, чтобы попытаться расположить эти точки в многоугольнике, лучшим шаблоном является не квадратная сетка, а шестиугольная сетка. Видеть:
Наконец, некоторые методы оптимизации с использованием моделей силы могут быть использованы для уточнения относительного расположения точек.
NB: Это хорошо известная проблема в кристаллографии .
источник
Смотрите ветку по адресу /math/15624/distribute-a-fixed-number-of-points-uniformly-inside-a-polygon . В частности, обратите внимание на ссылку (в комментарии) на «процесс Пуассона» и выполните поиск в Интернете. Связь с текущим вопросом заключается в том, что, когда вы можете равномерно распределить определенное количество точек, вы можете систематически увеличивать это количество до тех пор, пока в многоугольник не будет добавлено больше точек, и это решит проблему максимизации числа точек, подверженных требование минимального расстояния. (Технически, две проблемы - это проблемы двойной оптимизации, когда цели и ограничения взаимозаменяемы.)
источник
Решение должно быть равносторонними треугольниками, http://en.wikipedia.org/wiki/Equatell_triangle . Единственный вопрос - это длина сторон и "смещение по оси x" относительно вашего многоугольника.
(аналогично гексагональной сетке, упомянутой ниже)
источник