SERGE_BLIZNUK
Silver Member | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
druff
смотрите, вариант по принципу интергрирования.
идём по оси X с бесконечно малым шагом. (шаг в принципе будет определять точность.)
ну, например, если координаты имеют точность 3 знака после запятой, то шага 0.001 будет вполне достаточно.
На каждом шаге получаем площадь фигуры образованной Xi-1 и Xi (т.к. шаг меньше точности координат, то вертикальная линия любого прямоугольника попасть в середину шага НЕ МОЖЕТ. все полученные площади суммируются.
Это решение достаточно простое. Но, разумеется, потребует ОЧЕНЬ много вычислений (циклов).
другой вариант, который я предлагал (и реализовал) на программерсфоруме.
Сортируем массив по левым сторонам всех прямоугольников.
в цикле выбрасываем все прямоугольники, которые полностью лежат внутри других (проверяем перебором в цикле "каждый с каждым").
дальше рассматриваем участок "непрерывности" площади это участок, от одной границы текущего прямоугольника до любой ближайшей справа.
(в вашем примере 1-й диапазон непрерывности: A-B, второй: C, третий D и т.п.
В этом диапазоне гарантировано не может изменяться площадь.
находим площадь данного диапазона. идём на следующий и т.д.
сумма всех площадей и даст искомую общую площадь.
в качестве оптимизации можно так же в цикле проверить, если прямоугольник ни с кем не пересекается, то его площадь добавить в итоговую и убрать его из обрабатываемой очереди...
p.s. я интуитивно чувствую, что murkovich предлагает что-то аналогичное. Поэтому и попросил его расшифровать (расписать подробнее) предложенный алгоритм.
ДОБАВЛЕНО
я тут подумал... первый вариант (через бесконечно малые срезы) уж очень некрасивый..
я бы КРАЙНЕ не рекомендовал его рассматривать как основной...
|
