Здравствуй. Во время похождения по итернетам в поисках годного алгоритма на эту тему я увидел одну интересную идею, которую на досуге развил и дополнил. Наверное, каждый более-менее опытный кодер встречал типовую задачу на пресечение нескольких прямоугольников в системе координат. Насколько я понял, вопрос годного алгоритма остается открытым, а потому я решил предложить свой.
Давайте возьмем гипотетическую задачу:
Существует система координат, в которой расположено N-ное количество прямоугольников, параллельных осям координат, которые заданы координатами левой нижней и правой верхней вершины прямоугольника. Требуется найти общую площадь, занимаемую прямоугольниками.
- Первым делом требуется создать 2 массива, один одномерный, другой двумерный. В первом массиве мы будем хранить координаты всех точек, второй будет представлять собой координатную плоскость
- Так же, нам надо запомнить самую маленькую и самую большую координату по оси ординат. Тоже и с осью абсцисс. Этими точками мы задаем размеры второго массива. Это нам надо для того, чтобы убедиться, что область, которую мы будем рассматривать (назовем ее областью А), полностью покрывает нашу зону интереса, что является необходимым и достаточным условием.
- Следом, мы проецируем прямоугольники на область А, т.е. координаты прямоугольников будут эквивалентны номерам некоторым элементам массива со смещением.
- Затем начинаем заполнять этот массив. Элементы этого массива могут принимать два значения: 0 и 1. 0 означает, что это «клеточка» не принадлежит ни одному прямоугольнику, 1- принадлежит. Проверяем элементы области А на принадлежность прямоугольнику для каждого отдельного прямоугольника. 1 не может быть заменен на 0. 0 может быть заменен на 1. Таким образом, мы получим матрицу, которая будет состоять из нулей и единиц, где единицами будут «нарисованы» прямоугольники.
- Последним пунктом, считаем сумму всех элементов массива. Задача решена!
В заключение статьи хотелось бы рассказать об плюсах и минусах данного алгоритма.
Плюсы:
— Скорость работы при прочих равных напрямую зависит от количества данных прямоугольников и их разброса.
— Нет кучи условных операторов, которые сильно портят жизнь.
— Не надо отслеживать пересечения прямоугольников, те «клетки», которые принадлежат двум или более прямоугольникам все равно будут посчитаны только 1 раз.
— Высокая читаемость кода (при достаточно прямых руках).
— Простота реализации.
— Одинаковый алгоритм обработки для всех частей координатной плоскости.
Минусы:
— Требует достаточно хорошего пространственного воображения.
— Наличие достаточно большого количества циклов.
— Не подходит для большинства задач даже с незначительно измененными условиями.
