1

Задача: рисовать в некой области случайные непересекающиеся квадраты.

Очевидное решение - сгенерировать координаты очередного квадрата и проверить их на пересечение с каждым уже существующим квадратом. Соответственно, когда квадратов становится много, это решение дает понять, что оно не является оптимальным. :)

Кто-нибудь может предложить что-то более интересное?

4
  • Возникает несколько вопросов: какая форма области? Квадраты разного размера? Квадраты могут быть повернутыми?
    – yozh
    26 апр 2011 в 17:15
  • прямоугольная, да, да 26 апр 2011 в 18:34
  • Квадрат в квадрате быть может? 26 апр 2011 в 21:18
  • нет конечно! 27 апр 2011 в 15:46

4 ответа 4

2

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

Области можно организовать в R-дерево, чтобы быстро искать свободное место.

Например, как рисуем очередной квадрат: выбираем случайную точку. Находим по дереву ближайшую область S. Если точка не в S, придумываем какой-нибудь трюк, чтобы получить точку в S (ну нарисуем диаметр области, проведенный через точку и циклически так отразим её на другой конец области по этому диаметру :)). Получив точку, назовём её центром квадрата (или пусть будет верхним левым углом) и достроим квадрат на основе случайных угла поворота и длины стороны (с ограничением, чтоб не вылезти за пределы области).

Из-за последнего ограничения квадрат не совсем случайный. Но можно искать недостающее пространство опять же по дереву и заимствовать площадь.

А вообще с R-деревом ваш метод не так уж и плох. Надо проиндексировать квадраты и переодически переиндексировать, т. к. при динамическом добавлении квадратов R-дерево деградировать начнёт. При попадании точки в квадрат, отчеканить её за границы квадрата. Затем найти ограничение - максимальный свободный круг с центром в найденной случайной точке, случайно выбрать длину диагонали (половина которой ограничена радиусом окружности) и угол поворота и построить квадрат.

1
  • А вообще должно быть простое решение. :) Придумаю - допишу
    – yapycoder
    26 апр 2011 в 18:40
1

При рендеринге сцен с помощью трассировки лучей используют структуру, называемую octtree - т.е. делят пространство на 8 кубов, потом каждый куб на 8 кубов и т.д. Каждый из кубов содержит список объектов, которые в нем находятся (условно). Возможно, Вам поможет аналогичное разбиение на плоскости - 4 квадрата, каждый - еще на 4 и так далее... т.о. есть возможность быстро проверить есть ли в квадрате с выбранной точкой какие-либо сгенерированные объекты и проверить пересечения с ними по одному (т.е. аналогично вашему первому решению, только количество проверяемых объектов будет мало)

0

использовать растр, для складирования форм - а значит возможности проверки... заполнять начиная с больших форм к маленьким...

2
  • используй растр... для накопления результата и как следствие - возможности быстрой проверки...
    – igotm
    28 апр 2011 в 6:37
  • А что это значит? Можно поподробнее? 29 апр 2011 в 8:43
0

Если при описании границы фигуры A есть хоть одна точка, которая лежит на одной прямой между точками границы фигуры B, для которых Направление описание соответственно противоположно, то фигуры пересекаются.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.