Как через cross проверить, лежит ли точка на отрезке (целочисленно)?
Нужна простая надёжная функция: дана точка P и отрезок AB, вернуть true, если P лежит ровно на отрезке (включая концы). Координаты целые. Хочу без double и без epsilon. Какая правильная проверка?
2 ответа
Два условия: точка должна лежать на прямой AB и одновременно в пределах отрезка.
- На прямой:
(B-A) × (P-A) == 0(коллинеарность, точно в целых). - В пределах: достаточно проверить, что
Pв bounding-box отрезка по обеим осям.
bool onSegment(const P& a, const P& b, const P& p) {
if ((b - a).cross(p - a) != 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);
}
Почему bounding-box достаточно: раз точка уже коллинеарна с A и B (лежит на той же прямой), то проверка попадания в прямоугольник, натянутый на концы, равносильна попаданию в отрезок. Лишних проверок не нужно. Всё в целых, O(1), без epsilon.
Альтернатива через скалярное произведение, если не хочешь сравнивать по обеим осям отдельно: точка на отрезке, если коллинеарна и (P-A)·(P-B) <= 0.
bool onSegment(const P& a, const P& b, const P& p) {
return (b - a).cross(p - a) == 0 && (a - p).dot(b - p) <= 0;
}
Логика второго условия: векторы от P к концам A и B смотрят в противоположные стороны (скалярное ≤ 0) ровно тогда, когда P между ними. На концах скалярное = 0, поэтому концы включены. Тоже целочисленно и компактно. Грабля одна и та же — переполнение cross/dot при больших координатах, лечится __int128.