Как найти расстояние от точки до отрезка (а не до прямой)?
С расстоянием от точки до бесконечной прямой разобрался через косое произведение. Но мне нужно расстояние до отрезка: если проекция точки выходит за концы отрезка, ответ должен быть расстоянием до ближайшего конца. Как это аккуратно учесть?
2 ответа
Ключ — параметр проекции t. Проецируем точку P на прямую отрезка AB, получаем параметр t = (AP·AB)/(AB·AB). Если t в [0,1] — ближайшая точка лежит на отрезке (расстояние до прямой), иначе — до ближайшего конца.
double distToSegment(const P& a, const P& b, const P& p) {
P ab = b - a, ap = p - a;
long long ab2 = ab.dot(ab);
if (ab2 == 0) return sqrt((double)ap.dot(ap)); // отрезок выродился в точку
double t = (double)ap.dot(ab) / ab2;
if (t < 0) return sqrt((double)ap.dot(ap)); // ближе конец A
if (t > 1) return sqrt((double)(p - b).dot(p - b)); // ближе конец B
// проекция внутри: расстояние до прямой через cross
double cr = (double)ab.cross(ap);
return fabs(cr) / sqrt((double)ab2);
}
Идея: знак и положение t определяют, с какой стороны от отрезка находимся, а внутри отрезка расстояние до прямой удобно считать как |cross(AB, AP)| / |AB| — модуль косого произведения это удвоенная площадь треугольника, делённая на основание |AB| даёт высоту. Сложность O(1).
Частые грабли. Первое: не забыть про вырожденный отрезок (A == B) — иначе деление на ноль. Ветка ab2 == 0 это ловит.
Второе: если нужно сравнить расстояния (какой отрезок ближе) или проверить dist <= R, лучше сравнивать квадраты расстояний в целых числах, не извлекая корень. Расстояние до прямой в квадрате это cross*cross / ab2 — чтобы избежать дроби, сравнивай cross*cross с R*R*ab2. Так всё остаётся целым и точным, без sqrt и epsilon.
Третье: sqrt бери только в самом конце, когда нужна именно числовая величина расстояния, а не сравнение.