Плотная упаковка ортогональных форм

Question

Это проблема городского планирования.

Я пытаюсь упорядочить несколько прямоугольных зданий заданного размера в пределах партии, чтобы углы зданий всегда находились на максимальном расстоянии D от других зданий и чтобы было как можно меньше «потерянного» пространства.

Есть ли алгоритм закрытой упаковки, который я могу использовать для этой цели? Применим ли алгоритм Воронай в какой-либо форме?

Спасибо за внимание.

Answer 1

Это требование

углы здания всегда находятся на максимальном расстоянии D от других зданий

можно изменить, увеличив внешние границы каждого прямоугольника на реброшириной D / 2.Это оставляет вас со стандартной проблемой упаковки 2D полосы.Здесь

http://www.devx.com/dotnet/Article/36005

вы найдете хорошую статью о том, как атаковать такого рода проблемы, включая примеры программ (C #, VB.NET).Вот статья в Википедии

http://en.wikipedia.org/wiki/Bin_packing_problem

, которая тоже может вам немного помочь.