Геометрия,как найти площадь пересечения двух прямоугольников
Два прямоугольника на плоскости со сторонами, параллельными осям координат, заданы координатами левой верхней вершины и нижней правой вершины. Как определить площадь их общей части?
задан 9 Апр ’17 13:36
1 ответ
Сначала решим задачу для одномерного случая. Пусть даны отрезки $%[a,b]$% и $%[c,d]$%. Найдём длину их общей части. Полезно нарисовать несколько картинок, различая отдельные случаи.
1) Один из отрезков лежит правее другого. В этом случае отрезки либо не пересекаются, либо пересекаются по точке. Длина их общей части равна нулю. Этому случаю соответствуют неравенства $%b\le c$% или $%d\le a$% (совокупность).
Теперь рассматриваем двумерный случай. Если у прямоугольника левая верхняя вершина $%(x,y)$%, а правая нижняя $%(z,t)$%, то он равен $%[x,z]\times[y,t]$%. Если даны два таких прямоугольника вида $%[x_i,z_i]\times[y_i,t_i]$%, где $%i=1,2$%, то в пересечении получится множество $%([x_1,z_1]\cap[x_2,z_2])\times([y_1,t_1]\cap[y_2,t_2])$%. Для одномерного случая мы всё уже умеем выяснять, и остаётся перемножить два измерения.
отвечен 9 Апр ’17 20:28
falcao
300k ● 9 ● 38 ● 55
От перебора случаев спасает функция max и min. Для одномерного случая — min(b,d)-max(a,c).
(9 Апр ’17 21:09) knop
@knop: я дал общую картину, и сознательно не стал упоминать про min и max (хотя изначально такое намерение было). Способ конкретной реализации системы логических условий — вещь уже в значительной мере техническая. Сходу не очень понятно, в каком виде это всё проще реализовать программно. В Maple я бы использовал условные операторы с участием elif.
(9 Апр ’17 21:20) falcao
min-max может давать отрицательное значение. Наверное, надо брать его максимум с нулём — тогда получится готовая формула.
Алгоритм нахождения площади пересечения
Вот задача, но мне не нужен код, помогите с алгоритмом нахождения площади пересечения.
Напишите программу, которая находит площадь пересечения, то есть общей части двух прямоугольников. Каждый прямоугольник задается координатами двух произвольных противоположных углов. Стороны прямоугольников параллельны осям координат.
Ваша программа должна вводить с клавиатуры числа x1, y1, x2, y2, x3, y3, x4, y4. Числа xi, yi будут вводиться в i-строке (1≤i≤4) и разделяться одним пробелом. Точки (x1, y1) и (x2, y2) – координаты двух противоположных углов первого прямоугольника. Точки (x3, y3) и (x4, y4) – координаты двух противоположных углов второго прямоугольника.
Числа xi, yi – целые; 0≤xi, yi≤30000; оба прямоугольника имеют ненулевую площадь.
Ваша программа должна вывести на экран одно число S – площадь общей части двух введенных прямоугольников. Если введенные прямоугольники не имеют общих точек, то ваша программа должна вывести на экран число 0.
Голосование за лучший ответ
собственно, всё сводится к нахождению пересечений отрезков (x1, x2) ∩ (x3, x4) и отрезков (y1,y2) ∩ (y3, y4)
а пересечение отрезков (a, b)∩(c, d) посчитать легко: это (max(a,c), min(b,d)).
если max(a,c) > min(b,d), то пересечение пустое
так что программа простая:
1) приводишь прямоугольники (xi, yi) — (xj, yj) к «нормальному» виду
xi < xj, yi < yj
2) находишь пересечения отрезков
(x1, x2) ∩ (x3, x4) = (xA, xB)
(y1, y2) ∩ (y3, y4) = (yA, yB)
3) если пересечения не пустые, считаешь площадь прямоугольника (xA, yA) — (xB, yB)
Категория: Паскаль
Даны два прямоугольника со сторонами параллельными осям координат. Вычислите площадь их общей части (пересечения).
Если прямоугольники не пересекаются, ответ 0.
Ввод
В первой строке описан первый прямоугольник. Для него заданы: x-координата левого нижнего угла, затем y-координата левого нижнего угла, затем x-координата правого верхнего угла, затем y-координата правого верхнего угла.
Во второй строке аналогично задан второй прямоугольник.
Все координаты — целые числа от -100 до 100.
Вывод
Выведите одно целое число — площадь пересечения прямоугольников.
Пример:
Ввод
0 0 2 2
1 1 3 3
Вывод
1
Ввод-вывод консольный (с клавиатуры).
Написано на Pascal (Delphi). Исходный код в ‘Prog.dpr’.
Пересечение прямоугольников
Калькулятор выполняет разбиение пересекающим прямоугольником пересекаемого. В результате разбиения может получиться от одного до четырех новых прямоугольников. В качестве результата выводятся данные таких прямоугольников в виде четырех чисел: координат левого нижнего угла прямоугольника x и y, ширины и высоты.
Обратите внимание, что получающиеся в результате прямоугольники могут накладываться или пересекаться друг с другом. То есть они НЕ являются попарно непересекающимися. Варианты таких прямоугольников приведены на картинке ниже:
Это сделано специально — таким образом решается задача получения максимально возможных размеров новых прямоугольников, что полезно для некоторых алгоритмов, например, для алгоритма максимальных прямоугольников (Maximal Rectangles Algorithm 1 ) используемого для решения задачи двумерной упаковки в контейнеры.