e-maxx_algo

Трёхмерный и многомерный случай

Уже в трёхмерном случае нет простого уравнения, описывающего прямую (её можно задать как пересечение двух плоскостей, т.е. систему двух уравнений, но это неудобный способ).

Следовательно, в трёхмерном и многомерном случаях мы должны пользоваться параметрическим способом задания прямой, т.е. в виде точки и вектора :

Т.е. прямая — это все точки, которые можно получить из точки прибавлением вектора с произвольным коэффициентом.

Построение прямой в параметрическом виде по координатам концов отрезка — тривиально, мы просто берём один конец отрезка за точку , а вектор из первого до второго конца — за вектор .

Точка пересечения прямых

Решение

Если две прямые не параллельны, то они пересекаются. Чтобы найти точку пересечения, достаточно составить из двух уравнений прямых систему и решить её:

Пользуясь формулой Крамера, сразу находим решение системы, которое и будет искомой точкой пересечения:

Если знаменатель нулевой, т.е.

то система решений не имеет (прямые параллельны и не совпадают) или имеет бесконечно много (прямые совпадают). Если необходимо различить эти два случая, надо проверить, что коэффициенты прямых пропорциональны с тем же коэффициентом пропорциональности, что и коэффициенты и , для чего достаточно посчитать два определителя, если они оба равны нулю, то прямые совпадают:

Реализация

struct pt {

double x, y;

};

struct line {

double a, b, c;

};

const double EPS = 1e-9;

double det (double a, double b, double c, double d) { return a * d - b * c;

}

bool intersect (line m, line n, pt & res) { double zn = det (m.a, m.b, n.a, n.b);

if (abs (zn) < EPS) return false;

res.x = - det (m.c, m.b, n.c, n.b) / zn;

res.y = - det (m.a, m.c, n.a, n.c) / zn; return true;

}

bool parallel (line m, line n) {

return abs (det (m.a, m.b, n.a, n.b)) < EPS;

}

bool equivalent (line m, line n) {

return abs (det (m.a, m.b, n.a, n.b)) < EPS

&&abs (det (m.a, m.c, n.a, n.c)) < EPS

&&abs (det (m.b, m.c, n.b, n.c)) < EPS;

}

Пересечение двух отрезков

Даны два отрезка и (они могут вырождаться в точки). Требуется найти их пересечение: оно может быть пустым (если отрезки не пересекаются), может быть одной точкой, и может быть целым отрезком (если отрезки накладываются друг на друга).

Алгоритм

Работать с отрезками будем как с прямыми: построим по двум отрезкам уравнения их прямых, проверим, не параллельны ли прямые. Если прямые не параллельны, то всё просто: находим их точку пересечения и проверяем, что она принадлежит обоим отрезкам (для этого достаточно проверить, что точка принадлежит каждому отрезку в проекции на ось и на ось по отдельности). В итоге в этом случае ответом будет либо "пусто", либо единственная найденная точка.

Более сложный случай — если прямые оказались параллельными (сюда же относится случай, когда один или оба отрезка выродились в точки). В этом случае надо проверить, что оба отрезка лежат на одной прямой (или, в случае когда они оба вырождены в точку — что эта точка совпадает). Если это не так, то ответ — "пусто". Если это так, то ответ

— это пересечение двух отрезков, лежащих на одной прямой, что реализуется достаточно просто — надо взять максимум из левых концов и минимум из правых концов.

В самом начале алгоритма напишем так называемую "проверку на bounding box" — во-первых, она необходима для случая, когда два отрезка лежат на одной прямой, а во-вторых, она, как легковесная проверка, позволяет алгоритму работать в среднем быстрее на случайных тестах.

Реализация

Приведём здесь полную реализацию, включая все вспомогательные функции по работе с точками и прямыми.

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

const double EPS = 1E-9;

struct pt {

double x, y;

bool operator< (const pt & p) const {

return x < p.x-EPS || abs(x-p.x) < EPS && y < p.y - EPS;

}

};

struct line {

double a, b, c;

line() {}

line (pt p, pt q) {

a = p.y - q.y; b = q.x - p.x;

c = - a * p.x - b * p.y; norm();

}

void norm() {

double z = sqrt (a*a + b*b); if (abs(z) > EPS)

a /= z, b /= z, c /= z;

}

double dist (pt p) const {

return a * p.x + b * p.y + c;

}

};

#define det(a,b,c,d) (a*d-b*c)

inline bool betw (double l, double r, double x) {

return min(l,r) <= x + EPS && x <= max(l,r) + EPS;

}

inline bool intersect_1d (double a, double b, double c, double d) { if (a > b) swap (a, b);

if (c > d) swap (c, d);

return max (a, c) <= min (b, d) + EPS;

}

