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

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

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

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

Модератору: Пожалуйста, перенесите этот пост в тему "пересечение прямоугольников"

Здравствуйте, WinterMute, Вы писали:

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

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

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

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

а если один внутри другого? но вписанные окружности не дают понять пересечение?

Здравствуйте, WinterMute, Вы писали:

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

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

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

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

прямоугольник — 4 угла, да возьми и процерь, не находятся ли один из углов внутри другого прямоугольника, и так 8 углов максимум проверять.
есть классическая задача проверки нахождения точки внутри треугольника (обычно задача звучит так: определить, находится ли начало кординат внутри треугольника), исходи от него и сделай свое

Здравствуйте, ilnar, Вы писали:

I>прямоугольник — 4 угла, да возьми и процерь, не находятся ли один из углов внутри другого прямоугольника, и так 8 углов максимум проверять.
I>есть классическая задача проверки нахождения точки внутри треугольника (обычно задача звучит так: определить, находится ли начало кординат внутри треугольника), исходи от него и сделай свое

Пересечение прямоугольников не гарантирует нахождения одного из углов внутри другого прямоугольника. Возьми квадрат, поверни на 45 градусов вокруг центра. Квадраты будут пересекаться (пересечение — 8иугольник), но нет вершины лежащий внутри другого.

Здравствуйте, Tan4ik, Вы писали:

T>Здравствуйте, ilnar, Вы писали:

I>>прямоугольник — 4 угла, да возьми и процерь, не находятся ли один из углов внутри другого прямоугольника, и так 8 углов максимум проверять.
I>>есть классическая задача проверки нахождения точки внутри треугольника (обычно задача звучит так: определить, находится ли начало кординат внутри треугольника), исходи от него и сделай свое

T>Пересечение прямоугольников не гарантирует нахождения одного из углов внутри другого прямоугольника. Возьми квадрат, поверни на 45 градусов вокруг центра. Квадраты будут пересекаться (пересечение — 8иугольник), но нет вершины лежащий внутри другого.

я надеюсь этот случай охватывается, если проверять еще и пересечение диагоналя первого прямоугольника второго треугольника?

Здравствуйте, WinterMute, Вы писали:

WM>Вычислим центры первого и второго прямоугольника (это быстро). Для каждого прямоугольника вычислим радиусы вписанной и описанной окружности (тоже быстро). Теперь, если расстояние между центрами прямоугольников меньше суммы радиусов вписанных окружностей -- они точно пересекаются, если расстояние больше суммы описанных окружностей -- они точно не пересекаются, в оставшемся случае нужно смотреть:
Назовем радиусы R1, r1, R2, r2. Расстояние между центрами — D.
Тогда.
if(D < max(r1 — R2, r2 — R1))
//не пересекаются

Здравствуйте, WinterMute, Вы писали:

WM>Модератору: Пожалуйста, перенесите этот пост в тему "пересечение прямоугольников"

У нас, к сожалению, нет пока такой фичи: склеивать ветки. Сделаю перекрёстные ссылки.

Здравствуйте, ilnar, Вы писали:

I>а если один внутри другого? но вписанные окружности не дают понять пересечение?

Да, нужно еще добавить проверку на то, что центр второго прямоугольника лежит внутри первого.

Здравствуйте, IO, Вы писали:

IO>Назовем радиусы R1, r1, R2, r2. Расстояние между центрами — D.
IO>Тогда.
IO>if(D < max(r1 — R2, r2 — R1))
IO> //не пересекаются

Зачем нужна разница радиусов вписанной и описанной окружности?

Здравствуйте, WinterMute, Вы писали:

Стороны прямоугольника образуют ортогональный репер. В этом базисе сам прямоугольник описывается как

0 <= x <= 1
0 <= y <= 1

Два прямоугольника задают два репера. Можно найти преобразование одного в другой. В общем виде оно будет выглядеть так

x2 = A*x1 + c

(здесь x1, x2 — координаты точки в разных базисах, А — матрица 2х2, с — вектор).

Координаты точки в одном базисе (х1,у1), координаты этой же точки в другом базисе (х2,у2).
Условие, что прямоугольники пересекаются — существует точка, для которой выполнено

0 <= x1 <= 1
0 <= y1 <= 1
0 <= x2 <= 1
0 <= y2 <= 1

