Эффективный алгоритм поиска точки, не затронутой набором прямоугольников

Question

Ввод: набор прямоугольников в пределах области (0, 0) - (1600, 1200).

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

Какой эффективный алгоритм для этого? Единственные два, о которых я могу думать сейчас:

• Создайте массив логических выражений 1600x1200. Выполните итерацию по области каждого прямоугольника, помечая эти биты как True. Повторяйте в конце и найдите бит False. Проблема в том, что это тратит впустую память и может быть медленным.
• Произвольная итерация по точкам. Для каждой точки выполните итерацию по прямоугольникам и посмотрите, содержит ли какой-либо из них эту точку. Вернуть первую точку, которую не содержит ни один из прямоугольников. Проблема в том, что это очень медленно для густонаселенных экземпляров проблемы.

Почему я это делаю? Это не для домашней работы или для соревнования по программированию, хотя я думаю, что более сложная версия этого вопроса была задана за один раз (у каждого прямоугольника был свой «цвет», и вы должны были вывести цвет из нескольких точек, которые они дали вам). Я просто пытаюсь программно отключить второй монитор в Windows, и у меня возникают проблемы с более вменяемым подходом . Поэтому моя цель - найти свободное место на рабочем столе, затем смоделировать щелчок правой кнопкой мыши, а затем смоделировать все щелчки, необходимые для его отключения, в окне свойств дисплея.

Answer 1

Для каждого прямоугольника создайте список трасс вдоль горизонтального направления. Например, прямоугольник 100x50 сгенерирует 50 прогонов по 100. Запишите их с их крайней левой координатой X и координатой Y в список или карту.

Сортировка списка, сначала Y, затем X.

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

Когда вы найдете первый прогон, который не растянулся на весь экран, все готово.

Answer 2

• Сортировка всех X-координат (начало и конец прямоугольников), а также 0 и 1600, удаление дубликатов.Обозначим это Xi (0 <= i <= n). </li>
• Сортировка всех Y-координат (начало и конец прямоугольников), а также 0 и 1200, удаление дубликатов.Обозначим это Yj (0 <= j <= m). </li>
• Создайте сетку * m с заданными значениями Xi и Yj из предыдущих точек, это должно быть намного меньше, чем исходное значение 1600x1200 (если у вас неттысячи прямоугольников, в этом случае эта идея не применяется).Каждая точка в этой сетке отображается в прямоугольнике исходного изображения 1600 x 1200.
• Нарисуйте прямоугольники в этой сетке: найдите координаты прямоугольников в наборах с первых шагов, закрасьте в сетке.Каждый прямоугольник будет на форме (Xi1, Yj1, Xi2, Yj2), поэтому вы рисуете в маленькой сетке все точки (x, y) так, что i1 <= x <i2 && j1 <= y <j2. </li>
• Найдите первую неокрашенную ячейку в сетке, возьмите любую точку из нее, например, центр.

Примечание. Предполагается, что прямоугольники имеют вид: (x1, y1, x2,y2), представляющий все точки (x, y), такие что x1 <= x <x2 && y1 <= y <y2. </p>

Nore2: Наборы Xi и Yj могут храниться в отсортированном массиве или дереведля доступа O (log n).Если количество прямоугольников велико.

Answer 3

• Я бы выделил изображение в моей любимой графической библиотеке и разрешил рисовать прямоугольники.
• Вы можете сначала попробовать версию в низком разрешении (с уменьшением в 8 раз), которая будет работать, если есть область не менее 15x15. Если это не удастся, вы можете попробовать высокое разрешение.
• Используйте Windows HRGN (Region в .net). Они были изобретены для этого. Но это не языковая независимость нет.
• Наконец, вы можете сделать вычитание прямоугольника. Единственная проблема заключается в том, что вы можете получить до 4 прямоугольников каждый раз, когда вычитаете один прямоугольник из другого. Если есть много маленьких, это может выйти из-под контроля.

P.S .: Рассмотрите возможность оптимизации для максимизированных окон. Тогда вы можете сказать, что нет пикселей, видимых без проверки нажатия.

Answer 4

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

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

Answer 5

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

Если вы действительно хотите сделать более умный подход, вы можете просто рассмотреть прямоугольники. Начните с прямоугольника с углами (0,0), (1600,1200) = (lx, ly), (rx, ry) и «вычтите» первое окно (wx1, wy1) (wx2, wy2).

Это может генерировать не более 4 новых «еще доступных» прямоугольников, если оно полностью содержится в исходном свободном прямоугольнике: (например, все 4 угла нового окна содержатся в старом), они (lx, ly) - (rx, wy1), (lx, wy1) - (wx1, wy2), (wx2, wy1) - (rx, wy2) и (lx, wy2) - (rx, ry). Если только один угол окна перекрывается (только один угол находится внутри свободного прямоугольника), он разбивает его на два новых прямоугольника; если сторона (2 угла) выступает в нее, она разбивается на 3; и если нет перекрытия, ничего не меняется. (Если все они выровнены по осям, у вас не может быть 3 углов внутри).

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

Вероятно, это будет медленнее, чем любой из описанных выше подходов на основе графических библиотек, но было бы интереснее написать:)

Answer 6

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

Зависимым от языка решением является использование Area (Java) .

Answer 7

Если вам известны минимальные размеры x и y прямоугольников, вы можете использовать первый подход (двумерный массив логических значений) с использованием меньшего количества пикселей.

Примите во внимание, что 1600x1200 меньше 2M пикселей.Это действительно так много памяти?Если вы используете bitvector, вам нужно только 235 тыс.

Answer 8

Это простое решение со сложностью 1600 + 1200, оно похоже на концепцию создания матрицы 1600x1200, но без использования всей матрицы:

1. Начните с двух логических массивов W [1600] и H [1200], для которых установлено значение true.
2. Затем для каждого видимого прямоугольника окна с диапазонами координат w1..w2 и h1..h2 отметьте W [w1..w2] и H [h1..h2] как false.
3. Чтобы проверить, находится ли точка с координатами (w, h) в пустом пространстве, просто проверьте, что (W [w] && H [h]) == правда