Геометрические этюды Введение А.Г.Баханский © Программирование – вторая грамотность. А.П.Ершов

Оглавление Площадь треугольника Площадь многоугольника Задача о площади многоугольника Ориентация треугольника Задача о выпуклости многоугольника Задача о штрафах за левый поворот Задача о пересечении отрезков Задача о расположении точки относительно многоугольника Расстояние от точки до прямой (плоскости)

Вспомним!!! Теорема. Площадь прямоугольной трапеции равна половине произведения суммы оснований на высоту. S=1/2(a+b)h h a b

Площадь треугольника Теорема. Площадь треугольника, заданного на плоскости координатами своих вершин (x 1,y 1 ), (x 2,y 2 ) и (x 3,y 3 ), равна S=1/2|(x 1 -x 2 ) (y 1 +y 2 )+ (x 2 -x 3 ) (y 2 +y 3 )+ (x 3 -x 1 ) (y 3 +y 1 )|

S1S1 S2S2 S3S3 x y O (x 1,y 1 ) (x 2,y 2 ) (x 3,y 3 ) S=1/2|(x 1 -x 2 ) (y 1 +y 2 )+ (x 2 -x 3 ) (y 2 +y 3 )+ (x 3 -x 1 ) (y 3 +y 1 )| Убедимся в этом S 1 =1/2 (x 1 -x 2 ) (y 1 +y 2 ) S 2 =1/2 (x 2 -x 3 ) (y 2 +y 3 ) S 3 =1/2 (x 1 -x 3 ) (y 3 +y 1 ) S=S 1 +S 2 -S 3 А зачем модуль?

x y O (x 1,y 1 ) (x 2,y 2 ) (x 3,y 3 ) S=1/2|(x 1 -x 2 ) (y 1 +y 2 )+ (x 2 -x 3 ) (y 2 +y 3 )+ (x 3 -x 1 ) (y 3 +y 1 )| Для другой ориентации треугольника

Три точки на плоскости с координатами (x 1,y 1 ), (x 2,y 2 ) и (x 3,y 3 ) лежат на одной прямой тогда и только тогда, когда (x 1 -x 2 ) (y 1 +y 2 )+ (x 2 -x 3 ) (y 2 +y 3 )+ (x 3 -x 1 ) (y 3 +y 1 )=0 Следствие

Площадь многоугольника Теорема. Площадь n-угольника, заданного на плоскости координатами своих вершин (x 1,y 1 ), (x 2,y 2 ), …, (x n,y n ) в порядке обхода, равна S=1/2|(x 1 -x 2 ) (y 1 +y 2 )+ (x 2 -x 3 ) (y 2 +y 3 )+ … +(x n-1 -x n ) (y n-1 +y n )+ +(x n -x 1 ) (y n +y 1 )|

Это легко увидеть из рисунка x y O (x 1,y 1 ) (x 2,y 2 ) (x 3,y 3 ) S=1/2|(x 1 -x 2 ) (y 1 +y 2 )+ (x 2 -x 3 ) (y 2 +y 3 )+ (x 3 -x 4 ) (y 3 +y 4 ) + +(x 4 -x 5 ) (y 4 +y 5 ) + (x 5 -x 1 ) (y 5 +y 1 ) | (x 4,y 4 ) (x 5,y 5 )

Задача о площади многоугольника Задача о площади многоугольника Найти площадь многоугольника, заданного на плоскости координатами своих вершин в порядке обхода. Ваша программа должна запросить число вершин, координаты каждой вершины и вычислить и сообщить площадь многоугольника.

Математическая модель Аргументы n – число сторон (вершин) многоугольника, целое, большее 2 x[1..n+1] – абсциссы вершин, вещественные y[1..n+1] – ординаты вершин, вещественные x[n+1]:=x[1], y[n+1]=y[1] Результаты S – площадь треугольника, вещественное Промежуточные величины i – счетчик цикла, целое

Число вершин? n Начало i=1,n Координаты i-ой вершины? x[i],y[i] x[n+1]:=x[1] y[n+1]:=y[1] 1 1 S:=0 i=1,n S:=S+(x[i]-x[i+1])* *(y[i]+y[i+1]) S:=abs(s)/2 Конец Площадь многоугольника S

Рассмотрим выражение F=(x 1 -x 2 ) (y 1 +y 2 )+ (x 2 -x 3 ) (y 2 +y 3 )+ (x 3 -x 1 ) (y 3 +y 1 ) Оно представляет собой удвоенную площадь треугольника со знаком. Оказывается знак этого выражения несет очень важную информацию о треугольнике. Сформулируем новую теорему.

