Skip to content

Van10000/tdd

 
 

Repository files navigation

##Идея алгоритма: Для того, чтобы поместить следующий прямоугольник, выполняем следующие действия:

  • Рассматриваем все точки на карте, являющиеся вершинами некоторого прямоугольника.
  • Для каждой такой точки - пробуем добавить новый прямоугольник с вершиной в этой точке.
  • Для этого просто за линию пробегаемся по всем прямоугольникам и проверяем на пересечение с текущим.
  • Из всех прямоугольников, которые удалось разместить таким образом выбираем ближайший к центру и размещаем его.

##Сложность алгоритма:

  • Требуется расположить n прямоугольников.
  • Для каждого выполним O(n^2) операций, так как рассмотрим O(n) точек - вершин уже расположенных прямоугольников, и для каждой такой вершины попробуем поставить прямоугольник и проверить за O(n), что он не пересекается с остальными.

Итоговая оценка - O(n^3)

##Примеры сгенерированных изображений:

Одинаковые прямоугольники

Случайные прямоугольники

Случайные длинные прямоугольники

Большие прямоугольники

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • C# 100.0%