bool intersect (pt a, pt b, pt c, pt d, pt & left, pt & right) {

if (! intersect_1d (a.x, b.x, c.x, d.x) || ! intersect_1d (a.y, b.y,

c.y, d.y))

return false; line m (a, b);

line n (c, d);

double zn = det (m.a, m.b, n.a, n.b); if (abs (zn) < EPS) {

if (abs (m.dist (c)) > EPS || abs (n.dist (a)) > EPS) return false;

if (b < a) swap (a, b); if (d < c) swap (c, d); left = max (a, c);

right = min (b, d); return true;

}

else {

left.x = right.x = - det (m.c, m.b, n.c, n.b) / zn; left.y = right.y = - det (m.a, m.c, n.a, n.c) / zn; return betw (a.x, b.x, left.x)

&&betw (a.y, b.y, left.y)

&&betw (c.x, d.x, left.x)

&&betw (c.y, d.y, left.y);

}

}

Нахождение площади простого многоугольника

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

Способ 1

Это легко сделать, если перебрать все рёбра и сложить площади трапеций, ограниченных каждым ребром.

Площадь нужно брать с тем знаком, с каким она получится (именно благодаря знаку вся "лишняя" площадь сократится). Т.е. формула такова:

S += (X2 - X1) * (Y1 + Y2) / 2

Код:

double sq (const vector<point> & fig)

{

double res = 0;

for (unsigned i=0; i<fig.size(); i++)

{

point

p1 = i ? fig[i-1] : fig.back(),

p2 = fig[i];

res += (p1.x - p2.x) * (p1.y + p2.y);

}

return fabs (res) / 2;

}

Способ 2

Можно поступить другим образом. Выберем произвольно точку O, переберём все рёбра, прибавляя к ответу ориентированную площадь треугольника, образованного ребром и точкой O (см. Ориентированная

площадь треугольника). Опять же, благодаря знаку, вся лишняя площадь сократится, и останется только ответ.

Этот способ хорош тем, что его проще обобщить на более сложные случаи (например, когда некоторые стороны - не прямые, а дуги окружности).

Теорема Пика. Нахождение площади решётчатого многоугольника

Многоугольник без самопересечений называется решётчатым, если все его вершины находятся в точках с целочисленными координатами (в декартовой системе координат).

Теорема Пика

Формула

Пусть дан некоторый решётчатый многоугольник, с ненулевой площадью.

Обозначим его площадь через ; количество точек с целочисленными координатами, лежащих строго внутри многоугольника — через ; количество точек с целочисленными координатами, лежащих на сторонах многоугольника — через .

Тогда справедливо соотношение, называемое формулой Пика:

В частности, если известны значения I и B для некоторого многоугольника, то его площадь можно посчитать за

, даже не зная координат его вершин.

Это соотношение открыл и доказал австрийский математик Георг Александр Пик (Georg Alexander Pick) в 1899 г.

Доказательство

Доказательство производится в несколько этапов: от самых простых фигур до произвольных многоугольников:

●Единичный квадрат. В самом деле, для него , , , и формула верна.

●Произвольный невырожденный прямоугольник со сторонами, параллельными осям координат. Для

Пика верна.

●Прямоугольный треугольник с катетами, параллельными осям координат. Для доказательства заметим, что любой

такой треугольник можно получить отсечением некоторого прямоугольника его диагональю. Обозначив через число целочисленных точек, лежащих на диагонали, можно показать, что формула Пика выполняется для такого треугольника, независимо от значения .

●Произвольный треугольник. Заметим, что любой такой треугольник может быть превращён в прямоугольник приклеиванием к его сторонам прямоугольных треугольников с катетами, параллельными осям

координат (при этом понадобится не более 3 таких треугольников). Отсюда можно получить корректность формулы Пика для любого треугольника.

●Произвольный многоугольник. Для доказательства триангулируем его, т.е. разобьём на треугольники с вершинами в целочисленных точках. Для одного треугольника формулу Пика мы уже доказали. Дальше, можно доказать, что при добавлении к произвольному многоугольнику любого треугольника формула Пика сохраняет свою корректность. Отсюда по индукции следует, что она верна для любого многоугольника.

Обобщение на высшие размерности

К сожалению, эта столь простая и красивая формула Пика плохо обобщается на высшие размерности.

Наглядно показал это Рив (Reeve), предложив в 1957 г. рассмотреть тетраэдр (называемый теперь тетраэдром Рива) со следующими вершинами:

Таким образом, объём и площадь поверхности этого тетраэдра могут быть разными, в то время как число точек внутри и на границе — неизменны; следовательно, формула Пика не допускает обобщений даже на трёхмерный случай.

Тем не менее, некоторое подобное обобщение на пространства большей размерности всё же имеется, —

это многочлены Эрхарта (Ehrhart Polynomial), но они весьма сложны, и зависят не только от числа точек внутри и на границе фигуры.

Задача о покрытии отрезков точками

Дано N отрезков на прямой. Требуется покрыть их наименьшим числом точек, т.е. найти наименьшее множество точек такое, что каждому отрезку принадлежит хотя бы одна точка.

Также рассмотрим усложнённый вариант этой задачи - когда дополнительно указано "запрещённое" множество отрезков, т.е. никакая точка из ответа не должна принадлежать ни одному запрещённому отрезку.

