Точка на прямой, луче и отрезке

Дана точка $P$ и объект, заданный двумя точками $A$ и $B$: прямая, луч из $A$ через $B$ или отрезок $AB$. Лежит ли $P$ на нём?

Три задачи решаются одна через другую, и все три — точно, без вещественных чисел.

Прямая

Точка лежит на прямой $AB$ тогда и только тогда, когда векторы $\vec{AB}$ и $\vec{AP}$ коллинеарны:

$$[\vec{AB}, \vec{AP}] = 0$$

bool onLine(Point a, Point b, Point p) {
    return Point(a, b) % Point(a, p) == 0;
}

Одно векторное произведение и сравнение с нулём. Если координаты целые — точно; если вещественные — через eq.

Луч

Луч выходит из $A$ и проходит через $B$. Точка на нём, если она на прямой и направление от $A$ к ней совпадает с направлением от $A$ к $B$.

Совпадение направлений — это неотрицательное скалярное произведение:

bool onRay(Point a, Point b, Point p) {
    return onLine(a, b, p) && Point(a, b) * Point(a, p) >= 0;
}

Знак «больше либо равно» включает случай $P = A$: там скалярное произведение равно нулю, и начало луча считается принадлежащим. Со строгим неравенством начало выпало бы — а это как раз тот вырожденный тест, который встретится на закрытой проверке.

Отрезок

Точка на отрезке $AB$, если она на прямой и лежит между $A$ и $B$.

Условие «между» удобно записать так: векторы $\vec{PA}$ и $\vec{PB}$ смотрят в противоположные стороны, то есть угол между ними развёрнутый:

$$(\vec{PA}, \vec{PB}) \le 0$$

bool onSegment(Point a, Point b, Point p) {
    return onLine(a, b, p) && Point(p, a) * Point(p, b) <= 0;
}

Нестрогое неравенство снова включает концы: если $P$ совпадает с $A$, то $\vec{PA}$ нулевой и произведение равно нулю.

Проверено: для точки $A + t \cdot \vec{AB}$ при $t$ от $-1$ до $3$ все три проверки совпали с условиями на параметр — «на прямой» всегда, «на луче» при $t \ge 0$, «на отрезке» при $0 \le t \le 1$. Двести тысяч случаев.

Сводка

объект	условие
прямая $AB$	$[\vec{AB}, \vec{AP}] = 0$
луч из $A$ через $B$	то же и $(\vec{AB}, \vec{AP}) \ge 0$
отрезок $AB$	то же и $(\vec{PA}, \vec{PB}) \le 0$

Видно, что все три отличаются одной строкой, и все три обходятся без деления. Это общий признак хорошо написанной геометрии: если в проверке появилось деление, скорее всего, есть способ без него.

Альтернатива через координаты

Иногда принадлежность отрезку проверяют по-другому: точка на прямой и её координаты лежат между координатами концов.

bool onSegment(Point a, Point b, Point p) {
    if (Point(a, b) % Point(a, p) != 0) return false;
    return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x)
        && min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}

Работает так же и иногда нагляднее. Но здесь обе проверки, по $x$ и по $y$, обязательны: для вертикального отрезка проверка по $x$ пропустит любую точку прямой, для горизонтального — проверка по $y$. Забыть одну из них — классическая ошибка.

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

Вырожденные случаи

Отдельно проверьте, что происходит при $A = B$. Тогда «отрезок» — это точка, направляющая нулевая, векторное произведение всегда ноль, и onLine вернёт истину для любой точки.

Формулы для отрезка при этом отработают правильно: $(\vec{PA}, \vec{PB}) = |\vec{PA}|^2 \ge 0$, значит условие $\le 0$ выполнится только при $P = A$. А вот onLine и onRay в вырожденном случае врут.

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