Форум программистов
 
Расширенный поиск
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

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

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

Excel VBA, CAD, Софт, ОС, Windows, Ubuntu, Android, VPS
Win Api, Assembler, C++, Java, Pascal, Lazarus, Delphi, OpenGL, DirectX
C#, Qt, .NET, ASP.NET, Windows Forms, ADO.NET, Framework, WPF, UWP, WinRT, XAML
HTML, CSS, JavaScript, Ajax, PHP, Perl, Python, Ruby, SQL, WordPress, API, XML, JSON, ActionScript, Flash

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

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

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

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

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

skype: ilya10009
По умолчанию

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

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

skype: ilya10009
По умолчанию

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

icq: 421049471
skype: phomm-
По умолчанию

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

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

Решил по-своему, 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 в 19:30. Причина: Не сказал на чём писал
Lasor вне форума   Ответить с цитированием
Ответ



Опции темы

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

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




11:21.


Powered by vBulletin® Version 3.8.8 Beta 2
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.

Покупайте на сайте www.skinon.ru уникальные чехлы и наклейки для телефонов.
купить трафик


как улучшить посещаемость, а также решения по монетизации сайтов, видео и приложений

RusProfile.ru


Справочник российских юридических лиц и организаций.
Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru