Урок 29. Нахождение уравнение прямой по двум точкам

Урок из серии «Геометрические алгоритмы»

Здравствуйте, дорогой читатель!

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

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

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

Сведения из вычислительной геометрии

Вычислительная геометрия – это раздел информатики, изучающий алгоритмы решения геометрических задач.

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

Результатом может быть либо ответ на какой то вопрос (типа принадлежит ли точка отрезку, пересекаются ли два отрезка, …), либо какой-то геометрический объект (например, наименьший выпуклый многоугольник, соединяющий заданные точки, площадь многоугольника, и т.п.).

Мы будем рассматривать задачи вычислительной геометрии только на плоскости и только в декартовой системе координат.

Векторы и координаты

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

Теперь геометрические объекты получают аналитическое выражение. Так, чтобы задать точку, достаточно указать её координаты: пару чисел (x; y). Отрезок можно задать, указав координаты его концов, прямую можно задать, указав координаты пары ее точек.

Но основным инструментом при решении задач у нас будут векторы. Напомню поэтому некоторые сведения о них.

Отрезок АВ, у которого точку А считают началом (точкой приложения), а точку В – концом, называют вектором АВ и обозначают либо , либо жирной строчной буквой, например а.

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

Произвольный вектор будет иметь координаты, равные разности соответствующих координат его конца и начала:

,

здесь точки A и B имеют координаты соответственно.

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

Ориентированный угол между векторами a и b положительный, если поворот от вектора a к вектору b совершается в положительном направлении (против часовой стрелки) и отрицательный – в другом случае. См рис.1а, рис.1б. Говорят также, что пара векторов a и b положительно (отрицательно) ориентирована.

Рис. 1а

Рис. 1б

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

Многие задачи вычислительной геометрии используют понятие векторного (косого или псевдоскалярного) произведений векторов.

Векторным произведением векторов 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)

где

a = (y2-y1),

b = (x1-x2),

c = x1(y1-y2) + y1(x2-x1)

Итак, прямую можно задать уравнением вида (1).

Задача 1. Заданы координаты двух точек. Найти её представление в виде ax + by + c = 0.

Решение

program Geom1; 

  var x1,y1,x2,y2:real; 

  a, b, c:real; 

procedure PointToLine(x1,y1,x2,y2:real; var a, b, c:real); 

  {Определение уравнения прямой по координатам двух точек} 

begin 

   a:= y2-y1; 

   b:= x1-x2; 

   c:= -x1*(y2-y1)+y1*(x2-x1); 

end; {PointToLine} 

Begin {main} 

   writeln('Введите координаты точек: x1,y1,x2,y2 '); 

  readln(x1,y1,x2,y2); 

  PointToLine( x1,y1,x2,y2,a,b,c); 

  writeln('Уравнение прямой: ',a:5:1,'x + ',b:5:1,'y+',c:5:1,'=0'); 

end.

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

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

До встречи в следующем уроке!