перекрытие прямоугольников

[Aleexeey]

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

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

Код:

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

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

[Finch]

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

[Aleexeey]

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

Второй вариант мне больше нравится. 
Щас попробую! 

[Skyf]

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

[Aleexeey]

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

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

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

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

За ранее спасибо!

[Алексей++]

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]

Алексей1153++ спасибо!
щас буду пробовать!

[Алексей++]

стало интересно, накидал вот что ) Но не тестировал. Зато идея видна

Код:

#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;
}

[Алексей++]

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

[Aleexeey]

Алексей1153++ это даже больше чем помощь  , спасибо огромное!
Именно то на что искал ответ