Проверка отрезка линии находится на расстоянии от точки

Question

У меня есть две точки A и B, которые определяют сегмент линии на экране устройства, плюс еще одна точка C. Используя эффективный и короткий алгоритм, который легко кодировать (предпочтительно с использованием стандартной математической библиотеки), как я могу проверить, является ли сегмент линииAB находится на расстоянии R от C?

Я знаю, что есть простой способ найти кратчайшее расстояние от точки до прямой, но предполагается, что линия бесконечно длинна.У меня есть отрезок с двумя конечными точками.

Я решил опубликовать это в Math SE, но решил не делать этого, так как не хочу получать все эти длинные математические формулы в качестве ответа, как в https://math.stackexchange.com/questions/2837/how-to-tell-if-a-line-segment-intersects-with-a-circle.Мне нужен эффективный и читаемый компьютерный алгоритм, а не формальная математическая теорема.

p / s: у меня есть следующий скелет метода Objective C, который необходимо реализовать:

typedef struct {
  CGPoint a;
  CGPoint b;
} CGLineSegment;

+ (BOOL)isLineSegment:(CGLineSegment)line withinRadius:(CGFloat)radius fromPoint:(CGPoint)point {

}

РЕДАКТИРОВАТЬ С РЕШЕНИЕМ:

благодаря ответу от veredesmarald (который я уже принял) я реализовал метод, который приведен здесь для справки других людей:

+ (BOOL)isLineSegment:(CGLineSegment)line withinRadius:(CGFloat)radius fromPoint:(CGPoint)point {
    CGPoint v = CGPointMake(line.b.x - line.a.x, line.b.y - line.a.y);
    CGPoint w = CGPointMake(point.x - line.a.x, point.y - line.a.y);
    CGFloat c1 = dotProduct(w, v);
    CGFloat c2 = dotProduct(v, v);
    CGFloat d;
    if (c1 <= 0) {
        d = distance(point, line.a);
    }
    else if (c2 <= c1) {
        d = distance(point, line.b);
    }
    else {
        CGFloat b = c1 / c2;
        CGPoint Pb = CGPointMake(line.a.x + b * v.x, line.a.y + b * v.y);
        d = distance(point, Pb);
    }
    return d <= radius;
}

CGFloat distance(const CGPoint p1, const CGPoint p2) {
    return sqrt(pow(p2.x - p1.x, 2) + pow(p2.y - p1.y, 2));
}

CGFloat dotProduct(const CGPoint p1, const CGPoint p2) {
    return p1.x * p2.x + p1.y * p2.y;
}

Answer 1

Когда мне пришлось реализовать метод определения расстояния от точки до интервала для графического назначения, я нашел эту страницу очень информативной: О линиях и расстоянии от точки до линии

В частности, вам может быть интересен отрезок Расстояние от точки до луча или сегмента .

Псевдокод из статьи (где · - скалярное произведение, а d() - расстояние между двумя точками):

distance( Point P, Segment P0:P1 )
{
      v = P1 - P0
      w = P - P0
      if ( (c1 = w·v) <= 0 )
            return d(P, P0)
      if ( (c2 = v·v) <= c1 )
            return d(P, P1)
      b = c1 / c2
      Pb = P0 + bv
      return d(P, Pb)
}

Этот метод основан на точечном произведении, чтобы определить, находится ли основание перпендикуляра в пределах интервала, а если нет, то какая конечная точка ближе.