Вторая пара неравенств выглядит так

0 <= a11*x1 + a12*y1 + c1 <= 1
0 <= a21*x1 + a22*y1 + c1 <= 1

Получаем 8 неравенств на 2 переменные. Надо ковырять дальше...

Здравствуйте, rus blood, Вы писали:

RB>Здравствуйте, WinterMute, Вы писали:
...
RB>Два прямоугольника задают два репера. Можно найти преобразование одного в другой. В общем виде оно будет выглядеть так
RB>

RB>x2 = A*x1 + c

RB>(здесь x1, x2 — координаты точки в разных базисах, А — матрица 2х2, с — вектор).
...

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

А>я бы просто выполнил преобразование (любое линейное), чтобы один из прямоугольнииков лег 2-я сторонами на оси координат.

вдогонку — после преобразования убедиться, что _обе_ проекции прямоугольников на оси попарно пересекаются.

Здравствуйте, WinterMute, Вы писали:

WM>Здравствуйте, IO, Вы писали:

IO>>Назовем радиусы R1, r1, R2, r2. Расстояние между центрами — D.
IO>>Тогда.
IO>>if(D < max(r1 — R2, r2 — R1))
IO>> //не пересекаются

WM>Зачем нужна разница радиусов вписанной и описанной окружности?
Прямоугольник внутри не достает до прямоугольника снаружи.
Вот еще:
if (D > R1+R2)
//не пересекаются

Т.е. это простые достаточные условия непересечения.

Здравствуйте, Аноним, Вы писали:

А>>я бы просто выполнил преобразование (любое линейное), чтобы один из прямоугольнииков лег 2-я сторонами на оси координат.

А>вдогонку — после преобразования убедиться, что _обе_ проекции прямоугольников на оси попарно пересекаются.

здесь

Автор: Tan4ik
Дата: 10.09.04

Здравствуйте, WinterMute, Вы писали:

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

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

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

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

пришло в голову, есть в математике такое понятие как epsilon-сеть, т.е. это множество точек, таких, что для любого x из пространства найдется х0 такое из сети, что метрика(х,х0)<=epsilon
учитывая это, целочисленные точки на плоскости образуют 1/sqrt(2) сеть

а теперь, пусть стороны прямоугольников — a1, b1; a2, b2
пусть a1<=b1, a2<=b2, a1<=a2 — замена и поворот при необходимости
теперь, чтоб покрыть сетью второй прямоугольник, нужна сеть a2/sqrt(2)
теперь если по периметру первого прямоугольника поставить точки через равное растояние соответственно по сторонам:
a) ceil(a1/a2*sqrt(2)) точек
b) ceil(b1/a2*sqrt(2)) точек
сделать решетку

теперь сделать решетку в другом прямоугольнике (поменяв цифры)

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

Здравствуйте, WinterMute, Вы писали:

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

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

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

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

Читаю и не знаю — смеяться или плакать.
Уважаемый WinterMute кажется использует шаманские методы для написания алгоритмов.
Алгоримт строиться на нахождении того находятся ли точки вершин внутри одного из прямойгольников и на определении пересечений сторон, и то это в случае если прямоугольники произвольно ориентированы относительно осей координат. Если же их стороны параллельны осям, то задача решается тривиальна и функцию для ее решения уже привели выше.
НО! Нахождение цетров и тем более РАСТОЯНИЙ. Это явно не правильный и ни с точки зрения геометрии ни с точки зрения скорости алгоритма метод.
И еще интересно знать как в прямоугольник можно вписать окружность(это можно сделать только для треугольников и правильных многоугольников). Если же имеется в виду окружность касающаяся только двух сторон, то это не называется вписаной окружностью.В геометрии для того и существуют четкие определения, чтобы ясно определять о чем идет речь. Здесь не понятно.

P.S. Уважаемый Модератор, эту ветку можно удалить. Т.к. тема раскрыта в предыдущей ветке. А здесь скорее ведутся псевдонаучные изыскания.

_Werewolf wrote:

> И еще интересно знать как в прямоугольник можно вписать окружность(это
> можно сделать только для треугольников и правильных многоугольников).

Как в анекдоте про военку: "Авал — это окружность, вписаная в квадрат со
сторонами 3 на 4".

--
С уважением,
Alex Besogonov (alexy@izh.com)

А если оба в виде подковы ?