Я ищу эффективный способ перемещения сотен однородных, возможно пересекающихся квадратов друг от друга, чтобы они больше не пересекались. Полученные новые позиции должны быть как можно ближе к исходным координатам.Решетка для пересечения площади
Есть ли такой алгоритм?
Ввести переменные сдвига Xi +, Xi-, Yi-, Yi- и решить линейную задачу, которая сводит к минимуму сумму переменных при ограничениях, которые выражают неперекрывающееся (Ui + Xi +) - (Uj - Xj-)> = S, (Vi + Yi +) - (Vj - Yj-)> = S или аналогично.
Если вы не знакомы с линейным программированием, вы должны прочитать о: http://en.wikipedia.org/wiki/Linear_programming
никогда ничего подобного не видел. Может быть, аргументы в пользу первой версии проблемы могут помочь. Похоже, он может быть сформулирован как проблема линейного программирования (переменными являются сдвиги). Но что вы подразумеваете под «униформой»? –
Тот же размер/площадь. – quano
См. Также http://stackoverflow.com/questions/6750377/move-rectangles-so-they-dont-overlap – brainjam