Пересечение двух прямоугольников

@Azazel-San · Регистрация: 24.11.2015

Author24 — интернет-сервис помощи студентам

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

@COKPOWEHEU · 14.09.2017, 00:11

Это в объеме что ли задача?
Что требуется? Определить пересекаются ли вообще? Или правильно отрисовать пересечение?

@TheCalligrapher · 14.09.2017, 00:51

Сообщение от Azazel-San

реализовать пересечение

Что такое "реализовать пересечение"?

Сообщение от Azazel-San

двух таких вот прямоугольников

Ваш красный "прямоугольник" какой-то ни разу не прямоугольный. Что это вообще такое?

@Azazel-San · 14.09.2017, 08:05 **[ТС]**

COKPOWEHEU, нет не в объёме, определить пересекаются ли вообще
TheCalligrapher, ну, или как проверить пересекаются ли две эти фигуры, одна из них прямоугольник с параллельными осям сторонами, второй изометрический прямоугольник. Возможно ли как-то вообще проверить их на пересечение?

З.ы. - это для игры, зелёный квадрат - это персонаж, красный - часть карты

@Antikl · 14.09.2017, 08:33

можете сдесь глянуть
http://forum.sources.ru/index.php?showtopic=202182

Добавлено через 1 минуту
https://xdan.ru/how-to-check-i... ngles.html

@COKPOWEHEU · 14.09.2017, 09:18

Если на плоскости, то просто проверить пересечение отрезков. Если хоть одна сторона первого прямогугольника (четырехугольника?) пересекает хоть одну сторону второго - они пересекаются.
Для определения пересечения отрезков рисуете их на бумажке, пишете формулы, описывающие все точки на них (получится что-то вроде y=a*x+b или (x-x0)/(x1-x0) = (y-y0)/(y1-y0), где (x0, y0), (x1, y1) - координаты начала и конца отрезка) и решаете систему уравнений. Потом полученную формулу переводите на язык программирования

@Azazel-San · 14.09.2017, 09:24 **[ТС]**

Antikl, хм... интересно, стороны моего красного прямоугольника параллельны осям координат?

Добавлено через 5 минут
COKPOWEHEU, тоже думал об пересечении отрезков, но тогда надо проверять для каждой из сторон пересечение? Т.е. нужно будет проверять пересекает ли сторона a,b прямоугольника А, сторону a,b прямоугольника B и так для всех сторон? А если зелёный прямоугольник будет включён в красный что тогда?

@woldemas · 14.09.2017, 09:47

Сообщение от COKPOWEHEU

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

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

Добавлено через 21 минуту
Один параллелограмм, а второй прямоугольник выровненный по осям?
Если так, то простой формулы я не знаю, надо выводить. Представить точку параллелограмма в виде линейной комбинации
p = c + u * (a - c) + v * (d - c), где u,v - параметры. Подставить в неравенства для прямоугольника xmin <= px <= xmax, ymin <= py <= ymax и решить. Получатся два интервала для u и v в общем виде, если они оба имеют общую точку с интервалом [0;1] пересечение есть.

@Azazel-San · 14.09.2017, 10:14 **[ТС]**

woldemas, где u v - ширина и высота? Или что это за параметры?

MrGluck · 14.09.2017, 10:31

Azazel-San, если вы используете двухмерную систему координат (а судя по подписям к осям, так оно и есть), тогда у меня плохие новости.
Ваш красный прямоугольник - не прямоугольник вовсе.

@Azazel-San · 14.09.2017, 11:22 **[ТС]**

MrGluck, изначально он им был, до того как его координаты были приведены к изометрической системы, просто я не знал как верно сформулировать вопрос, типо пересечение прямоугольника и четырёхугольника?

@COKPOWEHEU · 14.09.2017, 13:12

Сообщение от Azazel-San

А если зелёный прямоугольник будет включён в красный что тогда?

А это считается пересечением?
.
Если ребра зеленого прямоугольника всегда параллельны осям, задача существенно упрощается

@Azazel-San · 14.09.2017, 14:15 **[ТС]**

Сообщение от COKPOWEHEU

А это считается пересечением?

впринципе да, это уже получается совсем другая проверка, по идее включатся они не должны, но всякое может случится..

Сообщение от COKPOWEHEU

задача существенно упрощается

всмысле?

@saqef · 14.09.2017, 14:23

Всё предельно просто:
Цикл с перебором граней 1 прямоугольника со вложенным циклом с перебором 2 прямоугольница
с проверкой на пересечение отрезков.
Алгоритмов на пересечение отрезков полно.
Кормен

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

@woldemas · 14.09.2017, 14:41

Сообщение от Azazel-San

где u v - ширина и высота?

Нет это параметры точки, любая точка для которых их значения в диапазоне от 0 до 1 принадлежит четырехугольнику

Сообщение от saqef

Цикл с перебором граней 1 прямоугольника со вложенным циклом с перебором 2 прямоугольница
с проверкой на пересечение отрезков.

Это если не учитывать вариант вложения. Тогда действительно если один параллелен осям задача упрощается: берем четыре прямые параллельные осям содержащие стороны зеленого и считаем их пересечения со сторонами красного, если хоть одна полученная точка попадает в диапазон стороны зеленого - они пересекаются. Точка пересечения стороны aс красного с прямой x_max( или bd) зеленого ищется просто: ее координата x известна = x_max, y = y_a + (y_c - y_a) * (x_max - x_a) / (x_c - x_a). Если она попадает в диапазон [y_min; y_max] - пересечение есть.

@Azazel-San · 14.09.2017, 17:05 **[ТС]**

woldemas, как-то я туплю, что такое x_max, y_min, y_max ? y_a , y_c - я так понимаю это вершины а и с красного прямоугольника?

@woldemas · 14.09.2017, 17:18

Сообщение от Azazel-San

woldemas, как-то я туплю, что такое x_max, y_min, y_max ? y_a , y_c - я так понимаю это вершины а и с красного прямоугольника?

Ну зеленый он же по осям выровнен, у него у одной стороны (левой) все x одинаковы назовем x_min, у правой - x_max, аналогично y_min (сверху), у_max(снизу).

@Azazel-San · 14.09.2017, 18:18 **[ТС]**

woldemas, сделал что-то такое:

C++

float intersection(Object &rect)
{
    float x_max = x2;
    float y = rect.x1 + (rect.x3 - rect.x1) * (x_max - x1) / (x3 - x1);
 
    return (x_max, y);
}

для начала решил посмотреть что за точки возвращает ф-я, и она возвращает -inf
Object &rect - это красный прямоугольник, он имеет координаты вершин x1, y1, x2, y2, x3, y3, x4, y4, ф-я вызывается из класса зеленого прямоугольника у него тоже есть координаты вершин

@woldemas · 14.09.2017, 18:21

Ну это значит видимо, что x3 = x1, т.е. эта сторона параллельна стороне с которой ищется пересечение, эту пару можно не рассматривать, наверное, хотя трудно сказать.

@Azazel-San · 14.09.2017, 18:36 **[ТС]**

woldemas, вероятно, да
x1 = x; y1 = y;
x2 = x + width; y2 = y;
x3 = x; y3 = y + height;
x4 = x + width; y4 = y + height;

@Azazel-San Mental handicap 1246 / 624 / 171 Регистрация: 24.11.2015 Сообщений: 2,429
	14.09.2017, 17:05 [ТС]	16
	woldemas, как-то я туплю, что такое `x_max, y_min, y_max` ? y_a , y_c - я так понимаю это вершины а и с красного прямоугольника? 0

@woldemas 672 / 475 / 215 Регистрация: 06.09.2013 Сообщений: 1,306
	14.09.2017, 18:21	19
	Ну это значит видимо, что x3 = x1, т.е. эта сторона параллельна стороне с которой ищется пересечение, эту пару можно не рассматривать, наверное, хотя трудно сказать. 0

@Azazel-San Mental handicap 1246 / 624 / 171 Регистрация: 24.11.2015 Сообщений: 2,429
		1
	Пересечение двух прямоугольников 13.09.2017, 23:41. Показов 8569. Ответов 22 Метки нет (Все метки) Собственно, как можно реализовать пересечение двух таких вот прямоугольников, когда известны все вершины первого и второго? Миниатюры 0

@COKPOWEHEU 3881 / 2479 / 418 Регистрация: 09.09.2017 Сообщений: 10,862
	14.09.2017, 00:11	2
	Это в объеме что ли задача? Что требуется? Определить пересекаются ли вообще? Или правильно отрисовать пересечение? 0

@TheCalligrapher Вездепух 11688 / 6367 / 1723 Регистрация: 18.10.2014 Сообщений: 16,050
	14.09.2017, 00:51	3
	Сообщение от Azazel-San реализовать пересечение Что такое "реализовать пересечение"? Сообщение от Azazel-San двух таких вот прямоугольников Ваш красный "прямоугольник" какой-то ни разу не прямоугольный. Что это вообще такое? 0

@Azazel-San Mental handicap 1246 / 624 / 171 Регистрация: 24.11.2015 Сообщений: 2,429
	14.09.2017, 08:05 [ТС]	4
	COKPOWEHEU, нет не в объёме, определить пересекаются ли вообще TheCalligrapher, ну, или как проверить пересекаются ли две эти фигуры, одна из них прямоугольник с параллельными осям сторонами, второй изометрический прямоугольник. Возможно ли как-то вообще проверить их на пересечение? З.ы. - это для игры, зелёный квадрат - это персонаж, красный - часть карты 0

@Antikl с++ 1282 / 523 / 225 Регистрация: 15.07.2015 Сообщений: 2,562
	14.09.2017, 08:33	5
	можете сдесь глянуть http://forum.sources.ru/index.php?showtopic=202182 Добавлено через 1 минуту https://xdan.ru/how-to-check-i... ngles.html 0

@COKPOWEHEU 3881 / 2479 / 418 Регистрация: 09.09.2017 Сообщений: 10,862
	14.09.2017, 09:18	6
	Если на плоскости, то просто проверить пересечение отрезков. Если хоть одна сторона первого прямогугольника (четырехугольника?) пересекает хоть одну сторону второго - они пересекаются. Для определения пересечения отрезков рисуете их на бумажке, пишете формулы, описывающие все точки на них (получится что-то вроде y=a*x+b или (x-x0)/(x1-x0) = (y-y0)/(y1-y0), где (x0, y0), (x1, y1) - координаты начала и конца отрезка) и решаете систему уравнений. Потом полученную формулу переводите на язык программирования 0

@Azazel-San Mental handicap 1246 / 624 / 171 Регистрация: 24.11.2015 Сообщений: 2,429
	14.09.2017, 09:24 [ТС]	7
	Antikl, хм... интересно, стороны моего красного прямоугольника параллельны осям координат? Добавлено через 5 минут COKPOWEHEU, тоже думал об пересечении отрезков, но тогда надо проверять для каждой из сторон пересечение? Т.е. нужно будет проверять пересекает ли сторона a,b прямоугольника А, сторону a,b прямоугольника B и так для всех сторон? А если зелёный прямоугольник будет включён в красный что тогда? 0

@woldemas 672 / 475 / 215 Регистрация: 06.09.2013 Сообщений: 1,306
	14.09.2017, 09:47	8
	Сообщение от COKPOWEHEU Если на плоскости, то просто проверить пересечение отрезков. Если хоть одна сторона первого прямогугольника (четырехугольника?) пересекает хоть одну сторону второго - они пересекаются. А если один вложен в другой и стороны не пересекаются? Добавлено через 21 минуту Один параллелограмм, а второй прямоугольник выровненный по осям? Если так, то простой формулы я не знаю, надо выводить. Представить точку параллелограмма в виде линейной комбинации p = c + u * (a - c) + v * (d - c), где u,v - параметры. Подставить в неравенства для прямоугольника xmin <= px <= xmax, ymin <= py <= ymax и решить. Получатся два интервала для u и v в общем виде, если они оба имеют общую точку с интервалом [0;1] пересечение есть. 0

@Azazel-San Mental handicap 1246 / 624 / 171 Регистрация: 24.11.2015 Сообщений: 2,429
	14.09.2017, 10:14 [ТС]	9
	woldemas, где u v - ширина и высота? Или что это за параметры? 0

MrGluck Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	14.09.2017, 10:31	10
	Azazel-San, если вы используете двухмерную систему координат (а судя по подписям к осям, так оно и есть), тогда у меня плохие новости. Ваш красный прямоугольник - не прямоугольник вовсе. 0

	14.09.2017, 18:36

Опции темы

@Azazel-San Mental handicap 1246 / 624 / 171 Регистрация: 24.11.2015 Сообщений: 2,429
	14.09.2017, 11:22 [ТС]	11
	MrGluck, изначально он им был, до того как его координаты были приведены к изометрической системы, просто я не знал как верно сформулировать вопрос, типо пересечение прямоугольника и четырёхугольника? 0

@COKPOWEHEU 3881 / 2479 / 418 Регистрация: 09.09.2017 Сообщений: 10,862
	14.09.2017, 13:12	12
	Сообщение от Azazel-San А если зелёный прямоугольник будет включён в красный что тогда? А это считается пересечением? . Если ребра зеленого прямоугольника всегда параллельны осям, задача существенно упрощается 0

@Azazel-San Mental handicap 1246 / 624 / 171 Регистрация: 24.11.2015 Сообщений: 2,429
	14.09.2017, 14:15 [ТС]	13
	Сообщение от COKPOWEHEU А это считается пересечением? впринципе да, это уже получается совсем другая проверка, по идее включатся они не должны, но всякое может случится.. Сообщение от COKPOWEHEU задача существенно упрощается всмысле? 0

@saqef 34 / 36 / 17 Регистрация: 16.04.2017 Сообщений: 478 Записей в блоге: 4
	14.09.2017, 14:23	14
	Всё предельно просто: Цикл с перебором граней 1 прямоугольника со вложенным циклом с перебором 2 прямоугольница с проверкой на пересечение отрезков. Алгоритмов на пересечение отрезков полно. Кормен Если требуется проверка на вложенность, то смотрим по какую сторону от отрезка лежат координаты узлов другого прямоугольника. 0

@woldemas 672 / 475 / 215 Регистрация: 06.09.2013 Сообщений: 1,306
	14.09.2017, 14:41	15
	Сообщение от Azazel-San где u v - ширина и высота? Нет это параметры точки, любая точка для которых их значения в диапазоне от 0 до 1 принадлежит четырехугольнику Сообщение от saqef Цикл с перебором граней 1 прямоугольника со вложенным циклом с перебором 2 прямоугольница с проверкой на пересечение отрезков. Это если не учитывать вариант вложения. Тогда действительно если один параллелен осям задача упрощается: берем четыре прямые параллельные осям содержащие стороны зеленого и считаем их пересечения со сторонами красного, если хоть одна полученная точка попадает в диапазон стороны зеленого - они пересекаются. Точка пересечения стороны aс красного с прямой x_max( или bd) зеленого ищется просто: ее координата x известна = x_max, y = y_a + (y_c - y_a) * (x_max - x_a) / (x_c - x_a). Если она попадает в диапазон [y_min; y_max] - пересечение есть. 0

@woldemas 672 / 475 / 215 Регистрация: 06.09.2013 Сообщений: 1,306
	14.09.2017, 17:18	17
	Сообщение от Azazel-San woldemas, как-то я туплю, что такое x_max, y_min, y_max ? y_a , y_c - я так понимаю это вершины а и с красного прямоугольника? Ну зеленый он же по осям выровнен, у него у одной стороны (левой) все x одинаковы назовем x_min, у правой - x_max, аналогично y_min (сверху), у_max(снизу). 1

@Azazel-San Mental handicap 1246 / 624 / 171 Регистрация: 24.11.2015 Сообщений: 2,429
	14.09.2017, 18:36 [ТС]	20
	woldemas, вероятно, да x1 = x; y1 = y; x2 = x + width; y2 = y; x3 = x; y3 = y + height; x4 = x + width; y4 = y + height; 0