Задача: рисовать в некой области случайные непересекающиеся квадраты.
Очевидное решение - сгенерировать координаты очередного квадрата и проверить их на пересечение с каждым уже существующим квадратом. Соответственно, когда квадратов становится много, это решение дает понять, что оно не является оптимальным. :)
Кто-нибудь может предложить что-то более интересное?
Поддерживать в актуальном состоянии набор пустых выпуклых областей. После добавления очередного квадрата в какую-то пустую область, заменить эту область подходящими кусками меньшего размера.
Области можно организовать в R-дерево, чтобы быстро искать свободное место.
Например, как рисуем очередной квадрат: выбираем случайную точку. Находим по дереву ближайшую область S. Если точка не в S, придумываем какой-нибудь трюк, чтобы получить точку в S (ну нарисуем диаметр области, проведенный через точку и циклически так отразим её на другой конец области по этому диаметру :)). Получив точку, назовём её центром квадрата (или пусть будет верхним левым углом) и достроим квадрат на основе случайных угла поворота и длины стороны (с ограничением, чтоб не вылезти за пределы области).
Из-за последнего ограничения квадрат не совсем случайный. Но можно искать недостающее пространство опять же по дереву и заимствовать площадь.
А вообще с R-деревом ваш метод не так уж и плох. Надо проиндексировать квадраты и переодически переиндексировать, т. к. при динамическом добавлении квадратов R-дерево деградировать начнёт. При попадании точки в квадрат, отчеканить её за границы квадрата. Затем найти ограничение - максимальный свободный круг с центром в найденной случайной точке, случайно выбрать длину диагонали (половина которой ограничена радиусом окружности) и угол поворота и построить квадрат.