Одна из важнейших операций заключается в определении положения точки относительно направленного отрезка прямой линии. Результат выполнения операции показывает, лежит ли точка слева или справа от направленного отрезка прямой линии или, если она совпадает с прямой линией, располагается она после конца направленного отрезка этой прямой линии, до начала, а если ни то, ни другое, то не совпадает ли она с началом или с концом или лежит между ними. Направленный отрезок прямой линии четко разделяет плоскость на семь непересекающихся областей и эта операция сообщает, какой из этих областей принадлежит точка (рис. 1).

Для определения положения текущей точки относительно отрезка прямой линии p0p1, направленного от точки р0 к точке p1, используется компонентная функция classify. Возвращается значение типа перечисления, указывающее на положение текущей точки:

Рис. 1: Разделение плоскости на семь областей направленным отрезком прямой линии

enum {LEFT, RIGHT, BEYOND, BEHIND, BETWEEN, ORIGIN, DESTINATION};
// СЛЕВА, СПРАВА, ВПЕРЕДИ, ПОЗАДИ, МЕЖДУ, НАЧАЛО, КОНЕЦ

int Point::classify(Point &p0, Point &pl)
{
Point p2 = *this;
Point a = p1 - pO;
Point b = p2 - pO;
double sa = a. x * b.y - b.x * a.y;
if (sa > 0.0)
return LEFT;
if (sa < 0.0)
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 (pO == p2)
return ORIGIN;
if (p1 == p2)
return DESTINATION;
return BETWEEN;
}

Вначале проверяется ориентация точек p0, p1 и р2, чтобы определить, располагается ли точка р2 слева или справа, или она коллинеарна с отрезком p0p1. В последнем случае необходимы дополнительные вычисления, ели векторы a=pl-pO и b=р2-p0 имеют противоположное направление, то точка р2 лежит позади направленного отрезка p0p1 если вектор а короче вектора b, то точка р2 расположена после отрезка p0p1. В противном случае точка р2 сравнивается с точками p0 и р1 для определения, совпадает ли с одной из этих концевых точек или лежит между ними.

Для удобства предусмотрена несколько иная версия компонентной функции classify, которой в качестве аргумента передается ребро вместо пары точек.
int Point::classify(Edge &e)
{
return classify(e.org, e.dest);
}

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