Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: перекрытие прямоугольников  (Прочитано 14646 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Aleexeey
Постоялец

ru
Offline Offline

« : 05-04-2009 11:57 » 

Доброе время суток!

Задался вопросом:
Есть несколько прямоугольников, наложенные друг на друга (с разными размерами и положениями).
Например это массив: 1) первый прямоугольник, его позиция, 2) второй прямоугольник, его позиция, ... n) последний прямоугольник и его позиция.
И нужно найти прямоугольник, который полностью перекрыт другими (back).
Или иными словами, получить номера прямоугольников, которые хотя-бы частично, но видны (front).

Код:
struct rectArray
{
       RECT r; // размер и позиция прямоугольника
       int i; // номер прямоугольника (где 0, 1, ... - задний план; ..., n-2, n-1 - передний план)
};
array<rectArray> ra;

Где можно найти такой алгоритм, или как грамотно его реализовать?
Подкиньте идейки, пожалуйста!
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #1 : 05-04-2009 15:05 » new

Ну первый метод, он хоть и самый громоздкий по времени выполнения, Но самый простой. Это простой перебор. Почти в каждой библиотеке, которую я видел в классе rect содержится метод, который возрашает ответ, перекрывается ли данный прямоугольник другим или нет.
Второй метод, рассортировать координаты левого-верхнего угла и правого нижнего угла всех прямоугольников и по оси X и по стороне Y. Т.е. получится два отсортированных массива с координатами. Теперь только останется в этом массиве сопоставить свой прямоугольник с другими координатами. И если есть пересечение коррдинат и по оси X и по оси Y. Значит это и есть наш прямоугольник, Но тут набо будет писать кучу проверок.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Aleexeey
Постоялец

ru
Offline Offline

« Ответ #2 : 05-04-2009 15:34 » 

Finch спасибо!
я первый способ пробовал и он меня не устраивает, слишком тормозит.
мне нужно самое эффективное решение (по отношению производительности)!

Второй вариант мне больше нравится.  Класс!
Щас попробую!  Да-да
Записан
Skyf
Гость
« Ответ #3 : 05-04-2009 16:09 » 

Есть алгоритмы готовые - копни в той же винде, они реализуют такое для окошек - там было название, сейчас и не вспомнить.
Записан
Aleexeey
Постоялец

ru
Offline Offline

« Ответ #4 : 10-04-2009 07:12 » 

Доброе время всем кто читает!
Пробовал упорядочиванием rect, этот способ мне не понравился, т. к. не точное определение перекрытия.

Вот например:
Допустим проверяемый RECT перекрыт двумя прямоугольниками (сверху слева и снизу справа) так, что (верх права и низ лева)
углы не перекрыты (этот RECT нужно считать не перекрытым), хотя определив MIN и MAX размеры перебираемых прямоугольников,
можно заключить что проверяемый RECT полностью перекрыт.


Остановился на варианте, перебирать rect с конца, тем самым не доходя до начала уже обнаружится перекрытие.

Подскажите только, как узнать что проверяемый прямоугольник полностью перекрыт другими прямоугольниками!
Или киньте ссылку где можно найти такой алгоритм, мне нужна максимальная производительность!

За ранее спасибо!
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #5 : 10-04-2009 07:34 » 

Aleexeey, попробуй рекурсию:

к примеру, прямоугольники отсортированы по Z
1,2,3,4,5,6,7,8
1 - это самый верхний.
 хотим узнать, виден ли 5 :

1) проверяем перекрытие с 4. продолженные края прямоугольника 4 разбивают 5 на несколько под-прямоугольников (от 1 до 9).
1.1) если разбито на всего 1 прямоуг, то 5 либо весь не виден из под 4, либо весь виден, по отношению к 4 же.
1.2) иначе - передаём рекурсивно кажную долю в пункт 1, но уже сверяемся с 3-м прямоугольником

2) если был виден хотя бы один кусочек - то 5 - виден хотя бы частично
Записан

