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

Question

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

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

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

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

Answer 1

Идея, может прийти к югу от п^2 в зависимости от того, как прямоугольники расположены:

Вычислить возможную область в явном виде.

Структура данных, представляющая его, представляет собой список неперекрывающихся субрегионов, каждый из которых является треугольником (если вы приближаетесь к кругу) или «громоздким треугольником» (где одна сторона может быть сегментом круга) ,

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

Возможно, это может случиться, если количество жизнеспособных субрегионов может быть небольшим в любой момент времени. Обработка пары прямоугольников и субрегионов имеет верхнюю границу O (1), поэтому, если мы ожидаем m субрегионов, которые будут волнообразными O (nm). Вероятно, это может быть намного хуже, чем O (n^2) в худшем случае (скажем, много непересекающихся прямоугольников, полностью содержащихся в круге), но в вашем типичном случае (большие прямоугольники, малый круг) есть вероятность, что количество субрегионов не будет, t растет очень высоко, и тогда это будет «почти O (n)».

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

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