Следует также заметить, что эту задачу можно рассматривать и как задачу в теории расписаний - требуется покрыть заданный набор мероприятий-отрезков наименьшим числом точек.

Ниже будет описан жадный алгоритм, решающий обе задачи за O (N log N).

Решение первой задачи

Заметим сначала, что можно рассматривать только те решения, в которых каждая из точек находится на правом конце какого-либо отрезка. Действительно, нетрудно понять, что любое решение, если оно не удовлетворяет этому свойству, можно привести к нему, сдвигая его точки вправо настолько, насколько это возможно.

Попытаемся теперь построить решение, удовлетворяющее указанному свойству. Возьмём точки-правые концы отрезков, отсортируем их, и будем двигаться по ним слева направо. Если текущая точка является правым концом уже покрытого отрезка, то мы пропускаем её. Пусть теперь текущая точка является правым концом текущего отрезка, который ещё не был покрыт до этого. Тогда мы должны добавить в ответ текущую точку, и отметить все отрезки, которым принадлежит эта точка, как покрытые. Действительно, если бы мы пропустили текущую точку и не стали бы добавлять её в ответ, то, так как она является правым концом текущего отрезка, то мы уже не смогли бы покрыть текущий отрезок.

Однако при наивной реализации этот метод будет работать за O (N2). Опишем эффективную реализацию этого метода.

Возьмём все точки-концы отрезков (как левые, так и правые) и отсортируем их. При этом для каждой точки сохраним вместе с ней номер отрезка, а также то, каким концом его она является (левым или правым). Кроме того, отсортируем точки таким образом, что, если есть несколько точек с одной координатой, то сначала будут идти

левые концы, и только потом - правые. Заведём стек, в котором будут храниться номера отрезков, рассматриваемых в данный момент; изначально стек пуст. Будем двигаться по точкам в отсортированном порядке. Если текущая точка - левый конец, то просто добавляем номер её отрезка в стек. Если же она является правым концом, то проверяем, не был ли покрыт этот отрезок (для этого можно просто завести массив булевых переменных). Если он уже был покрыт, то ничего не делаем и переходим к следующей точке (забегая вперёд, мы утверждаем, что в этом случае в стеке текущего отрезка уже нет). Если же он ещё не был покрыт, то мы добавляем текущую точку в ответ, и теперь мы хотим отметить для всех текущих отрезков, что они становятся покрытыми. Поскольку в стеке как раз хранятся номера непокрытых ещё отрезков, то будем доставать из стека по одному отрезку и отмечать, что он уже покрыт, пока стек полностью не опустеет. По окончании работы алгоритма все отрезки будут покрыты, и притом наименьшим числом точек (повторимся, здесь важно требование, что при равенстве координат сначала идут левые концы, и только затем правые).

Таким образом, весь алгоритм выполняется за O (N), не считая сортировки точек, а итоговая сложность алгоритма как раз равна O (N log N).

Решение второй задачи

Здесь уже появляются запрещённые отрезки, поэтому, во-первых, решения вообще может не существовать, а вовторых, уже нельзя утверждать, что ответ можно составить только из правых концов отрезков. Однако описанный выше алгоритм можно соответствующим образом модифицировать.

Снова возьмём все точки-концы отрезков (как целевых отрезков, так и запрещённых), отсортируем их, сохранив вместе с каждой точкой её тип и отрезок, концом которого она является. Опять же, отсортируем отрезки так, чтобы при равенстве координат левые концы шли перед правыми, а если и типы концов равны, то левые концы запрещённых должны идти перед левыми концами целевых, а правые концы запрещённых - после целевых (чтобы запрещённые отрезки учитывались как можно дольше при равенстве координат). Заведём счётчик запрещённых отрезков, который будет равен числу запрещённых отрезков, покрывающих текущую точку. Заведём очередь (queue), в которой будут храниться номера текущих целевых отрезков. Будем перебирать точки

вотсортированном порядке. Если текущая точка - левый конец целевого отрезка, то просто добавим номер её отрезка

вочередь. Если текущая точка - правый конец целевого отрезка, то, если счётчик запрещённых отрезков равен нулю, то мы поступаем аналогично предыдущей задаче - ставим точку в текущую точку, и выталкиваем все отрезки из очереди, отмечая, что они покрыты. Если же счётчик запрещённых отрезков больше нуля, то в текущую точку мы стрелять не можем, а потому мы должны найти самую последнюю точку, свободную от запрещённых отрезков; для этого надо поддерживать соответствующий указатель last_free, который будет обновляться при поступлении запрещённых отрезков. Тогда мы стреляем в last_free-EPS (потому что прямо в неё нельзя стрелять - эта

точка принадлежит запрещённому отрезку), и выталкивать отрезки из очереди, пока точка last_free-EPS принадлежит им. А именно, если текущая точка - левый конец запрещённого отрезка, то мы увеличиваем счётчик, и если перед этим

счётчик был равен нулю, то присваиваем last_free текущую координату. Если текущая точка - правый конец

запрещённого отрезка, то просто уменьшаем счётчик.