Вычислите площадь, покрытую картами, случайно расположенными на столе

Question

Это вопрос собеседования, собеседование завершено.

Учитывая колоду прямоугольных карт, поместите их случайным образом на прямоугольный стол, размер которого намного больше, чем общая сумма размеров карт.Некоторые карты могут случайно совпадать друг с другом.Разработайте алгоритм, который может рассчитать площадь таблицы, покрываемую всеми картами, а также проанализировать временную сложность алгоритма.Все координаты каждой вершины всех карт известны.Карты могут перекрываться по любым схемам.

Моя идея:

Сортировка карточек по убыванию их вертикальной координаты.

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

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

Любая помощь приветствуется.спасибо!

Answer 1

Это можно легко сделать, используя формулу пересечения объединений (размер объединения B B C = A + B + C - AB - AC - BC + ABC и т. Д.) , но это приведет к алгоритму O(n!). Есть еще один, более сложный способ, который приводит к O(n^2 (log n)^2).

---

Храните каждую карту как многоугольник + его область в списке. Сравните каждый многоугольник в списке с каждым другим многоугольником. Если они пересекаются, удалите их обоих из списка и добавьте их объединение в список. Продолжайте, пока полигоны не пересекаются. Суммируйте их площади, чтобы найти общую площадь.

Полигоны могут быть вогнутыми и иметь отверстия, поэтому вычислить их пересечение нелегко. Тем не менее, есть алгоритмы (и библиотеки ) , доступные для вычисления в O(k log k), где k - количество вершин. Поскольку число вершин может быть порядка n, это означает, что вычисление пересечения составляет O(n log n).

Сравнение каждого многоугольника с любым другим многоугольником O(n^2). Однако мы можем использовать O(n log n) алгоритм развертки для поиска ближайших полигонов, что делает общий алгоритм O((n log n)^2) = O(n^2 (log n)^2).

Answer 2

Это почти наверняка не то, что искали ваши интервьюеры, но я бы предложил, просто чтобы посмотреть, что они сказали в ответ:

Я предполагаю, что все карты имеют одинаковый размер и строго прямоугольные, без отверстий, но они расположены случайным образом в смысле X, Y, а также произвольно ориентированы в смысле тета. Поэтому каждая карта характеризуется тройкой (x, y, theta) или, конечно, у вас также есть четверка угловых локаций. С помощью этой информации мы можем довольно просто провести анализ Монте-Карло.

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

Очевидно, что вы можете проверить каждую точку в O (n), где n - количество карт. Тем не менее, есть небольшая хитрая техника, которая, я думаю, применима здесь, и я думаю, что это ускорит процесс. Вы можете распределить по столу соответствующий размер сетки (в зависимости от размера карт) и предварительно обработать карты, чтобы выяснить, в каких сетках они могут находиться. (Вы можете переоценить, предварительно обработав карты как если бы они были круглыми дисками с диаметром, проходящим между противоположными углами.) Теперь создайте хэш-таблицу с ключами в качестве местоположений сетки, а содержимое каждого представляет собой любую возможную карту, которая может перекрывать эту сетку. (Карты появятся в нескольких сетках.)

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

Об этом методе можно сказать очень много:

• Вы можете довольно легко изменить его для работы с непрямоугольными картами, особенно если они выпуклые
• Вероятно, вы можете изменить его для работы с картами разного размера или формы, если вам нужно (и в этом случае геометрия действительно раздражает)
• Если вы проводите собеседование в месте, где проводятся научные или инженерные работы, им это понравится
• очень хорошо распараллеливается
• Это так здорово !!

С другой стороны:

• Это метод аппроксимации (но вы можете использовать его с любой точностью!)
• Вы находитесь в стране ожидаемого времени выполнения, а не детерминированного времени выполнения
• Кто-то может задать вам подробные вопросы о Монте-Карло
• Если они не знакомы с Монте-Карло, они могут подумать, что вы придумываете

Хотел бы я взять кредит на эту идею, но, увы, я взял ее из бумаги, вычисляющей площади поверхности белков на основе положения и размеров атомов в белках. (Та же самая основная идея, за исключением того, что теперь у нас была трехмерная сетка в 3-пространстве, и карты действительно были дисками. Мы проходили и для каждого атома, генерировали группу точек на его поверхности и смотрели, были ли они или нет Интерьер к любым другим атомам.)

РЕДАКТИРОВАТЬ: Мне приходит в голову, что исходная проблема предусматривает, что общая площадь стола намного больше, чем общая площадь карты. В этом случае соответствующий размер сетки означает, что большинство сеток должно быть незанятыми. Вы также можете предварительно обработать местоположения сетки, как только ваша хеш-таблица будет создана, и полностью исключить их, генерируя только точки внутри, возможно, занятых местоположений сетки. (В основном, выполняйте индивидуальные оценки MC для каждого потенциально перекрытого местоположения сетки.)

Answer 3

Вот идея, которая не идеальна, но практически полезна. Вы разрабатываете алгоритм, который зависит от точности измерения epsilon (eps). Представьте, что вы разбили пространство на квадраты размера eps x eps. Теперь вы хотите посчитать количество квадратов, лежащих внутри карт. Пусть количество карточек равно n, а стороны карточек - h и w.

Вот наивный способ сделать это:

S = {} // Hashset
for every card:
   for x in [min x value of card, max x value of card] step eps:
       for y in [min y value of card, max y value of card] step eps:
           if (x, y) is in the card:
               S.add((x, y))
return size(S) * eps * eps

Алгоритм работает в O (n * (S / eps) ^ 2), и ошибка сильно ограничена (2 * S * n * eps), поэтому относительная ошибка не более (2 * eps * n / S).

Так, например, чтобы гарантировать ошибку менее 1%, вы должны выбрать eps меньше, чем S / (200 n), и алгоритм выполняется примерно за 200 ^ 2 * n ^ 3 шагов.

Answer 4

Предположим, есть n карт единичной площади. Пусть T будет площадь стола. Для скрытой проблемы ожидаемая площадь покрытия будет

$ T (1 - ({{T-1} \ over {T}}) ^ n) $

Answer 5

T = Общая площадь стола.

C = Общая площадь, на которую может быть покрыта картами (площадь одной карты, умноженная на количество карт).

V = Общая площадь перекрывающихся карт (V = oVerlap)

Область для расчета = T - (C - V)

Должно быть (да, это опасные слова) некоторыеспособ эффективно проанализировать пространство, занимаемое картами, чтобы легко идентифицировать перекрывающиеся и непересекающиеся ситуации.Определите их, выделите все перекрывающиеся области, и все готово.

Сложность времени заключалась бы в рассмотрении каждой карты по порядку, одна за другой, и сравнении каждой с каждой оставшейся картой (карта 2 уже проверена).против карты 1), что делает ее n !, нехорошо ... но тут-то и возникает "следует". Должен быть какой-то эффективный способ убрать все карты, которые не перекрываются из рассмотрения, чтобы заказать карты, чтобы сделать этоочевидно, если они не могут перекрывать другие / предыдущие карты и, возможно, идентифицировать или группировать потенциально перекрывающиеся карты.

Интересная проблема.