return RIGHT;
. if ( a.x * b.x < 0.0 || a.y * b.y < 0.0 ) return BEHIND;
if ( a.length () < b.length ()) return BEYOND;
if ( p == *this ) return ORIGIN;
if ( q == *this )
return DESTINATION;
return BETWEEN;
}
BEYOND
RIGHT
LEFT
BEHINDРис. 8.3
Компьютерная графика. Полигональные модели
8.3. Расстояние от точки до прямой Пусть заданы точка С(сх, су) и прямая АВ, где А(ак, ау), В(ЬХ, Ьу) и требуется н ти расстояние от этой точки до прямой. Найдем длину отрезка АВ:
1 = ^{ах-Ьх)2 +(ау-Ъу}
Опустим из точки С перпендикуляр на АВ. Точку Р пересечения этого перпен куляра с прямой можно представить параметрически Р = А + г(В-А), где
(ау-су]ау-Ьу)-(ах-сх\Ъх-ах)
Положение точки С на этом перпендикуляре будет задаваться параметром 5, ^ < 0 означает, что С находится слева от АВ, 5 > 0, что С - справа от АВ и 5 = О начает, что С лежит на АВ.
Для вычисления 5 воспользуемся следующей формулой:
(ау-су1ьх-ах)-{ах-сх\Ьу-ау)
5 _
і2и тогда искомое расстояние РС = я1. ,
8.4. Нахождение пересечения двух отрезков Пусть А, В, С и £> - точки на плоскости. Тогда направленные отрезки АВ и задаются следующими параметрическими уравнениями: Р = А + г{В-Л\РеЛВ, е = с + ^-с),ееСА
Если отрезки АВ и Си пересекаются, то Л + г(Д-Л)=С + *(0-С).
Перепишем это векторное соотношение в координатном виде: ах + г{Ьх ~ах) = сх+ ^ -сх), а у + г(ру - а у )= су + Б^у - су )
Эта система линейных алгебраических уравнений при
{Ьх ~ах)^у ~су)* ^у ~ауКх- ~сх) имеет единственное решение:
8. Основные алгоритмы вычислительной геометрии
_ [ау -суIfx ~сх)~(ах ~сх\dy -су) (bx - ах ){^у - су J- (by - ау \dx - сх)
= (ау ~су)/>х ~)-iflx -сх jpy -ау)
(bx - ах if у - Су y{by~ay\dx~ сх)
Если оба получившихся значения /- и s принадлежат отрезку [0,1], то отрезки АВ и CD пересекаются и точка пересечения может быть найдена из параметрических уравнений. В случае, когда оба или одно из полученных значений не принадлежат отрезку [0,1], отрезки АВ и CD не пересекаются, но пересекаются соответствующие прямые.
Равенство фх - ax)(dv - cv) = (bY - av)(dx - cx) означает, что отрезки АВ и CD параллельны.