Урок из серии «Геометрические алгоритмы»
Здравствуйте, дорогой читатель!
Сегодня мы начнем изучать алгоритмы, связанные с геометрией. Дело в том, что олимпиадных задач по информатике, связанных с вычислительной геометрией, достаточно много и решение таких задач часто вызывают затруднения.
За несколько уроков мы рассмотрим ряд элементарных подзадач, на которые опирается решение большинства задач вычислительной геометрии.
На этом уроке мы составим программу для нахождения уравнения прямой , проходящей через заданные две точки . Для решения геометрических задач нам понадобятся некоторые знания из вычислительной геометрии. Часть урока мы посвятим знакомству с ними.
Сведения из вычислительной геометрии
Вычислительная геометрия – это раздел информатики, изучающий алгоритмы решения геометрических задач.
Исходными данными для таких задач могут быть множество точек на плоскости, набор отрезков, многоугольник (заданный например, списком своих вершин в порядке движения по часовой стрелке) и т.п.
Результатом может быть либо ответ на какой то вопрос (типа принадлежит ли точка отрезку, пересекаются ли два отрезка, …), либо какой-то геометрический объект (например, наименьший выпуклый многоугольник, соединяющий заданные точки, площадь многоугольника, и т.п.).
Мы будем рассматривать задачи вычислительной геометрии только на плоскости и только в декартовой системе координат.
Векторы и координаты
Чтобы применять методы вычислительной геометрии, необходимо геометрические образы перевести на язык чисел. Будем считать, что на плоскости задана декартова система координат, в которой направление поворота против часовой стрелки называется положительным.
Теперь геометрические объекты получают аналитическое выражение. Так, чтобы задать точку, достаточно указать её координаты: пару чисел (x; y). Отрезок можно задать, указав координаты его концов, прямую можно задать, указав координаты пары ее точек.
Но основным инструментом при решении задач у нас будут векторы. Напомню поэтому некоторые сведения о них.
Отрезок АВ , у которого точку А считают началом (точкой приложения), а точку В – концом, называют вектором АВ и обозначают либо , либо жирной строчной буквой, например а .
Для обозначения длины вектора (то есть длины соответствующего отрезка) будем пользоваться символом модуля (например, ).
Произвольный вектор будет иметь координаты, равные разности соответствующих координат его конца и начала:
,
здесь точки A
и B
имеют координаты 
соответственно.
Для вычислений мы будем использовать понятие ориентированного угла , то есть угла, учитывающего взаимное расположение векторов.
Ориентированный угол между векторами a и b положительный, если поворот от вектора a к вектору b совершается в положительном направлении (против часовой стрелки) и отрицательный – в другом случае. См рис.1а, рис.1б. Говорят также, что пара векторов a и b положительно (отрицательно) ориентирована.
Таким образом, величина ориентированного угла зависит от порядка перечисления векторов и может принимать значения в интервале .
Многие задачи вычислительной геометрии используют понятие векторного (косого или псевдоскалярного) произведений векторов.
Векторным произведением векторов a и b будем называть произведение длин этих векторов на синус угла между ними:
.
Векторное произведение векторов в координатах:
Выражение справа – определитель второго порядка:
В отличии от определения, которое дается в аналитической геометрии, это скаляр.
Знак векторного произведения определяет положение векторов друг относительно друга:
a и b положительно ориентирована.
Если величина , то пара векторов a и b отрицательно ориентирована.
Векторное произведение ненулевых векторов равно нулю тогда и только тогда, когда они коллинеарны (
). Это значит, что они лежат на одной прямой или на параллельных прямых.
Рассмотрим несколько простейших задач, необходимых при решении более сложных.
Определим уравнение прямой по координатам двух точек.
Уравнение прямой, проходящей через две различные точки, заданные своими координатами.
Пусть на прямой заданы две не совпадающие точки: с координатами (x1;y1) и с координатами (x2; y2). Соответственно вектор с началом в точке и концом в точке имеет координаты (x2-x1, y2-y1). Если P(x, y) – произвольная точка на нашей прямой, то координаты вектора равны (x-x1, y – y1).
С помощью векторного произведения условие коллинеарности векторов и можно записать так:
Т.е. (x-x1)(y2-y1)-(y-y1)(x2-x1)=0
(y2-y1)x + (x1-x2)y + x1(y1-y2) + y1(x2-x1) = 0
Последнее уравнение перепишем следующим образом:
ax + by + c = 0, (1)
c = x1(y1-y2) + y1(x2-x1)
Итак, прямую можно задать уравнением вида (1).
Задача 1. Заданы координаты двух точек. Найти её представление в виде ax + by + c = 0.
На этом уроке мы познакомились с некоторыми сведениями из вычислительной геометрии. Решили задачу по нахождению уравнения линии по координатам двух точек.
На следующем уроке составим программу для нахождения точки пересечения двух линий, заданных своими уравнениями.
Уравнение параболы является квадратичной функцией. Существует несколько вариантов составления этого уравнения. Все зависит от того, какие параметры представлены в условии задачи.
Инструкция
Парабола представляет собой кривую, которая по своей форме напоминает дугу и является графиком степенной функции. Независимо от того, характеристики имеет парабола, эта является четной. Четной называется такая функция, у при всех значениях аргумента из определения при изменении знака аргумента значение не изменяется:f(-x)=f(x)Начните с самой простую функции: y=x^2. Из ее вида можно сделать вывод, что она как при положительных, так и при отрицательных значениях аргумента x. Точка, в которой x=0, и при этом, y =0 считается точкой .
Ниже приведены все основные варианты построения этой функции и ее . В качестве первого примера ниже рассмотрена функция вида:f(x)=x^2+a, где a - целое числоДля того, чтобы построить график данной функции, необходимо сдвинуть график функции f(x) на a единиц. Примером может служить функция y=x^2+3, где вдоль оси y сдвигают функцию на две единицы. Если дана функция с противоположным знаком, например y=x^2-3, то ее график сдвигают вниз по оси y.
Еще один вид функции, которой может быть задана парабола - f(x)=(x +a)^2. В таких случаях график, наоборот, сдвигается вдоль оси абсцисс (оси x) на a единиц. Для примера можно рассмотреть функции: y=(x +4)^2 и y=(x-4)^2. В первом случае, где имеется функция со знаком плюс, график сдвигают по оси x влево, а во втором случае - вправо. Все эти случаи показаны на рисунке.
Пусть прямая проходит через точки М 1 (х 1 ; у 1) и М 2 (х 2 ; у 2). Уравнение прямой, проходящей через точку М 1 , имеет вид у- у 1 = k (х - х 1), (10.6)
где k - пока неизвестный коэффициент.
Так как прямая проходит через точку М 2 (х 2 у 2), то координаты этой точки должны удовлетворять уравнению (10.6): у 2 -у 1 = k (х 2 -х 1).
Отсюда
находим
Подставляя найденное значениеk
в уравнение (10.6), получим уравнение
прямой, проходящей через точки М 1
и М 2:
Предполагается, что в этом уравнении х 1 ≠ х 2 , у 1 ≠ у 2
Если х 1 = х 2 , то прямая, проходящая через точки М 1 (х 1 ,у I) и М 2 (х 2 ,у 2) параллельна оси ординат. Ее уравнение имеет вид х = х 1 .
Если у 2 = у I , то уравнение прямой может быть записано в виде у = у 1 , прямая М 1 М 2 параллельна оси абсцисс.
Уравнение прямой в отрезках
Пусть
прямая пересекает ось Ох в точке М 1 (а;0),
а ось Оу – в точке М 2 (0;b).
Уравнение примет вид:
т.е.
.
Это уравнение называетсяуравнением
прямой в отрезках, т.к. числа а и b
указывают, какие отрезки отсекает прямая
на осях координат
.
Уравнение прямой, проходящей через данную точку перпендикулярно данному вектору
Найдем уравнение прямой, проходящей через заданную точку Мо (х О; у о) перпендикулярно данному ненулевому вектор n = (А; В).
Возьмем на прямой произвольную точку М(х; у) и рассмотрим вектор М 0 М (х - х 0 ; у - у о) (см. рис.1). Поскольку векторы n и М о М перпендикулярны, то их скалярное произведение равно нулю: то есть
А(х - хо) + В(у - уо) = 0. (10.8)
Уравнение (10.8) называется уравнением прямой, проходящей через заданную точку перпендикулярно заданному вектору .
Вектор n= (А; В), перпендикулярный прямой, называется нормальным нормальным вектором этой прямой .
Уравнение (10.8) можно переписать в виде Ах + Ву + С =0 , (10.9)
где А и В координаты нормального вектора, С = -Ах о - Ву о - свободный член. Уравнение (10.9) есть общее уравнение прямой (см. рис.2).
Рис.1 Рис.2
Канонические уравнения прямой
,
Где
- координаты точки, через которую проходит
прямая, а
- направляющий вектор.
Кривые второго порядка Окружность
Окружностью называется множество всех точек плоскости, равноотстоящих от данной точки, которая называется центром.
Каноническое
уравнение круга радиуса
R с
центром в точке
:
В частности, если
центр кола совпадает с началом координат,
то уравнение будет иметь вид:
Эллипс
Эллипсом
называется множество точек плоскости,
сумма расстояний от каждой из которых
до двух заданных точек
и
,
которые называются фокусами, есть
величина постоянная
,
большая чем расстояние между фокусами
.
Каноническое уравнение эллипса,
фокусы которого лежат на оси Ох, а начало
координат посредине между фокусами
имеет вид
г
де
a длина большой полуоси;
b– длина
малой полуоси (рис. 2).
Прямая, проходящая через точку K(x 0 ; y 0) и параллельная прямой y = kx + a находится по формуле:
y - y 0 = k(x - x 0) (1)
Где k - угловой коэффициент прямой.
Альтернативная формула:
Прямая, проходящая через точку M 1 (x 1 ; y 1) и параллельная прямой Ax+By+C=0 , представляется уравнением
A(x-x 1)+B(y-y 1)=0 . (2)
Пример №1 . Составить уравнение прямой, проходящей через точку M 0 (-2,1) и при этом:а) параллельно прямой 2x+3y -7 = 0;
б) перпендикулярно прямой 2x+3y -7 = 0.
Решение . Представим уравнение с угловым коэффициентом в виде y = kx + a . Для этого перенесем все значения кроме y в правую часть: 3y = -2x + 7 . Затем разделим правую часть на коэффициент 3 . Получим: y = -2/3x + 7/3
Найдем уравнение NK, проходящее через точку K(-2;1), параллельно прямой y = -2 / 3 x + 7 / 3
Подставляя x 0 = -2, k = -2 / 3 , y 0 = 1 получим:
y-1 = -2 / 3 (x-(-2))
или
y = -2 / 3 x - 1 / 3 или 3y + 2x +1 = 0
Пример №2
. Написать уравнение прямой, параллельной прямой 2x + 5y = 0 и образующей вместе с осями координат треугольник, площадь которого равна 5.
Решение
. Так как прямые параллельны, то уравнение искомой прямой 2x + 5y + C = 0. Площадь прямоугольного треугольника , где a и b его катеты. Найдем точки пересечения искомой прямой с осями координат:
;
.
Итак, A(-C/2,0), B(0,-C/5). Подставим в формулу для площади: 
. Получаем два решения: 2x + 5y + 10 = 0 и 2x + 5y – 10 = 0 .
Пример №3
. Составить уравнение прямой, проходящей через точку (-2; 5) и параллельной прямой 5x-7y-4=0 .
Решение. Данную прямую можно представить уравнением y = 5 / 7 x – 4 / 7 (здесь a = 5 / 7). Уравнение искомой прямой есть y – 5 = 5 / 7 (x – (-2)), т.е. 7(y-5)=5(x+2) или 5x-7y+45=0 .
Пример №4 . Решив пример 3 (A=5, B=-7) по формуле (2), найдем 5(x+2)-7(y-5)=0.
Пример №5
. Составить уравнение прямой, проходящей через точку (-2;5) и параллельной прямой 7x+10=0.
Решение. Здесь A=7, B=0. Формула (2) дает 7(x+2)=0, т.е. x+2=0. Формула (1) неприменима, так как данное уравнение нельзя разрешить относительно y (данная прямая параллельна оси ординат).
Уравнение прямой, проходящей через данную точку в данном направлении. Уравнение прямой, проходящей через две данные точки. Угол между двумя прямыми. Условие параллельности и перпендикулярности двух прямых. Определение точки пересечения двух прямых
1. Уравнение прямой, проходящей через данную точку A (x 1 , y 1) в данном направлении, определяемом угловым коэффициентом k ,
y - y 1 = k (x - x 1). (1)
Это уравнение определяет пучок прямых, проходящих через точку A (x 1 , y 1), которая называется центром пучка.
2. Уравнение прямой, проходящей через две точки: A (x 1 , y 1) и B (x 2 , y 2), записывается так:
Угловой коэффициент прямой, проходящей через две данные точки, определяется по формуле
3. Углом между прямыми A и B называется угол, на который надо повернуть первую прямую A вокруг точки пересечения этих прямых против движения часовой стрелки до совпадения ее со второй прямой B . Если две прямые заданы уравнениями с угловым коэффициентом
y = k 1 x + B 1 ,