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

Ответ 1

Это можно сделать легко, используя формулу union-intersection (размер объединения 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).

Ответ 2

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

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

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

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

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

В этом методе много сказано:

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

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

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

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

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

Ответ 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 шага.

Ответ 4

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

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

Ответ 5

T = общая площадь таблицы.

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

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

Площадь для вычисления = T - (C - V)

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

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

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