Ладно блин, третья попытка.

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

Метод "в лоб": перебрать все сочетания граней прямоугольников и попытаться найти их пересечение. Если есть хоть одно пересечение -- прямоугольники пересекаются.

Нужно получше подумать, но наверное сработает и такой способ (и он будет быстрее): берёшь две грани от прямоугольников которые лежат ближе всего друг к другу (видимо, это те, которые пересекаются с отрезком соединяющем центры двух прямоугольников). Смотришь, пересекаются ли они друг с другом, если да -- прямоугольники пересекаются, если нет, то нет.