У меня есть прямоугольная плоскость целочисленной размерности. Внутри этой плоскости у меня есть набор непересекающихся прямоугольников (целочисленной размерности и с целочисленными координатами).
Мой вопрос в том, как я могу эффективно найти обратное этому набору; то есть части плоскости, не входящие в подпрямоугольник. Естественно, этот набор точек образует набор прямоугольников --- и именно они меня интересуют.
Мое текущее, наивное решение использует логическую матрицу (размер плоскости) и работает, устанавливая точку i, j равняется 0, если он содержится в подпрямоугольнике, и 1 в противном случае. Затем я перебираю каждый элемент матрицы, и если это 1 (бесплатная) попытка «вырасти» прямоугольник наружу от точки. Уникальность не имеет значения (подойдет любой подходящий набор прямоугольников).
Существуют ли какие-либо алгоритмы, которые могут решить такую проблему более эффективно? (То есть, без необходимости прибегать к логической матрице.