Как правильно рассчитать коэффициент полезного использования пространства?

Question

[sirenko]

https://codepen.io/212ww134/pen/ZEPbOdV
Подскажите, пожалуйста,как правильно рассчитать коэффициент полезного использования пространства? Можно использовать только чистый

Answer 1

[Wataru]

Обход в ширину, он же алгоритм заливки: закрасьте на невидимом канвазе или в массиве все блоки, пройдитесь по всей границе канваза/массива, если там непокрашенная точка, то красьте ее и добавляйте ее в очередь. Потом берите из очереди точки и добавляйте в нее 4 соседа, если они еще не покрашены. В конце все непокрашенные пиксели - ваши полости.

Можно ускорить алгоритм сжатием координат: вввпишите все x и y координаты всех углов блоков, отсортируйте и унифицируйте (отдельно по каждой оси). Потом замените все координаты в блоках на порядковый номер в массиве уникальных координат. Примените алгоритм выше, но в конце надо помнить, что каждая ячейка теперь не 1x1, а сколько-то больше по вертикали и горизонтали.

Comments

[sirenko]

спасибо, буду пробовать

[Wataru]

Еще есть метод сканирующей прямой и системы непересекающихся множеств. Работать это все будет где-то за O(n log n), но без хорошего опыта с алгоритмами вы это вряд ли напишите. Но если хотите, могу объяснить.

[sirenko]

Wataru, да, буду очень благодарна))(Это тестовое задание на стажировку. В условии указано, что необходимо решить его максимально простым и оптимальным способом)

[Wataru]

sirenko, увы, при попытке описать метод нашелся косяк. Обход в ширину со сжатием координат быстрее. Это будет O(n^2).

Другой быстрый метод, действительно за n log n: построить граф из линий и обойти все ребра. Что-то вроде этого: e-maxx.ru/algo/facets

Надо построить граф, где вершины - это углы блоков, а ребра - линии между ними. Для этого точки надо отсортировать 2 раза: по x, y а потом по y, x.

Но проблема этого алгоритма, что он не обработает области с дырками, вроде пустоты в которой коробками ограниченна другая область. Это можно обойти, если добавить еще линии на граф. Из каждого левого верхнего угла пустите вверх луч, пока он не пересечет другой блок. Это можно все за n log n сделать методом сканирующей прямой снизу вверх. У вас может начаться луч или встретится нижняя грань блока. Храните лучи в балансированном дереве (set) и при границе отсекайте те лучи, которые с ней пересекаются. В c++ это легко делается через lower_bound у set, в js вам придется писать свое BST похоже.

Лучи, которые не пересеклись ни с чем, надо запомнить.

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

Площадь многоугольника считайте так: https://e-maxx.ru/algo/polygon_area

Это очень сложно релизовать.

[sirenko]

Wataru, ещё раз спасибо) а может как-то помочь замена алгоритма next fit на какой то более подходящий, или не в этом дело?

[Wataru]

sirenko, next fit?

[sirenko]

Wataru, "Next Fit" (или "Next-Fit") - это алгоритм упаковки элементов в ограниченное пространство

[Wataru]

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

Еще, стоит полумать, вдруг в задаче можно класть блоки так, чтобы замкнутых пустот не образовывалось вообще.