Алгоритмы C++

const double EPS = 1E-9;

bool in (int a, int b, double c) {

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

}

bool intersect_1 (int a, int b, int c, int d) {

return max (a, b) >= min (c, d) && max (c, d) >= min (a, b);

}

bool intersect (pt a, pt b, pt c, pt d) {

int A1 = a.y-b.y, B1 = b.x-a.x, C1 = -A1*a.x - B1*a.y; int A2 = c.y-d.y, B2 = d.x-c.x, C2 = -A2*c.x - B2*c.y; int zn = det (A1, B1, A2, B2);

if (zn != 0) {

double x = - det (C1, B1, C2, B2) * 1. / zn; double y = - det (A1, C1, A2, C2) * 1. / zn; return in (a.x, b.x, x) && in (a.y, b.y, y)

&& in (c.x, d.x, x) && in (c.y, d.y, y);

}

else

return det (A1, C1, A2, C2) == 0 && det (B1, C1, B2, C2) == 0

&&intersect_1 (a.x, b.x, c.x, d.x)

&&intersect_1 (a.y, b.y, c.y, d.y);

}

ипрямых пропорциональны, и прямые параллельны или совпадают. В этом случае надо проверить, совпадают они

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

Нахождение уравнения прямой для отрезка

Уравнение прямой имеет вид A x + B y + C = 0. Найдём значения коэффициентов A, B, C для любого заданного отрезка.

Понятно, что, вообще говоря, таких наборов значений существует бесконечное множество.

Способ 1

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

Вот готовые формулы для не вертикальных прямых (их легко получить, если представить уравнение прямой в виде y = K x + B):

A = - (Y1 - Y2) / (X1 - X2),

B = 1,

C = - (A * X1) - (B * Y1)

Для вертикальных прямых имеем:

A = 1,

B = 0,

C = - X1

Реализация:

struct segment {

double x1, y1, x2, y2;

};

struct line {

double a, b, c;

};

const double EPS = 1e-6;

bool eq (double a, double b)

{

return fabs (a-b) < EPS;

}

void segment_to_line (const segment & s, line & l)

{

if (eq (s.x1, s.x2))

{

l.a = 1; l.b = 0;

l.c = - s.x1;

}

else

{

l.a = - (s.y1 - s.y2) / (s.x1 - s.x2); l.b = 1;

l.c = - (l.a * s.x1 + l.b * s.y1);

}

}

Способ 2

По-другому избежать неоднозначности можно следующим образом:

A = Y1 - Y2

B = X2 - X1

C = - (A X1 + B Y1)

В корректности этих формул можно убедиться непосредственной подстановкой.

Способ 2 обычно лучше способа 1 в том смысле, что если все координаты целочисленные, то и коэффициенты в уравнении прямой также получатся целочисленными.

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

Решение

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

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

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

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

Реализация

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;

}

Точка пересечения отрезков

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

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

Реализация

int segments_intersection (segment s1, segment s2, point & p1, point & p2)

{

if (!intersect (s1, s2)) return 0;

if (s1 == s2)

{

p1.x = s1.x1; p1.y = s2.y1; return 1;

}

line l1, l2; segment_to_line (s1, l1); segment_to_line (s2, l2); if (!same_line (l1, l2))

{

lines_intersection (l1, l2, p1); return 1;

}

if (s1.x1 > s1.x2 || s1.x2 == s1.x2 && s1.y1 > s1.y2)

swap (s1.x1, s1.x2), swap (s1.y1, s1.y2);

if (s2.x1 > s2.x2 || s2.x1 == s2.x2 && s2.y1 > s2.y2) swap (s2.x1, s2.x2), swap (s2.y1, s2.y2);

if (s1.x1 > s2.x1 || s1.x1 == s2.x1 && s1.y1 > s2.y1) p1.x = s1.x1, p1.y = s1.y1;

else

p1.x = s2.x1, p1.y = s2.y1;

if (s1.x2 < s2.x2 || s1.x2 == s2.x2 && s1.y2 < s2.y2) p2.x = s1.x2, p2.y = s1.y2;

else

p2.x = s2.x2, p2.y = s2.y2; if (p1 == p2)

return 1; return 2;

}

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

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