Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Qt и кроссплатформенное программирование С/С++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 22.09.2016, 16:15   #1
Lasor
Пользователь
 
Регистрация: 05.12.2012
Сообщений: 67
По умолчанию Группировка прямоугольников

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

Номера внутри - их номера в массиве.
Есть у кого идеи как их сгруппировать?
Lasor вне форума Ответить с цитированием
Старый 22.09.2016, 19:47   #2
waleri
Старожил
 
Регистрация: 13.07.2012
Сообщений: 6,493
По умолчанию

Ну, расставьте в круг...
waleri вне форума Ответить с цитированием
Старый 22.09.2016, 21:22   #3
Lasor
Пользователь
 
Регистрация: 05.12.2012
Сообщений: 67
По умолчанию

Цитата:
Сообщение от waleri Посмотреть сообщение
Ну, расставьте в круг...
Не понял
Lasor вне форума Ответить с цитированием
Старый 23.09.2016, 03:22   #4
SAMOUCHKA
Форумчанин
 
Регистрация: 07.08.2011
Сообщений: 576
По умолчанию

Цитата:
Под группировкой подразумевается разбиение на отдельные массивы общего массива, в котором и приходят данные по прямоугольникам.
не понятно по каким параметрам их группировать
SAMOUCHKA вне форума Ответить с цитированием
Старый 23.09.2016, 07:18   #5
Lasor
Пользователь
 
Регистрация: 05.12.2012
Сообщений: 67
По умолчанию

Цитата:
Сообщение от SAMOUCHKA Посмотреть сообщение
не понятно по каким параметрам их группировать
По принципу соседей: тех, что находятся радом или по диагогали друг от друга.
Lasor вне форума Ответить с цитированием
Старый 23.09.2016, 07:30   #6
SAMOUCHKA
Форумчанин
 
Регистрация: 07.08.2011
Сообщений: 576
По умолчанию

Цитата:
Сообщение от Lasor Посмотреть сообщение
По принципу соседей: тех, что находятся радом или по диагогали друг от друга.
в смысле имеют общие точки? Тут несколько способов. Гугли заполнение фигуры или как то так.
SAMOUCHKA вне форума Ответить с цитированием
Старый 28.09.2016, 01:05   #7
phomm
personality
Старожил
 
Аватар для phomm
 
Регистрация: 28.04.2009
Сообщений: 2,876
По умолчанию

Вот тема с решением почти той же задачи http://programmersforum.ru/showthread.php?t=169044
Для Вашей задачи только признаки общности задать не из принципа, что индексы в 2мерном массиве "рядом", а координаты углов не больше некоего эпсилона (по картинке - пара пикселей). Ну и паскаль, да.
phomm вне форума Ответить с цитированием
Старый 06.10.2016, 12:25   #8
Lasor
Пользователь
 
Регистрация: 05.12.2012
Сообщений: 67
По умолчанию

Цитата:
Сообщение от phomm Посмотреть сообщение
Вот тема с решением почти той же задачи http://programmersforum.ru/showthread.php?t=169044
Для Вашей задачи только признаки общности задать не из принципа, что индексы в 2мерном массиве "рядом", а координаты углов не больше некоего эпсилона (по картинке - пара пикселей). Ну и паскаль, да.
Спасибо за наводку, буду разбираться в том, что там написано.
Lasor вне форума Ответить с цитированием
Старый 13.10.2016, 16:51   #9
Lasor
Пользователь
 
Регистрация: 05.12.2012
Сообщений: 67
По умолчанию

Решил по-своему, 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;
}
Пока работает.
Чую, где-то кроется косяк. В процессе тестов не выявил.

Последний раз редактировалось Lasor; 13.10.2016 в 18:30. Причина: Не сказал на чём писал
Lasor вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Метод прямоугольников realist88 Помощь студентам 1 17.05.2015 16:16
Площадь прямоугольников savraska Помощь студентам 7 04.06.2010 16:42
N прямоугольников по горизонтали Анюта01 Помощь студентам 5 19.03.2010 15:42
Площади прямоугольников.С++ evgenij9241 Помощь студентам 1 15.01.2010 15:33
5 прямоугольников Carbon Помощь студентам 10 08.11.2007 10:08