Circle and Line Segment Intersection Detection (LatLon Point, Meter Radius and LatLon Line)

Question

Hi,

I have a circle which is actually a latlon position with a radius measured in meters. And I also have a road A-B defined as two lat-lon positions. How do I find whether that road cross inside the circle or not. Is it possible without projection latlon positions into xy positions? If possible please tell me how to do it. I'm actually trying to implement a snap-to-road functionality in a navigation software. So this is not a homework and straight forward usable procedure is very much appreciated as I'm very bad in maths.

Thanks.

Answer 1

I do not know the lat-long representation.
But - in general this question does not require a high math.
First build the equation of the Line between A to B (call the line L1).
Then find the equation of the perpendicular line to L1 that pass through the center of the circle (call it L2).
Then find the intersection of the two equations and check if the intersection point is inside the circle and if it is in [A-B].

Answer 2

Itay's, solution is elegant and does not require much mat.

You could however go for a more naive(CPU heavy) implementation:

make your line into a array of points and then measure the distance from each point to the center of your circle:

Method to transform two points into a array of coordinates(I have only tested this method briefly)

 public static Point[] generatePath(int startX, int startY, int endX, int endY) {
      _deltaX = Math.Abs(endX - startX);
      _deltaY = Math.Abs(endY - startY);
      if ( _deltaX >=_deltaY ) {
        //x is independent variable
        _numpixels = _deltaX + 1;
        _d = (2 * _deltaY) - _deltaY;
        _dinc1 = _deltaY << 1;
        _dinc2 = (_deltaY - _deltaX) << 1;
        _xinc1 = 1;
        _xinc2 = 1;
        _yinc1 = 0;
        _yinc2 = 1;
      } else {
        //y is independent variable
        _numpixels = _deltaY + 1;
        _d = (2 * _deltaX) - _deltaY;
        _dinc1 = _deltaX << 1;
        _dinc2 = (_deltaX - _deltaY) << 1;
        _xinc1 = 0;
        _xinc2 = 1;
        _yinc1 = 1;
        _yinc2 = 1;
      }
      // Make sure x and y move in the right directions 
      if ( startX > endX ) {
        _xinc1 = -_xinc1;
        _xinc2 = -_xinc2;
      }
      if ( startY > endY ) {
        _yinc1 = -_yinc1;
        _yinc2 = -_yinc2;
      }
      _x = startX;
      _y = startY;
      Point[] returnPath = new Point[_numpixels];
      for ( int i = 0;i < _numpixels;i++ ) {
        returnPath[i].X =_x;
        returnPath[i].Y =_y;
        if ( _d < 0 ) {
          _d = _d + _dinc1;
          _x = _x + _xinc1;
          _y = _y + _yinc1;
        } else {
          _d = _d + _dinc2;
          _x = _x + _xinc2;
          _y = _y + _yinc2;
        }
      }
      return returnPath;
    }

Method to calculate distance from center of your circle to every point in your line:

 public static double GetLenghtBetweenPoints(Point Source, Point Distination) {
      return Math.Sqrt((Math.Pow((Source.X-Distination.X), 2) + Math.Pow((Source.Y-Distination.Y), 2)));
    }