- PVSM.RU - https://www.pvsm.ru -
Здравствуй. Во время похождения по итернетам в поисках годного алгоритма на эту тему я увидел одну интересную идею, которую на досуге развил и дополнил. Наверное, каждый более-менее опытный кодер встречал типовую задачу на пресечение нескольких прямоугольников в системе координат. Насколько я понял, вопрос годного алгоритма остается открытым, а потому я решил предложить свой.
Существует система координат, в которой расположено N-ное количество прямоугольников, параллельных осям координат, которые заданы координатами левой нижней и правой верхней вершины прямоугольника. Требуется найти общую площадь, занимаемую прямоугольниками.
В заключение статьи хотелось бы рассказать об плюсах и минусах данного алгоритма.
— Скорость работы при прочих равных напрямую зависит от количества данных прямоугольников и их разброса.
— Нет кучи условных операторов, которые сильно портят жизнь.
— Не надо отслеживать пересечения прямоугольников, те «клетки», которые принадлежат двум или более прямоугольникам все равно будут посчитаны только 1 раз.
— Высокая читаемость кода (при достаточно прямых руках).
— Простота реализации.
— Одинаковый алгоритм обработки для всех частей координатной плоскости.
— Требует достаточно хорошего пространственного воображения.
— Наличие достаточно большого количества циклов.
— Не подходит для большинства задач даже с незначительно измененными условиями.
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/pesochnitsa/73151
Нажмите здесь для печати.