Инвертирование набора прямоугольников на 2D-плоскости

Question

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

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

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

Существуют ли какие-либо алгоритмы, которые могут решить эту проблему более эффективно? (Т. Е. Без необходимости прибегать к булевой матрице.

Answer 1

Да, это довольно просто я ответил почти идентичный вопрос о SO раньше, но не смог найти его еще

в любом случае, по существу, вы можете сделать это:.

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

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

Answer 2

Я подозреваю, что вы можете куда-то добраться, заказав прямоугольники по y-координате и используя метод сканирования. Я могу или не могу фактически реализовать реализацию.

.

Answer 3

Это относительно просто, потому что ваши прямоугольники не пересекаются. Цель состоит в основном в наборе непересекающихся прямоугольников, которые полностью покрывают плоскость, некоторые обозначаются как оригинальные, а некоторые обозначаются как «обратные».

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

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

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

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

Детали в качестве упражнения для читателя ;-)

Answer 4

Вы должны взглянуть на алгоритмы пространства заполнения. Эти алгоритмы являются tyring, чтобы заполнить заданное пространство некоторыми геометрическими фигурами. Не следует пытаться модифицировать такой алгоритм в соответствии с вашими потребностями.

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

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

Вот site с алгоритмом, который может быть полезен.

Answer 5

Хорошо! Первая реализация! (Java), основанный на @Paul's ответ:

List<Rectangle> slice(Rectangle r, Rectangle mask) 
{ 
     List<Rectangle> rects = new ArrayList(); 

     mask = mask.intersection(r); 

     if(!mask.isEmpty()) 
     { 
       rects.add(new Rectangle(r.x, r.y, r.width, mask.y - r.y)); 
       rects.add(new Rectangle(r.x, mask.y + mask.height, r.width, (r.y + r.height) - (mask.y + mask.height))); 
       rects.add(new Rectangle(r.x, mask.y, mask.x - r.x, mask.height)); 
       rects.add(new Rectangle(mask.x + mask.width, mask.y, (r.x + r.width) - (mask.x + mask.width), mask.height)); 

       for (Iterator<Rectangle> iter = rects.iterator(); iter.hasNext();) 
         if(iter.next().isEmpty()) 
           iter.remove(); 
     } 
     else rects.add(r); 

     return rects; 
} 

List<Rectangle> inverse(Rectangle base, List<Rectangle> rects) 
{ 
     List<Rectangle> outputs = new ArrayList(); 
     outputs.add(base); 

     for(Rectangle r : rects) 
     { 
       List<Rectangle> newOutputs = new ArrayList(); 

       for(Rectangle output : outputs) 
       { 
         newOutputs.addAll(slice(output, r)); 
       } 

       outputs = newOutputs; 
     } 
     return outputs; 
} 

Возможно рабочий пример here