Хотя вопрос и простой, оставлю в качестве шпаргалки-сниппета:
#include <algorithm>
/*
x1, y1 - левая нижняя точка первого прямоугольника
x2, y2 - правая верхняя точка первого прямоугольника
x3, y3 - левая нижняя точка второго прямоугольника
x4, y4 - правая верхняя точка второго прямоугольника
*/
int f(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4)
{
int left = std::max(x1, x3);
int top = std::min(y2, y4);
int right = std::min(x2, x4);
int bottom = std::max(y1, y3);
int width = right - left;
int height = top - bottom;
if (width < 0 || height < 0)
return 0;
return width * height;
}
Исходя из вопроса, полагаю, что координаты растут из нижнего левого угла (если же Y растет сверху вниз, то необходимо внести соответствующие поправки).
Идея простая, иллюстрируется на картинке (показано как определяется ширина общего прямоугольника, высота определяется аналогично):
вычисление площади пересечения двух прямоугольников
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| using System; | |
| namespace Rectangles | |
| { | |
| public static class RectanglesTask | |
| { | |
| // Пересекаются ли два прямоугольника (пересечение только по границе также считается пересечением) | |
| // работает от обратного, если значения стороны одного прямоугольник больше чем значение прямо противоположной стороны другого прямоугольника | |
| // значит они не пересекаются. | |
| public static bool AreIntersected(Rectangle r1, Rectangle r2) => r1.Top > r2.Bottom || r1.Left > r2.Right || r2.Top > r1.Bottom || r2.Left > r1.Right ? false : true; | |
| // Площадь пересечения прямоугольников | |
| // решение почерпнуто из https://ru.stackoverflow.com/questions/758529 | |
| // вкратце: по оси Х: берется наибольшое значение от левой точки двух прямоугольников, | |
| // берется наименьшее значение от правой точки двух прямоугольников, из правой точки вычитаем левую и если это значение больше 0 | |
| // прямоугольники пересекаются, и эта вычисленная величина равно длинне необходимой площади пересечения. По оси У аналогично. | |
| public static int IntersectionSquare(Rectangle r1, Rectangle r2) | |
| { | |
| int leftIntersection = Math.Max(r1.Left, r2.Left); | |
| int topIntersection = Math.Min(r1.Bottom, r2.Bottom); | |
| int rightIntersction = Math.Min(r1.Right, r2.Right); | |
| int bottonIntersection = Math.Max(r1.Top, r2.Top); | |
| int widhtIntersection = rightIntersction — leftIntersection; | |
| int heightIntersection = topIntersection — bottonIntersection; | |
| if (widhtIntersection < 0 || heightIntersection < 0) | |
| return 0; | |
| else return widhtIntersection * heightIntersection; | |
| } | |
| // Если один из прямоугольников целиком находится внутри другого — вернуть номер (с нуля) внутреннего. | |
| // Иначе вернуть -1 | |
| // Первый прямоугольник находится во втором, если во втором находятся две противоположные вершины (по диагонали) первого, для другого прямоугольника все тоже самое но наоборот. | |
| public static int IndexOfInnerRectangle(Rectangle r1, Rectangle r2) => r1.Left <= r2.Left && r2.Right <= r1.Right && r2.Top >= r1.Top && r2.Bottom <= r1.Bottom ? 1 : (r2.Left <= r1.Left && r1.Right <= r2.Right && r1.Top >= r2.Top && r1.Bottom <= r2.Bottom) ? 0 : -1; | |
| } | |
| } |
I have a problem where I have TWO NON-rotated rectangles (given as two point tuples {x1 x2 y1 y2}) and I like to calculate their intersect area. I have seen more general answers to this question, e.g. more rectangles or even rotated ones, and I was wondering whether there is a much simpler solution as I only have two non-rotated rectangles.
What I imagine should be achievable is an algorithm that only uses addition, subtraction and multiplication, possibly abs() as well. What certainly should not be used are min/max, equal, greater/smaller and so on, which would make the question obsolete.
Thank you!
EDIT 2: okay, it’s become too easy using min/max or abs(). Can somebody show or disprove the case only using add/sub/mul?
EDIT: let’s relax it a little bit, only conditional expressions (e.g. if, case) are prohibited!
PS: I have been thinking about it for a half hour, without success, maybe I am now too old for this 
Кхм. Очень просто. Пусть прямоугольник $%A$% ограничен координатами $%(X_{ЛA}, Y_{НA}, X_{ПA}, Y_{ВA})$%, а прямоугольник $%B$% — координатами $%(X_{ЛB}, Y_{НB}, X_{ПB}, Y_{ВB})$%, где Л — лево, П — право, Н — низ, В — верх.
- Проверить условия перекрытия, например, если $%X_{ПA} < X_{ЛB}$%, то прямоугольники не пересекаются, общая площадь равна нулю.
- Определить стороны прямоугольника образованного пересечением, например, если $%X_{ПA} > X_{ЛB}$%, а $%X_{ЛA} < X_{ЛB}$%, то $%Delta X=X_{ПA}-X_{ЛB}$%
- Определить площадь, как произведение сторон: $%S_{AB}=Delta X ast Delta Y$%
Как найти площадь пересечения двух прямоугольников?
Есть два прямоугольника стороны, которых параллельны осям и они пересекаются. Нам известно:
(x1,y1) — левая нижняя точка первого прямоугольника
(x2,y2) — правая верхняя точка первого прямоугольника
(x3,y3) — левая нижняя точка второго прямоугольника
(x4,y4) — правая верхняя точка второго прямоугольника
И нужно найти площадь их пересечения. Но пересекатся они могут с разних сторон.
Хотя вопрос и простой, оставлю в качестве шпаргалки-сниппета:
Исходя из вопроса, полагаю, что координаты растут из нижнего левого угла (если же Y растет сверху вниз, то необходимо внести соответствующие поправки).
Идея простая, иллюстрируется на картинке (показано как определяется ширина общего прямоугольника, высота определяется аналогично):
Всё ещё ищете ответ? Посмотрите другие вопросы с метками c++ математика геометрия прямоугольники или задайте свой вопрос.
Site design / logo © 2022 Stack Exchange Inc; user contributions licensed under cc by-sa. rev 2022.6.10.42345
Нажимая «Принять все файлы cookie», вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.
геометрия — Пересечение прямоугольников
Как вывести общую формулу для построения пересечения прямоугольников? Ведь бывает, что один прямоугольник находится внутри другого или координаты первого прямоугольника по х больше, чем у второго и при этом меньше по у, чем у второго. Как свести разные случаи в один?
задан 30 Май ’17 20:59
1 ответ
Задача для прямоугольников сводится к аналогичной задаче для отрезков. По каждой оси смотрим на пересечения отрезков, а потом берём получившийся прямоугольник (как декартово произведение). Если хотя одно пересечение отрезков окажется пустым, то и пересечение прямоугольников пусто.
По определению, отрезок [a,b] есть множество решений двойного неравенства a<=x<=b. Для двух отрезков имеем систему неравенств a<=x, c<=x, x<=b, x<=d. Она равносильна системе max(a,c)<=x, x<=min(b,d). То есть надо взять максимум левых концов и минимум правых. Получится отрезок [max(a,c),min(b,d)]. Если первое число больше второго, то это пустое множество.
отвечен 30 Май ’17 21:15
@falcao: Я уж сороковой год использую неравенство $%max(a,c)le min(b,d)$% в для проверки пересечения отрезков. Проверять пересечение прямоугольников не приходилось. Это я о программировании.
@EdwardTurJ: я вспомнил по ходу дела, что вопрос о прямоугольниках уже звучал здесь. Там площадь надо было найти. Наверное, на практике такое редко требуется, а в тренировочных задачах частенько встречается.
Получить точки пересечения из 2 прямоугольников
Допустим, у нас есть два прямоугольника, определенные их нижним левым и верхним правым углами. Например: rect1 (x1, y1) (x2, y2) а также rect2 (x3, y3) (x4, y4).
Я пытаюсь найти координаты (внизу слева и вверху справа) пересеченного прямоугольника.
Любые идеи, алгоритм, псевдокод, будет принята с благодарностью.
постскриптум Я нашел похожие вопросы, но они проверяют, только если 2 прямоугольника пересекаются.
Решение
Если входные прямоугольники нормализованы, то есть вы уже знаете, что x1 < x2 , y1 < y2 (и то же самое для второго прямоугольника), тогда все, что вам нужно сделать, это рассчитать
и это даст вам ваше пересечение в виде прямоугольника (x5, y5)-(x6, y6) , Если исходные прямоугольники не пересекаются, результатом будет «вырожденный» прямоугольник (с x5 >= x6 и / или y5 >= y6 ), который вы можете легко проверить.
Постскриптум Как обычно, мелкие детали будут зависеть от того, нужно ли учитывать трогательный прямоугольники как пересекающиеся.
Другие решения
Чтобы найти пересечение, вам нужно сделать несколько простых сравнений точек:
Итак, как мы можем видеть из изображения, если x3, y3 больше или равно x1, y1 и меньше или равно x2, y2, то оно находится внутри первого прямоугольника, аналогично вам нужно будет проверить, попадает ли x4, y4 внутрь диапазон от х1, у1 до х2, у2, а также.
если оба условия оказываются верными, то вы можете быть уверены, что второй прямоугольник полностью охватывается первым. 
Вам нужно будет проверить и обратное, если узнаете, что внутри, что важно для вас.
Также необходимо, чтобы прямоугольники были выровнены по оси, иначе это не будет работать надежно.
Дайте мне знать, если вам нужно больше подробностей, хотя я думаю, что быстрый поиск в Google очень легко раскроет для вас более подробную информацию, но дайте мне знать, и я могу сделать учебник по столкновению с прямоугольником, если хотите.
Более подробно:
Чтобы выяснить, имеют ли прямоугольники пересечения, вы можете проверить координаты их определяющих точек, для наших целей мы будем использовать координаты верхнего левого и нижнего правого углов.
Мы можем использовать класс, чтобы сделать это проще для нас, и для максимального удобства использования кода мы можем использовать 2d Vector и 2d Point:
2dVectorPoint.h
Используемый код адаптирован из Вот чтобы сохранить мои пальцы.
Тогда мы можем использовать это, чтобы легко сравнить:
мы можем определить прямоугольник 1 как имеющий P1 и P2 как его границы и прямоугольник 2 как имеющий P3 и P4 как его границы, давая нам следующее сравнение:
Это вернет истинное значение для любого экземпляра пересечения или для прямоугольника 1, полностью охватывающего прямоугольник 2.
Чтобы проверить только пересечения, просто удалите проверку на равенство (возьмите все = из вышеприведенного уравнения), и вы будете проверять только на пересечения. Если у вас есть пересечение, вы можете использовать линейную алгебру для оценки точных координат.
Скажем, у блока есть радиус X и радиус Y (я знаю, что его нет, но этот термин здесь полезен).
Вы будете иметь:
Теперь, если прямоугольные средние точки находятся дальше, чем сумма их радиусов в соответствующем направлении — они не сталкиваются.
В противном случае они делают — этого намека должно хватить.
Теперь вы должны быть в состоянии выполнить задание.
ОБНОВИТЬ:
Хорошо — давайте решим это для 1D — позже вы решите это для 2D. Посмотрите на этот кусок … искусства
Вы видите 2 сегмента — теперь некоторые расчеты:
Теперь, как проверить, происходит ли столкновение? Как я уже сказал, если сумма «радиусов» меньше расстояния сегментов — столкновения нет:
Теперь ваша задача — вычислить пересечение / общую часть в 1D и 2D. Теперь все зависит от вас (вы можете прочитать ответ Андрея).
Здесь та же самая ситуация, но в 2D — две одномерные ситуации:
Вы можете иметь дело с x а также y Направление отдельно.
Предположим, что x1 <= x3 (первая коробка как минимум так же далеко, как и вторая). Тогда есть совпадение, если и только если x1 <= x3 <= x2 ,
Аналогично предположим y1 <= y3 (первая коробка, по крайней мере, так же далеко, как и вторая). Тогда есть совпадение, если и только если y1 <= y3 <= y2 ,
Если в обоих направлениях перекрытие, то перекрытие прямоугольника. Вы можете найти координаты, отсортировав x а также y координаты и выбрав два средних.