Плюшевая геометрия (информатика)

Учимся вычислять площадь.

Изначально достаточно знать формулу измерения площади прямоугольника. Из нее легко (разрезаниями, перекладываниями кусочков) получить формулы для площади параллелограмма, треугольника, трапеции.

Прямоугольник со сторонами a, b: a * b.

Параллелограмм со стороной a, высотой h: a * h.

Треугольник со сторонами a, b, c: sqrt(p * (p - a) * (p - b) * (p - c))

Треугольник со основанием c, высотой h: ½ c * h

Трапеция со сторонами a, b, высотой h: ½ (a + b) * h

Научимся вычислять площадь "кроссворда" — многоугольника со сторонами параллельными осям координат. Многоугольник задан последовательностью координат своих вершин и расположен в первой координатной четверти.

Последовательно идем от вершины к вершине. Если идем по вертикали, то не делаем ничего, если по горизонтали вправо, то прибавляем площадь прямоугольника под этим отрезком, если влево — вычитаем площадь прямоугольника под этим отрезком. Если мы обходили многоугольник по часовой стрелке, мы получим его площадь, а если против — его площадь со знаком минус, то есть, результат надо взять модуль результата.

Теперь возьмем произвольный многоугольник с вершинами в узлах сетки. Многоугольник по-прежнему задан последовательностью координат своих вершин и расположен в первой координатной четверти.

Последовательно идем от вершине к вершине, с каждой стороной прибавляя (или вычитая) трапецию под ней. Например, идя от первой вершины ко второй, прибавляем к общей площади (y1 + y2) * (x2 - x1) / 2. Действительно, y1 и y1 — основания трапеции, (x2 - x1) — ее высота. Причем, если x2 < x1, то мы идем налево и площадь трапеции войдет в общую сумму со знаком минус, что нам и нужно.

Привязку к сетке мы нигде не используем, поэтому вершины можно расположить где угодно, не обязательно в узлах.
Прибавив одно и то же число ко всем координатам y (подвинув ось x), можно всегда добиться расположения многоугольника в первой четверти. Вообще от движения оси x, формула подсчета не меняется, поэтому многоугольник может быть расположен, где угодно. В этом месте на этой лекции у меня возникла интересная дискуссия о смысле формулы (y1 + y2) * (x2 - x1) / 2, если сторона пересекает ось x. Куда делись трапеции? Почему мы по-прежнему считаем площадь между отрезком и осью (тут надо не забыть про знак)?
Если первую вершину многоугольника дописать в массив вершин после последней, то последняя сторона обрабатывается тем же циклом, что и все остальные.

Применяем измерение площадей.

Чтобы проверить лежит ли точка на прямой, проходящей, через две другие точки, посчитаем площадь треугольника с вершинами в этих трех точках.
Проверим лежит ли точка внутри выпуклого многоугольника. Сравним площадь этого многоугольника и сумму площадей треугольников с вершинами: две последовательные вершины многоугольника и данная точка.
Cчитая площади треугольников, надо не забыть, что они бывают отрицательными. И если про это забыть и просуммировать площади треугольников взятые с их знаками, то всегда получится площадь многоугольника, даже если точка вне него.
Также не вредно понять, зачем требование выпуклости многоугольника.

Пересечение прямоугольников на плоскости

Для того, чтобы задать прямоугольник, стороны которого параллельны осям координат, надо знать две его противоположные вершины. Можно считать, что это нижняя левая и верхняя правая (если это не так, то приведем данные к такому виду)
Даны несколько таких прямоугольников. Их пересечение, если не пусто, тоже является таким прямоугольником. Нужно найти две вершины, задающие его.
Тут полезно осознать сначала задачу о пересечении отрезков на прямой. А потом понять, что для каждой координаты у нас как раз решается задача об отрезках.

Площадь объединения прямоугольников на плоскости

Даны несколько прямоугольников, как в предыдущей задаче, с вершинами в узлах сетки. Нужно найти площадь их объединения.
Полезно понять, что их объединение вовсе не обязательно прямоугольник, и вообще, может не быть многоугольником.
Заведем двумерный массив, каждая ячейка которого соответствует клетке на сетке, заполним его нулями. Размеры выберем так, чтобы все прямоугольники заведомо были внутри. Для каждого прямоугольника прибавим единички к тем клеткам, которые он занимает. Потом по этому массиву посчитаем площадь занятых клеток. Также можно посчитать площадь области, покрытой двумя прямоугольниками и т.п.
Для этого способа требуется много памяти. Если стороны прямоугольников большие (или вычислены с высокой точностью), а самих прямоугольников немного, то полезно применить сжатие координат. Сохраним массив координат по оси x, массив координат по оси y, отсортируем эти массивы по возрастанию. Для каждого прямоугольника отыщем его конец и начало в этих массивах (бинарный поиск) и прибавим единичку к соответствующим ячейкам двумерного массива. Теперь двумерный массив нужен размера 2n x 2n, где n — количество прямоугольников. По сути, в качестве границ клеток сетки теперь используются только те горизонтали и вертикали, через которые проходят стороны прямоугольника.
Посмотрим теперь, что будет для задачи объединения отрезков на прямой. Можно действовать аналогично, но можно проще: упорядочиваем все координаты концов отрезков, но про каждую из них помним начинается в ней отрезок или заканчивается. Идем от самой меньшей к самой большей и встречая конец отрезка, увеличиваем счетчик количества отрезков, а встречая начало отрезка, уменьшаем счетчик количества отрезков. Теперь мы знаем, на каком участке прямой сколько отрезков и можем найти длину объединения, само объединение, область, покрытую двумя отрезками и т.п.
Здесь есть тонкость, что концы и начала некоторых отрезков могут совпасть. И при сортировке можно сначала расположить все начала, а потом все концы с одинаковой координатой, можно наоборот. То, как надо поступить, зависит от задачи. Для вычисления длины, например, не важно, для нахождения объединения отрезков сначала должны быть начала, а для объединения интервалов, сначала должны быть концы.
Полезно также понять, почему такой подход не работал для площади объединения прямоугольников.