Aleexeey
Постоялец

ru
Offline Offline

« Ответ #6 : 10-04-2009 07:43 » 

Алексей1153++ спасибо!
щас буду пробовать!
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #7 : 10-04-2009 11:01 » 

стало интересно, накидал вот что ) Но не тестировал. Зато идея видна
Код:
#include <windows.h>

bool GetIsRectVisible(RECT*,const RECT*,DWORD);

DWORD main(int argc, char *argv[])
{

enum
{
e_rectz_count=10,
};

RECT Array[e_rectz_count];

//...

//Array - отсортированные по возрастанию Z прямоугольники
//[0] - самый верхний пр-к

//пр-к, который будем проверять
const DWORD dwdRectIndexToCheck=4;


if(GetIsRectVisible(Array,&Array[dwdRectIndexToCheck],dwdRectIndexToCheck-1))
{
//видно
}
else
{
//невидно
}



return 0;
}

bool GetIsRectVisible(RECT* ArrayOfTopRectz,const RECT* pR, DWORD dwdIndexOf1stTop)
{
if(pR==0)return false;
if(dwdIndexOf1stTop==0xffffffff)return true;

RECT part;

//текущий верхний прямоугольник
RECT* const pRT=&ArrayOfTopRectz[dwdIndexOf1stTop];

BYTE byPartCount=0;

//смотрим взаимное расположение проверяемого и верхнего
if(
(pR->right  < pRT->left || pR->left > pRT->right)
&&
(pR->bottom > pRT->top  || pR->top < pRT->bottom)
)
{
//pR не пересекаются pRT совсем

//проверяем с остальными
return GetIsRectVisible(ArrayOfTopRectz,pR,dwdIndexOf1stTop-1);
}
else
if(
pR->right <= pRT->right &&
pR->left >= pRT->left &&
pR->bottom >= pRT->bottom &&
pR->top <= pRT->top
)
{
//pR полностью закрыт
return false;
}

//pR и pRT пересекаются

//видна ли часть pR слева?
if(pR->right>=pRT->left)
{
//проверяем всю часть слева (+сверху-слева и снизу-слева)
part.left   =pR->left;
part.right  =pRT->left;
part.top    =pR->top;
part.bottom =pR->bottom;
if(GetIsRectVisible(ArrayOfTopRectz,&part,dwdIndexOf1stTop-1))return true;
}

//видна ли часть pR справа?
if(pR->left<=pRT->right)
{
//проверяем всю часть справа (+сверху-справа и снизу-справа)
part.left   =pRT->right;
part.right  =pR->right;
part.top    =pR->top;
part.bottom =pR->bottom;
if(GetIsRectVisible(ArrayOfTopRectz,&part,dwdIndexOf1stTop-1))return true;
}

//видна ли часть pR сверху?
if(pR->bottom>=pRT->top)
{
//проверяем часть ТОЛЬКО сверху
part.left   =pRT->left;
part.right  =pRT->right;
part.top    =pR->top;
part.bottom =pRT->top;
if(GetIsRectVisible(ArrayOfTopRectz,&part,dwdIndexOf1stTop-1))return true;
}

//видна ли часть pR снизу?
if(pR->top<=pRT->bottom)
{
//проверяем часть ТОЛЬКО снизу
part.left   =pRT->left;
part.right  =pRT->right;
part.top    =pRT->bottom;
part.bottom =pR->bottom;
if(GetIsRectVisible(ArrayOfTopRectz,&part,dwdIndexOf1stTop-1))return true;
}

return false;
}
« Последнее редактирование: 10-04-2009 15:23 от Алексей1153++ » Записан

Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #8 : 10-04-2009 11:21 » 

уже нашёл кое что и исправил )
Записан

Aleexeey
Постоялец

ru
Offline Offline

« Ответ #9 : 12-04-2009 06:17 » 

Алексей1153++ это даже больше чем помощь  Класс!, спасибо огромное!
Именно то на что искал ответ  Да-да
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines