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

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

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

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

@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++
1
2
3
4
5
6
7
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;

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@Azazel-San Mental handicap 1246 / 624 / 171 Регистрация: 24.11.2015 Сообщений: 2,429

	Пересечение двух прямоугольников 13.09.2017, 23:41. Показов 9578. Ответов 22 Метки нет (Все метки) Собственно, как можно реализовать пересечение двух таких вот прямоугольников, когда известны все вершины первого и второго? Миниатюры 0

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

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

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

@COKPOWEHEU 4083 / 2681 / 432 Регистрация: 09.09.2017 Сообщений: 11,910
	14.09.2017, 09:18
	Если на плоскости, то просто проверить пересечение отрезков. Если хоть одна сторона первого прямогугольника (четырехугольника?) пересекает хоть одну сторону второго - они пересекаются. Для определения пересечения отрезков рисуете их на бумажке, пишете формулы, описывающие все точки на них (получится что-то вроде 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 [ТС]
	Antikl, хм... интересно, стороны моего красного прямоугольника параллельны осям координат? Добавлено через 5 минут COKPOWEHEU, тоже думал об пересечении отрезков, но тогда надо проверять для каждой из сторон пересечение? Т.е. нужно будет проверять пересекает ли сторона a,b прямоугольника А, сторону a,b прямоугольника B и так для всех сторон? А если зелёный прямоугольник будет включён в красный что тогда? 0

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

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

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

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

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

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

@Azazel-San Mental handicap 1246 / 624 / 171 Регистрация: 24.11.2015 Сообщений: 2,429
	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; 0