Урок 31. Проверка принадлежности точки отрезку

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

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

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

Для реализации операций сравнения над вещественными данными напишем еще две функции: функцию EqPoint(), которая ,будет проверять, совпадают ли две точки на плоскости и функцию RealMoreEq() , которую будем использовать для проверки отношения «>=» (больше или равно).   Причина ввода специальных функций нам уже известна.

Задача. Проверить, принадлежит ли точка отрезку.

Решение.

Пусть точки Урок 31. Проверка принадлежности точки отрезку— начальная и конечные точки отрезка. clip_image004— произвольная точка на плоскости.

Вектор с началом в точке clip_image006 и концом в точке clip_image008будет иметь координаты (x2-x1, y2-y1).

Если P(x, y) – произвольная точка, то координаты вектора clip_image010равны: (x-x1, y – y1).

Точка Р будет принадлежать отрезку если:

  1. Векторы в clip_image010[1] и clip_image015 коллинеарны (равно нулю их векторное произведение):
    clip_image017, т.е. (x-x1)(y2-y1)-(y-y1)(x2-x1) = 0
  2. Абсцисса точки P удовлетворяет условию: clip_image019 или clip_image021. Иначе точка будет находиться на прямой левее или правее отрезка.
Program geom3;
Const _Eps: Real = 1e-3; {точность вычислений}
var x1,y1,x2,y2,x,y:real;
Function RealEq(Const a, b:Real):Boolean; {строго равно}
begin
  RealEq := Abs(a-b)<= _Eps
End; {RealEq}

Function RealMoreEq(Const a, b:Real):Boolean; {больше или равно}
begin
  RealMoreEq := a - b >= _Eps
End; {RealMoreEq}

Function EqPoint(x1,y1,x2,y2:real):Boolean;
{Совпадают ли две точки на плоскости}
begin
  EqPoint:=RealEq(x1,x2)and RealEq(y1,y2)
end; {EqPoint}
Function AtOtres(x1,y1,x2,y2,x,y:real):Boolean;
{Проверка принадлежности точки P отрезку P1P2}
Begin
  If EqPoint( x1,y1,x2,y2)
    Then  AtOtres:=  EqPoint( x1,y1,x,y)
    {точки P1 и P2 совпадают, результат определяется совпадением точек P1 и P}
Else
  AtOtres := RealEq((x-x1)*(y2-y1)- (y-y1)*(x2-x1),0)and (RealMoreEq(x,x1)and
    RealMoreEq( x2,x)Or RealMoreEq(x,x2)and RealMoreEq( x1,x))
end;  {AtOtres}

begin {main}
  writeln(Введите координаты точек: x1,y1,x2,y2,x,y');
  readln( x1,y1,x2,y2,x,y);
  if  AtOtres(x1,y1,x2,y2,x,y)
    then writeln('Да.')
    else writeln('Нет.);
end.  {main}

Результаты выполнения программы.

Введите координаты точек: x1, y1, x2, y2, x,y
0.5  1  2.5  2.8  1.203  1.633
Да.

Результаты тестирования в программе GeoGebra:

Точка принадлежит отрезку

Сегодня мы написали функцию AtOtres() , которая проверяет принадлежность произвольной точки отрезку, заданному своими координатами.

Ввели еще две функции: EqPoint() и RealMoreEq() для реализации операций сравнения над вещественными данными. Первая проверяет, совпадают ли две точки на плоскости, вторая —  используется  для проверки отношения «>=».

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

На этом я с вами прощаюсь. До встречи на следующем уроке.

5 Комментария “Урок 31. Проверка принадлежности точки отрезку

  1. Добрый день. Спасибо. очень помог Ваш урок, но есть один вопрос. Вы указали, что для колинеарности векторов нужно удовлетворить уравнение (x-x1)(y2-y1)-(y-y1)(x2-x1) = 0 которое являеться векторным произведением. Непонятен этот момент. Векторное произведение это вектор. А указанное Вами уравнение, как я понимаю, выведено из уравнения прямой проходящей через 2 точки на плоскости(x-x1)/(x2-x1)=(y-y1)/(y2-y1). Поправьте меня, пожалуйста, если ошибаюсь, но мне кажется, что здесь ошибка.

    Спасибо)

  2. — угол между векторами, P1P2 и P1P = 0, тоже самое для P2P1 и P2P. Или же, для быстроты, скалярное произведение этих векторов >= 0, т.к. реальные значения углов нам не нужны.

  3. Есть решение попроще:
    function AtOtres(x1,y1,x2,y2,x,y:real):Boolean;
    Var k1,k2,s1,s2,s3:Real;
    begin
    k1:=ABS(X1-X2);k2:=ABS(Y1-Y2);s1:=Sqrt(k1*k1+k2*k2);// находим длину отрезка
    k1:=ABS(X1-X);k2:=ABS(Y1-Y);s2:=Sqrt(k1*k1+k2*k2);// находим длину 1 гипотенузы
    k1:=ABS(X2-X);k2:=ABS(Y2-Y);s3:=Sqrt(k1*k1+k2*k2);// находим длину 2 гипотенузы
    s1:=Round(s1*100)/100;s2:=s2+s3;s2:=Round(s2*100)/100;// необходимая точность
    If s2=s1 Then Result:=True else Result:=False;
    end;

  4. Спасибо! Потрепал нервы немного порядок выполнения логических операций паскаля. Кстати еще есть один косяк

    Function RealMoreEq(Const a, b:Real):Boolean; {больше или равно}
    begin
    RealMoreEq := a — b >= _Eps
    End; {RealMoreEq}

    нужно написать
    RealMoreEq := a — b >= 0
    иначе точка которая стоит прямо на начале или в конце отрезка не будет считаться принадлежащим этому отрезку

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *