Группировка прямоугольников

[Lasor]

Доброго времени.
Появилась инетересная и, на первый взгляд, простая задачка: сгруппировать прямоугольники на плоскости. Известны все координнаты прямоугольников относительно верхнего левого угла изображения.
Под группировкой подразумевается разбиение на отдельные массивы общего массива, в котором и приходят данные по прямоугольникам.
На картинке схематично набросал как могут располагаться сами прямоугольники.

Номера внутри - их номера в массиве.
Есть у кого идеи как их сгруппировать?

[waleri]

Ну, расставьте в круг...

[Lasor]

Сообщение от waleri

Ну, расставьте в круг...

Не понял

[SAMOUCHKA]

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

не понятно по каким параметрам их группировать

[Lasor]

Сообщение от SAMOUCHKA

не понятно по каким параметрам их группировать

По принципу соседей: тех, что находятся радом или по диагогали друг от друга.

[SAMOUCHKA]

Сообщение от Lasor

По принципу соседей: тех, что находятся радом или по диагогали друг от друга.

в смысле имеют общие точки? Тут несколько способов. Гугли заполнение фигуры или как то так.

[phomm]

Вот тема с решением почти той же задачи http://programmersforum.ru/showthread.php?t=169044
Для Вашей задачи только признаки общности задать не из принципа, что индексы в 2мерном массиве "рядом", а координаты углов не больше некоего эпсилона (по картинке - пара пикселей). Ну и паскаль, да.

[Lasor]

Сообщение от phomm

Вот тема с решением почти той же задачи http://programmersforum.ru/showthread.php?t=169044
Для Вашей задачи только признаки общности задать не из принципа, что индексы в 2мерном массиве "рядом", а координаты углов не больше некоего эпсилона (по картинке - пара пикселей). Ну и паскаль, да.

Спасибо за наводку, буду разбираться в том, что там написано.

[Lasor]

Решил по-своему, C++, QT:

/** Формирование регионов из прямоугольников */
void go(QRectWithMarkWithNumber item, std::vector<QRectWithMarkWithNumber> &items, std::vector<std::vector<QRect> > &output)
{
    /** Счётчик областей */
    static int number = 1;
    /** Глубина рекурсии */
    static int depth = 0;
    depth++;
    if ((depth == 1) && (item.rect.width() == 0))
    {
        for (size_t i = 0; i < items.size(); i++)
        {
            if (items[i].mark == false)
            {
                item = items[i];
                break;
            }
        }
    }
    for (size_t i = 0; i < items.size(); i++)
    {
        if (item.rect == items[i].rect)
        {
            items[i].mark = true;
            items[i].number = number;
            continue;
        }
        if (items[i].mark)
        {
            continue;
        }
        if (areNeighbours(item.rect, items[i].rect))
        {
            items[i].mark = true;
            items[i].number = number;
            go(items[i], items, output);
        }
    }
    //***//
    /** Вышли на первый уровень рекурсии */
    if (depth == 1)
    {
        /** Ищем регион номер number */
        std::vector<QRect> out;
        for (size_t i = 0; i < items.size(); i++)
        {
            if (items[i].number == number)
            {
                out.push_back(items[i].rect);
            }
        }
        /** Есть такой */
        if (!out.empty())
        {
            output.push_back(out);
            /** Все элементы в регионах? */
            if (allDone(items))
            {
                depth = 0;
                number = 1;
                return;
            }
            /** Нет, остались */
            else
            {
                item.reset();
                depth--;
                number++;
                go(item, items, output);
            }
        }
        /** Нет такого, выходим */
        else
        {
            depth--;
            return;
        }
    }
    /** Выходим из рекурсии */
    if (depth > 1)
    {
        depth--;
    }
    return;
    //***//
}

/** Структура для хранения данных о прямоугольнике */
struct QRectWithMarkWithNumber
{
    /** Сам прямоугольник */
    QRect rect;
    /** Отметка о соседстве */
    bool mark = false;
    /** Номер региона, в который поместили прямоугольник */
    int number = 0;
    bool operator == (const QRectWithMarkWithNumber& var)
    {
        return ((this->rect == var.rect) && (this->mark == var.mark) && (this->number == var.number));
    }
    /** Сброс параметров прямоугольника */
    void reset()
    {
        rect.setX(0);
        rect.setY(0);
        rect.setWidth(0);
        rect.setHeight(0);
        mark = false;
        number = 0;
    }
};

/** Проверка, являются ли элементы соседями */
bool areNeighbours(QRect rect1, QRect rect2)
{
    if ((rect1.height() != rect2.height()) || (rect1.width() != rect2.width()))
    {
        throw std::invalid_argument("Items size not equal!");
    }
    int deltaX = rect1.x() - rect2.x();
    int deltaY = rect1.y() - rect2.y();
    int height, width;
    height = rect1.height();
    width = rect1.width();
    if (
            ( (deltaX == 0) && (deltaY == -height) ) || //Второй ниже первого
            ( (deltaX == 0) && (deltaY == height) ) || //Второй выше первого
            ( (deltaX == -width) && (deltaY == 0) ) || //Второй правее первого
            ( (deltaX == width) && (deltaY == 0) ) //Второй левее первого
            )
    {
        return true;
    }
    return false;
}

Пока работает.
Чую, где-то кроется косяк. В процессе тестов не выявил.