Ответы:
площадь прямоугльника - это произведение длин сторон. длина стороны вычисляется по формуле - корень квадратный из (x1-x2)^2+(y1-y2)^2, (x1,y1) - координаты первой точки отрезка, (x2,y2)-координаты второй точки отрезка.
Если стороны прямоугольников не параллельны осям координат, то в любом случае придется искать точки пересечения сторон одного прямоугольника со сторонами другого. А дальше разбор случаев, когда в пересечении треугольник, четырехугольник, и так до восьмиугольника.
Есть еще вариант, он проще для реализации, но не знаю, насколько он правильный. Нам нужно определить углы фигуры F - пересечения прямоугольников. Если угол одного прямоугольника лежит внутри другого (включая границу), то это угол F. Точка пересечения сторон прямоугольников - тоже угол F. Больше углов у F нет (?). Дальше нужно все углы F упорядочить (по часовой стрелке или против - неважно). Для этого можно взять центр тяжести (среднее арифметическое координат) и отсортировать вершины по полярному углу относительно этого центра. Таким образом, мы получим упорядоченные координаты фигуры F. Для вычисления площади такой фигуры по координатам есть простая формула (иногда ее называют формулой трапеций).
1)Находим координаты вершин образованой фигуры.
2)Составляем аналитический график ломаных, ограничивающих фигуру сверху и снизу.
3)Интегрируем эти графики, и вычитаем нижний из верхнего.
Если стороны прямоугольников параллельны осям координат, то, разумеется, все проблемы отпадают.
Пусть (x1, y1) и (x2, y2) - координаты левого верхнего и правого нижнего угла первого прямоугольника,
(x3, y3) и (x4, y4) - координаты левого верхнего и правого нижнего угла второго прямоугольника.
Тогда площадь пересечения равна
max(min(x2, x4) - max(x1, x3), 0) * max(min(y2, y4) - max(y1, y3), 0)
Вроде так.
Проще всего реализовать наверно так:
Я предлагаю перейти в систему отсчёта, связанную с одним из прямоугольников и поместить одну из его вершин в начало координат.
мне кажется проще всего разбить фигуры на "полосы", параллельные какой-нибудь оси, например y. для этого нужно просто выписать х-координаты всех точек двух прямоугольников.
дальше идем по этим иксам от меньшего к большему и в каждой полосе находим, какая часть каждого прямоугольника и общей части находится в этой полосе.
так количество разных случаев сведется к минимуму
> alarmeria, что вы понимаете под "общей точкой"?
По-моему, самый простой подход - это выполнить над системой координат преобразование, которое перенесет один из прямоугольников в начало координат (см. аффинные преобразования на плоскости - потребуется поворот и масштабирование). Так задача уже инутитивно выглядит намного проще, поскольку один из прямоугольников лежит левым нижним углом на осях координат. А дальше я предложил бы такой подход:
Блин, не масштабирование, а перемещение, конечно. Заговорился :)
Первый вариант - рассмотреть все возможные случаи и аккуратно их описать в программе. Будет быстро работать, но писать нужно очень внимательно.
1) найти перескаются - ли прямоугольники
2) Найти фигуру пересечения ( Это может быть треугольник, четырехугольник, пятиугольник или шестиугольник )
3) Расчитать площадь получившейся фигуры, предварительно разбив ее на треугольники ( благо что фигура выпуклая )
Ко второму варианту Blackman-а + Дополнение #3 (вместе они составляют единственный содержательный ответ) варианту добавлю, что
Для вычисления площади есть очень ценная формула (дающая ответ и простая в реализации).
Площадь плоского несамопересекающегося многоугольника с вершинами (x1,y1),(x2,y2),...,(xn,yn) равна
S = 1/2 * Модуль(
x1 y2 - x2 y1 +
x2 y3 - x3 y2 +
... +
+x(n-1) yn - xn y(n-1) +
+xn y1 - x1 yn
)
Метод, приведенный в дополнении №3 очень хороший и простой и работать будет быстро.
Что касается замечания о упорядочивании вершин, так оно не так уж и сложно.
Находим любую точку внутри образовавшегося многоугольника (это любая общая точка прямоугольников).
Дальше для каждой вершины многоугольника вычисляем полярный угол ОТНОСИТЕЛЬНО ЭТОЙ ТОЧКИ (для определённости из диапазона [0;2 пи) или (-пи;пи], программистам на C для этой цели можно использовать функцию atan2).
Сортируя по углам упорядочим вершины. Можно сразу же и посчитать площадь, как сумму площадей треугольников (одной из вершин каждого треугольника является выбранная точка внутри, а остальными -- две соседние вершины многоугольника) или по формуле.
Решаю задачи Паскаль(Делфи) [30-100р в зависимости от сложности] оплата деньги на счет. моб. оператора -->
[email protected]
Помощь по Pascal, С, С++. Лаб. работы, задания. Недорого
Ящик
[email protected]
Сразу кидайте задания, чтобы можно было оценить их сложность и стоимость, соответственно
и что у вас получилось? можно получившийся код просмотреть? у меня похожая задача, только дано не 2 прямоугольника, а неизвестное количество.
а если смотреть не как координаты, а просто как матрицу заполненную нулями? а площади прямоугольников разбить как единичные площади, то есть если треугольник 3х5 то будет 15 единиц в матрице!
это разрешит проблему в пересечением так как в конце просто проходим матрицу и считаем количество единиц, пускай хоть пять прямоугольников наложились и пересеклись...все равно сколько в матрицу на одно и тоже место записать единиц)
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
-----------------------------------------
00000001111000000000000
00000001111000000000000
0000111111111111111000000
0000111111111111111000000
00000001111000000000000
15 лет назад