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

Это вопрос интервью, интервью было сделано.

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

Моя идея:

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

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

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

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

 Nick Johnson29 мар. 2012 г., 11:32
@ user1002288 Потому что каждый многоугольник можно разложить на треугольники. Это актуально, только если ответ на вопрос Нима состоит в том, что ониМожно вращаться - в противном случае, есть гораздо более простые решения.
 Nemo29 мар. 2012 г., 03:58
Вопрос, в частности, говорит, что таблица «намного больше, чем общая сумма размеров карт». Так что я думаю, что проблема просто просит вас эффективнонаходить перекрывающиеся карты, а затем используйте любой код, который вам нравится, чтобы вычислить их пересечение. (Это нормально для последних, чтобы быть медленным, потому что есть очень очень мало перекрывающихся карт с очень очень высокой вероятностью).
 Nim28 мар. 2012 г., 17:12
все ли они ориентированы одинаково (то есть карты никогда не будут поворачиваться под разными углами и т. д.)?
 Justin Pearce28 мар. 2012 г., 17:37
Вычислите треугольники из вершин карты и вычислите площадь, занимаемую этими треугольниками, с учетом перекрытий.
 user100228828 мар. 2012 г., 18:09
Почему они треугольники? они могут перекрываться любыми шаблонами. Спасибо !

Ответы на вопрос(5)

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

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

 BlueRaja - Danny Pflughoeft28 мар. 2012 г., 19:02
Это не проблема вероятности ожидаемого значения - он спрашивает, как эффективно рассчитатьфактический Площадь покрыта рядом карт.
 Victor Sorokin28 мар. 2012 г., 20:31
Мне нравится такой подход, он намного проще, чем другие предложения. ОП также может попробовать метод Монте-Карло.

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

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

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

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

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

Для этого метода можно многое сказать:

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

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

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

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

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

 Nick Johnson29 мар. 2012 г., 11:35
Очень умно. Мне нравится тот факт, что это намного проще реализовать, чем решения, которые требуют разложения полигонов, при условии, что вы готовы терпеть приближение.

которая не идеальна, но практически полезна. Вы разрабатываете алгоритм, который зависит от точности измерения 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 шагов.

 Stefano Borini28 мар. 2012 г., 18:17
Разве это не базовое радиовещание?
 High Performance Mark28 мар. 2012 г., 19:01
Это не лучевое вещание, это «численная интеграция» или «оценка площади путем подсчета очков». С другой стороны, это также можно назвать радиовещанием.
 Novak28 мар. 2012 г., 21:59
Многие графические методы тесно связаны с методами численного интегрирования. Это одна из них. Когда вы используете точки сетки таким образом, я думаю, что это обычно называется квадратурной техникой. Когда вы используете случайные точки, это Монте-Карло. Монте-Карло будет иметь лучшие свойства сходимости в пространствах более высокой размерности.
 aelguindy28 мар. 2012 г., 18:20
@ StefanoBorini Я не знаю, что такое raycasting, но я был бы удивлен, если бы то, что я описываю, еще не было сделано (и, возможно, тоже получило название) :-).
 Stefano Borini28 мар. 2012 г., 18:31
Вы делите поверхность на клетки, снимаете воображаемый луч из каждого центра клетки и проверяете, есть ли пересечение с объектом или нет. Это техника, используемая для создания изображений с трассировкой лучей (по крайней мере, самые основные из них).
Решение Вопроса

формула пересечения (размер объединения A 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).

 Colonel Panic29 мар. 2012 г., 12:15
Карты выпуклые. Пересечение выпуклых форм является выпуклым. Понял, спасибо.
 Colonel Panic28 мар. 2012 г., 20:11
На первую часть вашего ответа - легко как?
 BlueRaja - Danny Pflughoeft28 мар. 2012 г., 22:54
@Matt: сумма всех карт; вычесть площадь пересечения всех пар; добавить пересечение всех триплетов; вычесть четверки и т. д. На перекрестках не будет отверстий ибыть выпуклымтак что найти ихмного Полегче чем в более сложном случае.

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

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

Площадь для расчета = T - (C - V)

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

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

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

 Philip Kelley28 мар. 2012 г., 18:38
Вот почему вы (мучительно) проходите карточку за карточкой. «Первая» (или самая нижняя) карта покрывает область, в то время как все последующие (составленные) карты, которые перекрывают ее, не перекрывают область, в которой они перекрываются.
 tom1028 мар. 2012 г., 18:26
+1: это в основном правильно, за исключением того, что вычисляет не покрытую площадь, а не покрытую область (тривиальная проблема). V здесь необходимо правильно интерпретировать, так что если две карты перекрываются, вычтите область этого перекрытия один раз, а затем, если надеть третью карту, чтобы точно покрыть это перекрытие, вычтите область перекрытия еще раз, и т. Д. если все карты сложены, C = 52 * A и V = 51 * A, или площадь одной карты, что является правильным.
 BlueRaja - Danny Pflughoeft28 мар. 2012 г., 18:00
Вычисление «общей площади перекрывающихся карт» не работает, поскольку более двух карт могут перекрывать одно и то же пространство. Представьте, например, что все карты находятся в одном и том же месте - тогда «общая площадь перекрывающихся карт» равна площади одной карты! Кроме того, ваша формула явно неверна - представьте, что T очень большой, тоT - (C - V) может быть больше, чемC!!

Ваш ответ на вопрос