Ищете алгоритм для размещения максимального количества точек в пределах ограниченной области на минимальном расстоянии?

17

У меня есть слой многоугольника, который описывает ограничение; Я хочу добавить очки в этой области. Я хочу добавить как можно больше точек, но между ними должно быть минимальное расстояние. Возможно ли это сделать с помощью ГИС?

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

Мэтью Снейп
источник
1. Да. 2. Хотите случайный или заказанный (сетка)?
Брэд Несом
Кажется, два вопроса. Вы хотите, чтобы алгоритм делал это вне программного обеспечения? Или вы хотите знать, что ГИС-система может сделать это?
Брэд Несом
1
Ограничены ли точки так, чтобы они были> = минимальным расстоянием от границы многоугольника? Если так, то вопрос может быть более четко сформулирован как: Как я могу упаковать максимальное количество кругов в многоугольник?
Кирк Куйкендалл
Как-то связано: gis.stackexchange.com/q/4927/162
Жюльен
1
@qva Нет, нет, потому что точные решения, которые можно найти, асимметричны и их трудно получить даже для простых форм, таких как прямоугольники. Лучшие вычислительные методы, которые я нашел, основаны на пространственном моделируемом отжиге (и они работают очень хорошо, даже если они требуют большого количества вычислений). Используя их, я посмотрел на решения для многих полигонов различной формы. Ясно, что границы многоугольника управляют решениями, близкими к границам; глубоко внутри они имеют тенденцию приближаться к шестиугольным набивкам дисков.
whuber

Ответы:

5

Я думаю, что это можно рассматривать как проблему «упаковки».

Если это так, вы можете попробовать Генетический алгоритм, возможно, такой же, как в О генетических алгоритмах для упаковки полигонов .

Кирк Куйкендалл
источник
Интересная ссылка, спасибо. Быстрый взгляд показывает, что алгоритму статьи нужны полигоны, которые должны быть прямоугольниками. Знаете ли вы, можно ли его обобщить на произвольные многоугольники?
whuber
9

Я не знаю ни одного инструмента ГИС для этого, но у меня есть идея по алгоритму.

Во-первых, аппроксимация максимального числа точек может быть получена с помощью этой формулы:

Nb = 4.A / Pi.d^2

(где Aплощадь многоугольника и dминимальное расстояние).

Затем, чтобы попытаться расположить эти точки в многоугольнике, лучшим шаблоном является не квадратная сетка, а шестиугольная сетка. Видеть:

квадрат против гексагональной сетки

Наконец, некоторые методы оптимизации с использованием моделей силы могут быть использованы для уточнения относительного расположения точек.

NB: Это хорошо известная проблема в кристаллографии .

жюльен
источник
ГИС инструмент, чтобы сделать это ... ian-ko.com гео-мастер случайных точек в многоугольнике.
Брэд Несом
1
Благодарность! Но вопрос не совсем о случайных точках в многоугольнике, верно?
Жюльен
В качестве начального приближения быстро и грязно гексагональная упаковка работает нормально. Хотя это почти никогда не оптимально. Я ожидаю, что потенциальное улучшение будет пропорционально длине периметра многоугольника, поэтому для многоугольных многоугольников это не плохой подход.
whuber
6

Смотрите ветку по адресу /math/15624/distribute-a-fixed-number-of-points-uniformly-inside-a-polygon . В частности, обратите внимание на ссылку (в комментарии) на «процесс Пуассона» и выполните поиск в Интернете. Связь с текущим вопросом заключается в том, что, когда вы можете равномерно распределить определенное количество точек, вы можете систематически увеличивать это количество до тех пор, пока в многоугольник не будет добавлено больше точек, и это решит проблему максимизации числа точек, подверженных требование минимального расстояния. (Технически, две проблемы - это проблемы двойной оптимизации, когда цели и ограничения взаимозаменяемы.)

Whuber
источник
0

Решение должно быть равносторонними треугольниками, http://en.wikipedia.org/wiki/Equatell_triangle . Единственный вопрос - это длина сторон и "смещение по оси x" относительно вашего многоугольника.

(аналогично гексагональной сетке, упомянутой ниже)

Уффе Кусгаард
источник
1
Это верно только в бесконечной плоскости. Граница конечного многоугольника сильно ограничивает конфигурацию. Когда точек много , они приблизительно образуют равносторонние треугольники.
whuber