Ориентация треугольника Теорема. Треугольник, заданный на плоскости координатами своих вершин (x 1,y 1 ), (x 2,y 2 ) и (x 3,y 3 ) ориентирован против часовой стрелки, если (x 1 -x 2 ) (y 1 +y 2 )+ (x 2 -x 3 ) (y 2 +y 3 )+ (x 3 -x 1 ) (y 3 +y 1 )>0 по часовой стрелке, если (x 1 -x 2 ) (y 1 +y 2 )+ (x 2 -x 3 ) (y 2 +y 3 )+ (x 3 -x 1 ) (y 3 +y 1 )<0

Убедитесь в этом! x y O (x 1,y 1 ) (x 2,y 2 ) (x 3,y 3 ) F=(x 1 -x 2 ) (y 1 +y 2 )+ (x 2 -x 3 ) (y 2 +y 3 )+ (x 3 -x 1 ) (y 3 +y 1 ) (x 1,y 1 ) (x 2,y 2 ) (x 3,y 3 )

Задача о выпуклости многоугольника Задача о выпуклости многоугольника На плоскости заданы n точек своими координатами, являющиеся вершинами замкнутого многоугольника. Координаты точек заданы в порядке обхода вершин по границе многоугольника. Определить является ли многоугольник выпуклым. На входе программы задается число n (n<10) и массивы координат. На выходе ответ – да или нет. Данные вводятся с клавиатуры. Примеры Вход Выход n=7 {(0,0); (–2,3); (0,5); (4,5); (5,4); (5,2); (3,0)}да n=6 {(–3,1); (–1,2); (–2,3); (2,2); (3,0); (0,–1)}нет

Математическая модель Аргументы n – число сторон (вершин) многоугольника, целое, большее 2 x[1..n+2] – абсциссы вершин, вещественные y[1..n+2] – ординаты вершин, вещественные x[n+1]:=x[1], y[n+1]=y[1] x[n+2]:=x[2], y[n+2]=y[2] Результаты t - строковая константа для ответа, принимающая значения «да» или «нет» (или логическая переменная – true или false) Промежуточные величины i – счетчик цикла, целое z, z1 – значения функции F для трех подряд вершин многоугольника, вещественное

У выпуклого многоугольника все треугольники из соседних вершин 123, 234, 345, 456, 561, 612 одинаковой ориентации У невыпуклого многоугольника среди треугольников из соседних вершин 123, 234, 345, 456, 561, 612 есть треугольники разной ориентации

Число вершин? n Начало i=1,n Координаты i-ой вершины? x[i],y[i] x[n+1]:=x[1] y[n+1]:=y[1] x[n+2]:=x[2] y[n+2]:=y[2] 1 t:=`да` 1 z:=(x[1]-x[2])*(y[1]+y[2])+(x[2]-x[3])* *(y[2]+y[3])+(x[3]-x[1])*(y[3]+y[1]) i=2,n z1:=(x[i]-x[i+1])*(y[i]+y[i+1])+(x[i+1]-x[i+2])* *(y[i+1]+y[i+2])+(x[i+2]-x[i])*(y[i+2]+y[i]) Конец t z*z1<0 t:=`нет`

Задача о левых поворотах Задача о левых поворотах Новый градоначальник города Н.Глупова решил с целью пополнения бюджета и экономии горючего провести компанию борьбы с "левым уклоном". Для этого он запретил водителям выполнять левые повороты, установив за каждый такой поворот штраф в размере одного МРОТ. Кроме этого, он приказал установить компьютерную систему тотальной слежки за автомобилями, которая фиксирует координаты каждого автомобиля в начале и в конце его движения, а также в те моменты, когда автомобиль выполняет какой–либо поворот. От тяжелого прошлого городу Н.Глупову достались улицы в плохом состоянии, которые, кроме того, могут пересекаться под любыми углами. Развороты новый градоначальник не запретил. Задание: Написать программу, которая по заданной последовательности координат движения автомобиля вычисляет штраф.

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

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

Сравните ориентацию пар треугольников CAB и DAB и BCD и ACD в приведенных примерах. Сделайте вывод. A B C D 1 A B C D 2 A B C D 3 A B C D 4

Задача о расположении точки относительно выпуклого многоугольника Задача о расположении точки относительно выпуклого многоугольника Выпуклый многоугольник задан координатами своих вершин. Определить, является ли точка M с координатами (a,b) внутренней точкой многоугольника.

Посмотрите и сделайте вывод M M 2

Как распознать расположение точки и треугольника, подсчитав значение F для точек A,B,M B,C,M C,A,M? A B C M A B C M A B C M A C M и так далее.

Расстояние от точки до прямой. Теорема. Расстояние от точки M(x 1,y 1 ) до прямой ax+by+c=0 равно

Расстояние от точки до плоскости. Теорема. Расстояние от точки M(x 1,y 1,z 1 ) до плоскости ax+by+cz+d=0 равно

И это еще не все, но... КОНЕЦКОНЕЦ