:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Геометрия » Принадлежит или нет?.. » Точка отрезку
  Проверка принадлежности точки отрезку



Как определить, принадлежит ли точка A(x,y) отрезку с концевыми точками B(x1,y1) и C(x2,y2)?

Точки отрезка z можно описать уравнением

pOB+(1-p)OC=z, 0<=p<=1, OB и OC - векторы.

Если существует такое p, 0<=p<=1, что

pOB+(1-p)OC=A,

то A лежит на отрезке, иначе - нет.

Равенство расписывается по координатно так:

px1+(1-p)x2=x

py1+(1-p)y2=y

Из первого уравнения находим p, подставляем во второе: если получаем равенство и

0<=p<=1, то A на отрезке, иначе - нет.

Рабочая реализация более общей функции есть в разделе структуры геометрических данных.