Алгоритмы с треугольником на Python. Вычисление углов по координатам вершин. Вычисление площади по координатам вершин
Снова возвращаюсь к моему любимому разделу (подборке), касающемуся алгоритмов. Их великое множество. Вот сегодня начнём серию алгоритмов геометрических, на плоскости. Кстати часто на олимпиадах по программированию возникает как подзадача необходимость именно каких-то геометрических вычислений. И участники тратят много времени, чтобы самим выводить нужные формулы. А если знать хотя-бы путь выведения формулы, пригодной для вычисления, то всё было бы гораздо быстрее.
Сегодня о треугольниках. Часто треугольник задаётся тремя вершинами, т.е. координатами вершин и нужно вычислить углы треугольника. Ну, а также его площадь. На рисунке 1 представлен такой треугольник.
На самом деле задав вершины, мы задали также и три отрезка (см. Рисунок 1): (x1, y1, x2, y2), (x2, y2, x3, y3), (x1, y1, x3, y3). Отрезок, как известно, направления не имеет, поэтому концы можно указывать в любом порядке.
Но когда мы говорим об углах, удобнее использовать формулы векторной геометрии. Отличие вектора от отрезка во-первых в том, что у вектора есть направление, во-вторых, координатами вектора называются разности координат конца и начала вектора. Например, для вектора с координатами начала x3, y3 и координатами конца x1, y1 (см. Рисунок 1) координатами вектора называются (x1-x3) и (y1-y3). Длина вектора определяется как квадратный корень из суммы квадратов его координат:
sqrt((x1-x3)*(x1-x3) + (y1-y3)*(y1-y3)).
Или введя обозначения для координат вектора ax и ay
sqrt(ax*ax + ay*ay).
Наконец, есть такая вещь как скалярное произведение векторов (пусть это вектора a и b)
scal = |a|*|b|*cos(β), |a| и |b| - длины векторов, β - угол между векторами (см. Рисунок 1).
Прелесть скалярного произведения заключается в том, что оно может быть вычислено и другим способом
scal = ax*bx + ay*by
Я это не доказываю, так как всё таки это статья не математическая.
Таким образом, мы легко можем вычислить косинус угла между векторами и, соответственно, сам угол.
Напишем теперь программу, которая по координатам вершин определяет углы треугольника. Здесь уже нет ничего сложного, только не запутаться в координатах (рисунок 2).
В программе используется стандартная библиотека math (см. статью).
Например для координат на входе:
7 3 7 6 2 1
Получаем углы в радинах и градусах
1.9513027039072615 111.80140948635182
0.7853981633974484 45.00000000000001
0.40489178628508365 23.198590513648202
Вычислить площадь теперь уже не составляет никакого труда.
S = 0.5*sin(β)*a*b
Если не понятно, то sin(β)*a - высота треугольника на сторону b.
Программа вычисления площади треугольника по координатам вершин представлена ниже (рисунок 3)
На входе
7 3 7 6 2 1
Получаем площадь
7.5
Замечание
Впрочем есть ещё формула Герона: s = p(p − a)(p − b)(p − c), здесь a,b,c - стороны треугольника, p - половина периметра треугольника, т.е. (a+b+c)/2. Можно было использовать и её, ведь длины сторон мы вычисляем легко.
Пока всё!
Пишите свои предложения и замечания, и занимайтесь программированием, а также проектированием баз данных, хотя бы для поддержания уровня интеллекта.