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

У меня есть набор прямоугольников, и я хотел бы «уменьшить» набор, чтобы у меня было наименьшее количество прямоугольников для описания той же области, что и исходная установлен. Если возможно, я хотел бы, чтобы это было быстро, но меня больше интересует как можно меньшее количество прямоугольников. Сейчас у меня есть подход, который работает в большинстве случаев.

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

С этим набором из трех прямоугольников правильное решение будет иметь два прямоугольника, например:

Однако в этом случае мой алгоритм начинается с обработки синего прямоугольника. Это расширится вниз и разделит желтый прямоугольник (правильно). Но затем, когда обрабатывается оставшаяся часть желтого прямоугольника, вместо того, чтобы расширяться вниз, он сначала расширяется вправо и забирает часть, которая была ранее отделена. Затем обрабатывается последний прямоугольник, и он не может расширяться вправо или вниз, поэтому исходный набор прямоугольников остается. Я мог бы настроить алгоритм, чтобы сначала развернуть вниз, а затем вправо. Это исправит этот случай, но вызовет ту же проблему в аналогичном сценарии, который был перевернут.

Изменить: Чтобы уточнить, исходный набор прямоугольников не перекрывается и не должен быть соединен. И если подмножество прямоугольников соединено, то в многоугольнике, который их полностью покрывает, могут быть дыры. #include используя пространство имен std; #include #include #include void swap (long a, long b) {...

У меня есть следующий код:

#include "stdafx.h"
#include <iostream>
using namespace std;
#include <conio.h>
#include <cstring>
#include <iomanip>

void swap(long a, long b)
{
    long temp;

    temp=a;
    a=b;
    b=temp;
}
int _tmain(int argc, _TCHAR* argv[])
{
    int x = 5, y = 3;
    cout << x ;
    cout << y << endl;

    swap(x, y);

    cout << x ;
    cout << y << endl;

    getch();
    return 0;
}

Программа выдает результат:

5 3

3 5

Программа фактически меняет местами значения! Это почему? Параметры swap () не являются указателями или ссылками.

(я использую VS 2005)