Расстояние между кругом и сегментом [дубликат]

Странно, что я могу ответить, но не комментировать ... Мне понравился подход Multitaskpro смены всего, чтобы центр круга упал на происхождение. К сожалению, в его коде есть две проблемы. Сначала в части под квадратным корнем вам нужно удалить двойную мощность. Поэтому нет:

var underRadical = Math.pow((Math.pow(r,2)*(Math.pow(m,2)+1)),2)-Math.pow(b,2));

, но:

var underRadical = Math.pow(r,2)*(Math.pow(m,2)+1)) - Math.pow(b,2);

В конечных координатах он забывает смещать решение обратно , Поэтому нет:

var i1 = {x:t1,y:m*t1+b}

, но:

var i1 = {x:t1+c.x, y:m*t1+b+c.y};

Тогда вся функция будет:

function interceptOnCircle(p1, p2, c, r) {
    //p1 is the first line point
    //p2 is the second line point
    //c is the circle's center
    //r is the circle's radius

    var p3 = {x:p1.x - c.x, y:p1.y - c.y}; //shifted line points
    var p4 = {x:p2.x - c.x, y:p2.y - c.y};

    var m = (p4.y - p3.y) / (p4.x - p3.x); //slope of the line
    var b = p3.y - m * p3.x; //y-intercept of line

    var underRadical = Math.pow(r,2)*Math.pow(m,2) + Math.pow(r,2) - Math.pow(b,2); //the value under the square root sign 

    if (underRadical < 0) {
        //line completely missed
        return false;
    } else {
        var t1 = (-m*b + Math.sqrt(underRadical))/(Math.pow(m,2) + 1); //one of the intercept x's
        var t2 = (-m*b - Math.sqrt(underRadical))/(Math.pow(m,2) + 1); //other intercept's x
        var i1 = {x:t1+c.x, y:m*t1+b+c.y}; //intercept point 1
        var i2 = {x:t2+c.x, y:m*t2+b+c.y}; //intercept point 2
        return [i1, i2];
    }
}

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

vector distVector = centerPoint - projectedPoint;
if(distVector.length() < circle.radius)
{
    double distance = circle.radius - distVector.length();
    vector moveVector = distVector.normalize() * distance;
    circle.move(moveVector);
}

http://jsfiddle.net/ercang/ornh3594/1/

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

vector distVector = centerPoint - startPoint;
if(distVector.length() < circle.radius)
{
    double distance = circle.radius - distVector.length();
    vector moveVector = distVector.normalize() * distance;
    circle.move(moveVector);
}

https://jsfiddle.net/ercang/menp0991/

Другой в c # (частичный класс Circle). Протестировано и работает как прелесть.

public class Circle : IEquatable<Circle>
{
    // ******************************************************************
    // The center of a circle
    private Point _center;
    // The radius of a circle
    private double _radius;

   // ******************************************************************
    /// <summary>
    /// Find all intersections (0, 1, 2) of the circle with a line defined by its 2 points.
    /// Using: http://math.stackexchange.com/questions/228841/how-do-i-calculate-the-intersections-of-a-straight-line-and-a-circle
    /// Note: p is the Center.X and q is Center.Y
    /// </summary>
    /// <param name="linePoint1"></param>
    /// <param name="linePoint2"></param>
    /// <returns></returns>
    public List<Point> GetIntersections(Point linePoint1, Point linePoint2)
    {
        List<Point> intersections = new List<Point>();

        double dx = linePoint2.X - linePoint1.X;

        if (dx.AboutEquals(0)) // Straight vertical line
        {
            if (linePoint1.X.AboutEquals(Center.X - Radius) || linePoint1.X.AboutEquals(Center.X + Radius))
            {
                Point pt = new Point(linePoint1.X, Center.Y);
                intersections.Add(pt);
            }
            else if (linePoint1.X > Center.X - Radius && linePoint1.X < Center.X + Radius)
            {
                double x = linePoint1.X - Center.X;

                Point pt = new Point(linePoint1.X, Center.Y + Math.Sqrt(Radius * Radius - (x * x)));
                intersections.Add(pt);

                pt = new Point(linePoint1.X, Center.Y - Math.Sqrt(Radius * Radius - (x * x)));
                intersections.Add(pt);
            }

            return intersections;
        }

        // Line function (y = mx + b)
        double dy = linePoint2.Y - linePoint1.Y;
        double m = dy / dx;
        double b = linePoint1.Y - m * linePoint1.X;

        double A = m * m + 1;
        double B = 2 * (m * b - m * _center.Y - Center.X);
        double C = Center.X * Center.X + Center.Y * Center.Y - Radius * Radius - 2 * b * Center.Y + b * b;

        double discriminant = B * B - 4 * A * C;

        if (discriminant < 0)
        {
            return intersections; // there is no intersections
        }

        if (discriminant.AboutEquals(0)) // Tangeante (touch on 1 point only)
        {
            double x = -B / (2 * A);
            double y = m * x + b;

            intersections.Add(new Point(x, y));
        }
        else // Secant (touch on 2 points)
        {
            double x = (-B + Math.Sqrt(discriminant)) / (2 * A);
            double y = m * x + b;
            intersections.Add(new Point(x, y));

            x = (-B - Math.Sqrt(discriminant)) / (2 * A);
            y = m * x + b;
            intersections.Add(new Point(x, y));
        }

        return intersections;
    }

    // ******************************************************************
    // Get the center
    [XmlElement("Center")]
    public Point Center
    {
        get { return _center; }
        set
        {
            _center = value;
        }
    }

    // ******************************************************************
    // Get the radius
    [XmlElement]
    public double Radius
    {
        get { return _radius; }
        set { _radius = value; }
    }

    //// ******************************************************************
    //[XmlArrayItemAttribute("DoublePoint")]
    //public List<Point> Coordinates
    //{
    //    get { return _coordinates; }
    //}

    // ******************************************************************
    // Construct a circle without any specification
    public Circle()
    {
        _center.X = 0;
        _center.Y = 0;
        _radius = 0;
    }

    // ******************************************************************
    // Construct a circle without any specification
    public Circle(double radius)
    {
        _center.X = 0;
        _center.Y = 0;
        _radius = radius;
    }

    // ******************************************************************
    // Construct a circle with the specified circle
    public Circle(Circle circle)
    {
        _center = circle._center;
        _radius = circle._radius;
    }

    // ******************************************************************
    // Construct a circle with the specified center and radius
    public Circle(Point center, double radius)
    {
        _center = center;
        _radius = radius;
    }

    // ******************************************************************
    // Construct a circle based on one point
    public Circle(Point center)
    {
        _center = center;
        _radius = 0;
    }

    // ******************************************************************
    // Construct a circle based on two points
    public Circle(Point p1, Point p2)
    {
        Circle2Points(p1, p2);
    }

Требуется:

using System;

namespace Mathematic
{
    public static class DoubleExtension
    {
        // ******************************************************************
        // Base on Hans Passant Answer on:
        // http://stackoverflow.com/questions/2411392/double-epsilon-for-equality-greater-than-less-than-less-than-or-equal-to-gre

        /// <summary>
        /// Compare two double taking in account the double precision potential error.
        /// Take care: truncation errors accumulate on calculation. More you do, more you should increase the epsilon.
        public static bool AboutEquals(this double value1, double value2)
        {
            if (double.IsPositiveInfinity(value1))
                return double.IsPositiveInfinity(value2);

            if (double.IsNegativeInfinity(value1))
                return double.IsNegativeInfinity(value2);

            if (double.IsNaN(value1))
                return double.IsNaN(value2);

            double epsilon = Math.Max(Math.Abs(value1), Math.Abs(value2)) * 1E-15;
            return Math.Abs(value1 - value2) <= epsilon;
        }

        // ******************************************************************
        // Base on Hans Passant Answer on:
        // http://stackoverflow.com/questions/2411392/double-epsilon-for-equality-greater-than-less-than-less-than-or-equal-to-gre

        /// <summary>
        /// Compare two double taking in account the double precision potential error.
        /// Take care: truncation errors accumulate on calculation. More you do, more you should increase the epsilon.
        /// You get really better performance when you can determine the contextual epsilon first.
        /// </summary>
        /// <param name="value1"></param>
        /// <param name="value2"></param>
        /// <param name="precalculatedContextualEpsilon"></param>
        /// <returns></returns>
        public static bool AboutEquals(this double value1, double value2, double precalculatedContextualEpsilon)
        {
            if (double.IsPositiveInfinity(value1))
                return double.IsPositiveInfinity(value2);

            if (double.IsNegativeInfinity(value1))
                return double.IsNegativeInfinity(value2);

            if (double.IsNaN(value1))
                return double.IsNaN(value2);

            return Math.Abs(value1 - value2) <= precalculatedContextualEpsilon;
        }

        // ******************************************************************
        public static double GetContextualEpsilon(this double biggestPossibleContextualValue)
        {
            return biggestPossibleContextualValue * 1E-15;
        }

        // ******************************************************************
        /// <summary>
        /// Mathlab equivalent
        /// </summary>
        /// <param name="dividend"></param>
        /// <param name="divisor"></param>
        /// <returns></returns>
        public static double Mod(this double dividend, double divisor)
        {
            return dividend - System.Math.Floor(dividend / divisor) * divisor;
        }

        // ******************************************************************
    }
}

В этом столбе столбец столбец будет проверяться путем проверки расстояния между центром окружности и точкой на линии (Ipoint), которые представляют точку пересечения между нормальным N (изображение 2) от центра круга до отрезка.

( https://i.stack.imgur.com/3o6do.png ) [/g4]

На изображении 1 один круг и показана одна строка, вектор A указывает на точку начала линии, вектор B указывает на конечную точку линии, вектор C указывает на центр круга. Теперь мы должны найти вектор E (от начальной точки линии до центра круга) и вектор D (от начальной точки линии до конечной точки линии), этот расчет показан на изображении 1.

( https: / /i.stack.imgur.com/7098a.png)[/g5]

На изображении 2 мы видим, что вектор E проецируется на вектор D «точечным произведением», вектора E и единичного вектора D, результат точечного произведения является скалярным Xp, представляющим расстояние между начальной точкой линии и точкой пересечения (Ipoint) вектора N и вектора D. Следующий вектор X определяется путем умножения единичного вектора D и скалярного Xp .

Теперь нам нужно найти вектор Z (вектор в Ipoint), его простое его простое векторное сложение вектора A (начальная точка на линии) и вектор X. Далее нам нужно иметь дело со специальными случаями, мы должны проверьте, является ли Ipoint на сегменте линии, если его не нужно выяснить, осталось ли это от него или справа от него, мы будем использовать ближайший вектор, чтобы определить, какая точка ближе к кругу.

( https://i.stack.imgur.com/p9WIr.png ) [/g6]

Когда проекция Xp отрицательна Ipoint оставлен от сегмента линии, ближайший вектор равен вектору начальной точки линии, когда проекция Xp больше, чем величина вектора D, тогда Ipoint справа от сегмента линии, тогда ближайший вектор равен вектору конечной точки линии в любом другом случае ближайший вектор равен вектору Z.

Теперь, когда у нас есть ближайший вектор, нам нужно найти вектор от центра окружности до Ipoint (dist vector), его простое просто нужно просто вычесть ближайший вектор из центра вектора. Затем просто проверьте, меньше ли величина векторного расстояния, чем радиус круга, если он тогда сталкивается, если его нет, нет столкновения.

( https://i.stack.imgur.com/ QJ63q.png ) [/g7]

Для завершения мы можем вернуть некоторые значения для разрешения столкновений, самый простой способ - вернуть перекрытие столкновения (вычесть радиус из векторной величины) и ось возврата столкновений, его вектор D. Также точка пересечения - это вектор Z, если это необходимо.

Если координаты линии являются Ax, Ay и Bx, By и центр кругов Cx, Cy, то формулы прямых:

x = Ax * t + Bx * (1 - t)

y = Ay * t + By * (1 - t)

, где 0 & lt; = t & lt; = 1

и окружность

(Cx - x) ^ 2 + (Cy - y) ^ 2 = R ^ 2

, если вы подставляете формулы x и y линии в формулу кругов, вы получаете уравнение второго порядка t и его решения являются точками пересечения (если они есть). Если вы получаете t, который меньше 0 или больше 1, то это не решение, но оно показывает, что линия «указывает» на направление круга.

Вы можете найти точку на бесконечной линии, ближайшей к центру окружности, проецируя вектор AC на вектор AB. Вычислите расстояние между этой точкой и центром круга. Если оно больше, то R не пересекается. Если расстояние равно R, то линия является касательной к окружности, а точка, ближайшая к центру окружности, фактически является точкой пересечения. Если расстояние меньше R, то есть 2 точки пересечения. Они лежат на том же расстоянии от точки, ближайшей к центру круга. Это расстояние можно легко вычислить, используя теорему Пифагора. Вот алгоритм в псевдокоде:

{
dX = bX - aX;
dY = bY - aY;
if ((dX == 0) && (dY == 0))
  {
  // A and B are the same points, no way to calculate intersection
  return;
  }

dl = (dX * dX + dY * dY);
t = ((cX - aX) * dX + (cY - aY) * dY) / dl;

// point on a line nearest to circle center
nearestX = aX + t * dX;
nearestY = aY + t * dY;

dist = point_dist(nearestX, nearestY, cX, cY);

if (dist == R)
  {
  // line segment touches circle; one intersection point
  iX = nearestX;
  iY = nearestY;

  if (t < 0 || t > 1)
    {
    // intersection point is not actually within line segment
    }
  }
else if (dist < R)
  {
  // two possible intersection points

  dt = sqrt(R * R - dist * dist) / sqrt(dl);

  // intersection point nearest to A
  t1 = t - dt;
  i1X = aX + t1 * dX;
  i1Y = aY + t1 * dY;
  if (t1 < 0 || t1 > 1)
    {
    // intersection point is not actually within line segment
    }

  // intersection point farthest from A
  t2 = t + dt;
  i2X = aX + t2 * dX;
  i2Y = aY + t2 * dY;
  if (t2 < 0 || t2 > 1)
    {
    // intersection point is not actually within line segment
    }
  }
else
  {
  // no intersection
  }
}

EDIT: добавлен код, чтобы проверить, действительно ли найденные точки пересечения находятся в пределах сегмента линии.

Вам понадобится следующая математика:

Предположим, что A = (Xa, Ya), B = (Xb, Yb) и C = (Xc, Yc). Любая точка на линии от А до В имеет координаты (альфа * Ха + (1-альфа) Xb, альфа Ya + (1-альфа) * ​​Yb) = P

Если точка P имеет расстояние R до C, она должна быть на окружности. Вы хотите решить

distance(P, C) = R

, что

(alpha*Xa + (1-alpha)*Xb)^2 + (alpha*Ya + (1-alpha)*Yb)^2 = R^2
alpha^2*Xa^2 + alpha^2*Xb^2 - 2*alpha*Xb^2 + Xb^2 + alpha^2*Ya^2 + alpha^2*Yb^2 - 2*alpha*Yb^2 + Yb^2=R^2
(Xa^2 + Xb^2 + Ya^2 + Yb^2)*alpha^2 - 2*(Xb^2 + Yb^2)*alpha + (Xb^2 + Yb^2 - R^2) = 0

, если вы примените формулу ABC к этому уравнению для ее решения для альфы и вычислите координаты P используя решение (ы) для альфы, вы получаете точки пересечения, если они существуют.

Если вы находите расстояние между центром сферы (так как это 3D, я полагаю, вы имеете в виду сферу, а не круг) и линию, то проверьте, меньше ли это расстояние, чем радиус.

Точка столкновения, очевидно, является ближайшей точкой между линией и сферой (которая будет вычисляться при вычислении расстояния между сферой и линией)

Расстояние между точкой и line: http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html

Вот хорошее решение в JavaScript (со всей необходимой математикой и живой иллюстрацией) https://bl.ocks.org/milkbread/11000965

Хотя функция is_on в этом решении необходимы модификации:

function is_on(a, b, c) {
    return Math.abs(distance(a,c) + distance(c,b) - distance(a,b))<0.000001;
}

Эта Java-функция возвращает объект DVec2. Требуется DVec2 для центра круга, радиуса круга и строки.

public static DVec2 CircLine(DVec2 C, double r, Line line)
{
    DVec2 A = line.p1;
    DVec2 B = line.p2;
    DVec2 P;
    DVec2 AC = new DVec2( C );
    AC.sub(A);
    DVec2 AB = new DVec2( B );
    AB.sub(A);
    double ab2 = AB.dot(AB);
    double acab = AC.dot(AB);
    double t = acab / ab2;

    if (t < 0.0) 
        t = 0.0;
    else if (t > 1.0) 
        t = 1.0;

    //P = A + t * AB;
    P = new DVec2( AB );
    P.mul( t );
    P.add( A );

    DVec2 H = new DVec2( P );
    H.sub( C );
    double h2 = H.dot(H);
    double r2 = r * r;

    if(h2 > r2) 
        return null;
    else
        return P;
}

Я бы использовал алгоритм для вычисления расстояния между точкой (центром окружности) и линией (строка AB). Это можно затем использовать для определения точек пересечения прямой с кружком.

Пусть, скажем, мы имеем точки A, B, C. Ax и Ay - х и y-компоненты точек A. То же самое для B и C. Скаляр R - радиус окружности.

Вот алгоритм

// compute the euclidean distance between A and B
LAB = sqrt( (Bx-Ax)²+(By-Ay)² )

// compute the direction vector D from A to B
Dx = (Bx-Ax)/LAB
Dy = (By-Ay)/LAB

// Now the line equation is x = Dx*t + Ax, y = Dy*t + Ay with 0 <= t <= 1.

// compute the value t of the closest point to the circle center (Cx, Cy)
t = Dx*(Cx-Ax) + Dy*(Cy-Ay)    

// This is the projection of C on the line from A to B.

// compute the coordinates of the point E on line and closest to C
Ex = t*Dx+Ax
Ey = t*Dy+Ay

// compute the euclidean distance from E to C
LEC = sqrt( (Ex-Cx)²+(Ey-Cy)² )

// test if the line intersects the circle
if( LEC < R )
{
    // compute distance from t to circle intersection point
    dt = sqrt( R² - LEC²)

    // compute first intersection point
    Fx = (t-dt)*Dx + Ax
    Fy = (t-dt)*Dy + Ay

    // compute second intersection point
    Gx = (t+dt)*Dx + Ax
    Gy = (t+dt)*Dy + Ay
}

// else test if the line is tangent to circle
else if( LEC == R )
    // tangent point to circle is E

else
    // line doesn't touch circle

Хорошо, я не буду давать вам код, но поскольку вы отметили этот алгоритм , я не думаю, что это будет иметь для вас значение. Во-первых, вы должны получить вектор, перпендикулярный линии.

У вас будет неизвестная переменная в y = ax + c (c будет неизвестно) Чтобы решить эту проблему, вычислите ее значение, когда линия проходит через центр круга.

То есть, подключите местоположение центра круга к линейному уравнению и решите для c. Затем вычислите точку пересечения исходной линии и ее нормали.

Это даст вам ближайшую точку на линии к кругу. Вычислите расстояние между этой точкой и центром окружности (используя величину вектора). Если это меньше радиуса круга - вуаля, мы имеем пересечение!

Просто добавление к этой теме ... Ниже приведена версия кода, опубликованного pahlevan, но для C # / XNA и немного подобрана:

    /// <summary>
    /// Intersects a line and a circle.
    /// </summary>
    /// <param name="location">the location of the circle</param>
    /// <param name="radius">the radius of the circle</param>
    /// <param name="lineFrom">the starting point of the line</param>
    /// <param name="lineTo">the ending point of the line</param>
    /// <returns>true if the line and circle intersect each other</returns>
    public static bool IntersectLineCircle(Vector2 location, float radius, Vector2 lineFrom, Vector2 lineTo)
    {
        float ab2, acab, h2;
        Vector2 ac = location - lineFrom;
        Vector2 ab = lineTo - lineFrom;
        Vector2.Dot(ref ab, ref ab, out ab2);
        Vector2.Dot(ref ac, ref ab, out acab);
        float t = acab / ab2;

        if (t < 0)
            t = 0;
        else if (t > 1)
            t = 1;

        Vector2 h = ((ab * t) + lineFrom) - location;
        Vector2.Dot(ref h, ref h, out h2);

        return (h2 <= (radius * radius));
    }

Вот решение, написанное в голанге. Метод похож на некоторые другие ответы, размещенные здесь, но не совсем то же самое. Он прост в применении и был протестирован. Вот шаги:

1. Перевести координаты так, чтобы круг находился в начале координат.
2. Выразить сегмент линии как параметризованные функции t для координат x и y. Если t равно 0, значения функции являются одной конечной точкой сегмента, а если t равно 1, то значения функции являются другой конечной точкой.
3. Решите, если возможно, квадратичное уравнение, возникающее из-за ограничений значений из t, которые производят координаты x, y с расстояниями от начала координат, равными радиусу окружности.
4. Выбрасывают решения, где t равно & lt; 0 или> 1 (& lt; = 0 или> = 1 для открытого сегмента). Эти точки не содержатся в сегменте.
5. Верните исходные координаты.

Здесь выводятся значения для A, B и C для квадратичных чисел, где (n-et) и (m-dt) являются уравнениями для координат x и y линии соответственно. r - радиус круга.

(n-et)(n-et) + (m-dt)(m-dt) = rr
nn - 2etn + etet + mm - 2mdt + dtdt = rr
(ee+dd)tt - 2(en + dm)t + nn + mm - rr = 0

Поэтому A = ee + dd, B = - 2 (en + dm) и C = nn + mm - rr.

Вот код golang для функции:

package geom

import (
    "math"
)

// SegmentCircleIntersection return points of intersection between a circle and
// a line segment. The Boolean intersects returns true if one or
// more solutions exist. If only one solution exists, 
// x1 == x2 and y1 == y2.
// s1x and s1y are coordinates for one end point of the segment, and
// s2x and s2y are coordinates for the other end of the segment.
// cx and cy are the coordinates of the center of the circle and
// r is the radius of the circle.
func SegmentCircleIntersection(s1x, s1y, s2x, s2y, cx, cy, r float64) (x1, y1, x2, y2 float64, intersects bool) {
    // (n-et) and (m-dt) are expressions for the x and y coordinates
    // of a parameterized line in coordinates whose origin is the
    // center of the circle.
    // When t = 0, (n-et) == s1x - cx and (m-dt) == s1y - cy
    // When t = 1, (n-et) == s2x - cx and (m-dt) == s2y - cy.
    n := s2x - cx
    m := s2y - cy

    e := s2x - s1x
    d := s2y - s1y

    // lineFunc checks if the  t parameter is in the segment and if so
    // calculates the line point in the unshifted coordinates (adds back
    // cx and cy.
    lineFunc := func(t float64) (x, y float64, inBounds bool) {
        inBounds = t >= 0 && t <= 1 // Check bounds on closed segment
        // To check bounds for an open segment use t > 0 && t < 1
        if inBounds { // Calc coords for point in segment
            x = n - e*t + cx
            y = m - d*t + cy
        }
        return
    }

    // Since we want the points on the line distance r from the origin,
    // (n-et)(n-et) + (m-dt)(m-dt) = rr.
    // Expanding and collecting terms yeilds the following quadratic equation:
    A, B, C := e*e+d*d, -2*(e*n+m*d), n*n+m*m-r*r

    D := B*B - 4*A*C // discriminant of quadratic
    if D < 0 {
        return // No solution
    }
    D = math.Sqrt(D)

    var p1In, p2In bool
    x1, y1, p1In = lineFunc((-B + D) / (2 * A)) // First root
    if D == 0.0 {
        intersects = p1In
        x2, y2 = x1, y1
        return // Only possible solution, quadratic has one root.
    }

    x2, y2, p2In = lineFunc((-B - D) / (2 * A)) // Second root

    intersects = p1In || p2In
    if p1In == false { // Only x2, y2 may be valid solutions
        x1, y1 = x2, y2
    } else if p2In == false { // Only x1, y1 are valid solutions
        x2, y2 = x1, y1
    }
    return
}

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

package geom_test

import (
    "testing"

    . "**put your package path here**"
)

func CheckEpsilon(t *testing.T, v, epsilon float64, message string) {
    if v > epsilon || v < -epsilon {
        t.Error(message, v, epsilon)
        t.FailNow()
    }
}

func TestSegmentCircleIntersection(t *testing.T) {
    epsilon := 1e-10      // Something smallish
    x1, y1 := 5.0, 2.0    // segment end point 1
    x2, y2 := 50.0, 30.0  // segment end point 2
    cx, cy := 100.0, 90.0 // center of circle
    r := 80.0

    segx, segy := x2-x1, y2-y1

    testCntr, solutionCntr := 0, 0

    for i := -100; i < 100; i++ {
        for j := -100; j < 100; j++ {
            testCntr++
            s1x, s2x := x1+float64(i), x2+float64(i)
            s1y, s2y := y1+float64(j), y2+float64(j)

            sc1x, sc1y := s1x-cx, s1y-cy
            seg1Inside := sc1x*sc1x+sc1y*sc1y < r*r
            sc2x, sc2y := s2x-cx, s2y-cy
            seg2Inside := sc2x*sc2x+sc2y*sc2y < r*r

            p1x, p1y, p2x, p2y, intersects := SegmentCircleIntersection(s1x, s1y, s2x, s2y, cx, cy, r)

            if intersects {
                solutionCntr++
                //Check if points are on circle
                c1x, c1y := p1x-cx, p1y-cy
                deltaLen1 := (c1x*c1x + c1y*c1y) - r*r
                CheckEpsilon(t, deltaLen1, epsilon, "p1 not on circle")

                c2x, c2y := p2x-cx, p2y-cy
                deltaLen2 := (c2x*c2x + c2y*c2y) - r*r
                CheckEpsilon(t, deltaLen2, epsilon, "p2 not on circle")

                // Check if points are on the line through the line segment
                // "cross product" of vector from a segment point to the point
                // and the vector for the segment should be near zero
                vp1x, vp1y := p1x-s1x, p1y-s1y
                crossProd1 := vp1x*segy - vp1y*segx
                CheckEpsilon(t, crossProd1, epsilon, "p1 not on line ")

                vp2x, vp2y := p2x-s1x, p2y-s1y
                crossProd2 := vp2x*segy - vp2y*segx
                CheckEpsilon(t, crossProd2, epsilon, "p2 not on line ")

                // Check if point is between points s1 and s2 on line
                // This means the sign of the dot prod of the segment vector
                // and point to segment end point vectors are opposite for
                // either end.
                wp1x, wp1y := p1x-s2x, p1y-s2y
                dp1v := vp1x*segx + vp1y*segy
                dp1w := wp1x*segx + wp1y*segy
                if (dp1v < 0 && dp1w < 0) || (dp1v > 0 && dp1w > 0) {
                    t.Error("point not contained in segment ", dp1v, dp1w)
                    t.FailNow()
                }

                wp2x, wp2y := p2x-s2x, p2y-s2y
                dp2v := vp2x*segx + vp2y*segy
                dp2w := wp2x*segx + wp2y*segy
                if (dp2v < 0 && dp2w < 0) || (dp2v > 0 && dp2w > 0) {
                    t.Error("point not contained in segment ", dp2v, dp2w)
                    t.FailNow()
                }

                if s1x == s2x && s2y == s1y { //Only one solution
                    // Test that one end of the segment is withing the radius of the circle
                    // and one is not
                    if seg1Inside && seg2Inside {
                        t.Error("Only one solution but both line segment ends inside")
                        t.FailNow()
                    }
                    if !seg1Inside && !seg2Inside {
                        t.Error("Only one solution but both line segment ends outside")
                        t.FailNow()
                    }

                }
            } else { // No intersection, check if both points outside or inside
                if (seg1Inside && !seg2Inside) || (!seg1Inside && seg2Inside) {
                    t.Error("No solution but only one point in radius of circle")
                    t.FailNow()
                }
            }
        }
    }
    t.Log("Tested ", testCntr, " examples and found ", solutionCntr, " solutions.")
}

Вот результат теста:

=== RUN   TestSegmentCircleIntersection
--- PASS: TestSegmentCircleIntersection (0.00s)
    geom_test.go:105: Tested  40000  examples and found  7343  solutions.

Наконец, этот способ легко расширяется до случай луча, начинающегося в одной точке, проходящего через другой и простирающегося до бесконечности, только путем проверки, если t> 0 или t & lt; 1, но не оба.

Мне просто нужно было, поэтому я придумал это решение. Язык является maxscript, но его следует легко перевести на любой другой язык. sideA, sideB и CircleRadius являются скалярами, остальные переменные являются точками как [x, y, z]. Я предполагаю, что z = 0 решить на плоскости XY

fn projectPoint p1 p2 p3 = --project  p1 perpendicular to the line p2-p3
(
    local v= normalize (p3-p2)
    local p= (p1-p2)
    p2+((dot v p)*v)
)
fn findIntersectionLineCircle CircleCenter CircleRadius LineP1 LineP2=
(
    pp=projectPoint CircleCenter LineP1 LineP2
    sideA=distance pp CircleCenter
    --use pythagoras to solve the third side
    sideB=sqrt(CircleRadius^2-sideA^2) -- this will return NaN if they don't intersect
    IntersectV=normalize (pp-CircleCenter)
    perpV=[IntersectV.y,-IntersectV.x,IntersectV.z]
    --project the point to both sides to find the solutions
    solution1=pp+(sideB*perpV)
    solution2=pp-(sideB*perpV)
    return #(solution1,solution2)
)

Вот реализация в Javascript. Мой подход состоит в том, чтобы сначала преобразовать сегмент линии в бесконечную линию, затем найти точку (точки) пересечения. Оттуда я проверяю, найдены ли найденные точки в сегменте линии. Код хорошо документирован, вы должны быть в состоянии следовать.

Вы можете попробовать код здесь в этой live demo . Код был взят из моих алгоритмов repo .

// Small epsilon value
var EPS = 0.0000001;

// point (x, y)
function Point(x, y) {
  this.x = x;
  this.y = y;
}

// Circle with center at (x,y) and radius r
function Circle(x, y, r) {
  this.x = x;
  this.y = y;
  this.r = r;
}

// A line segment (x1, y1), (x2, y2)
function LineSegment(x1, y1, x2, y2) {
  var d = Math.sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
  if (d < EPS) throw 'A point is not a line segment';
  this.x1 = x1; this.y1 = y1;
  this.x2 = x2; this.y2 = y2;
}

// An infinite line defined as: ax + by = c
function Line(a, b, c) {
  this.a = a; this.b = b; this.c = c;
  // Normalize line for good measure
  if (Math.abs(b) < EPS) {
    c /= a; a = 1; b = 0;
  } else { 
    a = (Math.abs(a) < EPS) ? 0 : a / b;
    c /= b; b = 1; 
  }
}

// Given a line in standard form: ax + by = c and a circle with 
// a center at (x,y) with radius r this method finds the intersection
// of the line and the circle (if any). 
function circleLineIntersection(circle, line) {

  var a = line.a, b = line.b, c = line.c;
  var x = circle.x, y = circle.y, r = circle.r;

  // Solve for the variable x with the formulas: ax + by = c (equation of line)
  // and (x-X)^2 + (y-Y)^2 = r^2 (equation of circle where X,Y are known) and expand to obtain quadratic:
  // (a^2 + b^2)x^2 + (2abY - 2ac + - 2b^2X)x + (b^2X^2 + b^2Y^2 - 2bcY + c^2 - b^2r^2) = 0
  // Then use quadratic formula X = (-b +- sqrt(a^2 - 4ac))/2a to find the 
  // roots of the equation (if they exist) and this will tell us the intersection points

  // In general a quadratic is written as: Ax^2 + Bx + C = 0
  // (a^2 + b^2)x^2 + (2abY - 2ac + - 2b^2X)x + (b^2X^2 + b^2Y^2 - 2bcY + c^2 - b^2r^2) = 0
  var A = a*a + b*b;
  var B = 2*a*b*y - 2*a*c - 2*b*b*x;
  var C = b*b*x*x + b*b*y*y - 2*b*c*y + c*c - b*b*r*r;

  // Use quadratic formula x = (-b +- sqrt(a^2 - 4ac))/2a to find the 
  // roots of the equation (if they exist).

  var D = B*B - 4*A*C;
  var x1,y1,x2,y2;

  // Handle vertical line case with b = 0
  if (Math.abs(b) < EPS) {

    // Line equation is ax + by = c, but b = 0, so x = c/a
    x1 = c/a;

    // No intersection
    if (Math.abs(x-x1) > r) return [];

    // Vertical line is tangent to circle
    if (Math.abs((x1-r)-x) < EPS || Math.abs((x1+r)-x) < EPS)
      return [new Point(x1, y)];

    var dx = Math.abs(x1 - x);
    var dy = Math.sqrt(r*r-dx*dx);

    // Vertical line cuts through circle
    return [
      new Point(x1,y+dy),
      new Point(x1,y-dy)
    ];

  // Line is tangent to circle
  } else if (Math.abs(D) < EPS) {

    x1 = -B/(2*A);
    y1 = (c - a*x1)/b;

    return [new Point(x1,y1)];

  // No intersection
  } else if (D < 0) {

    return [];

  } else {

    D = Math.sqrt(D);

    x1 = (-B+D)/(2*A);
    y1 = (c - a*x1)/b;

    x2 = (-B-D)/(2*A);
    y2 = (c - a*x2)/b;

    return [
      new Point(x1, y1),
      new Point(x2, y2)
    ];

  }

}

// Converts a line segment to a line in general form
function segmentToGeneralForm(x1,y1,x2,y2) {
  var a = y1 - y2;
  var b = x2 - x1;
  var c = x2*y1 - x1*y2;
  return new Line(a,b,c);
}

// Checks if a point 'pt' is inside the rect defined by (x1,y1), (x2,y2)
function pointInRectangle(pt,x1,y1,x2,y2) {
  var x = Math.min(x1,x2), X = Math.max(x1,x2);
  var y = Math.min(y1,y2), Y = Math.max(y1,y2);
  return x - EPS <= pt.x && pt.x <= X + EPS &&
         y - EPS <= pt.y && pt.y <= Y + EPS;
}

// Finds the intersection(s) of a line segment and a circle
function lineSegmentCircleIntersection(segment, circle) {

  var x1 = segment.x1, y1 = segment.y1, x2 = segment.x2, y2 = segment.y2;
  var line = segmentToGeneralForm(x1,y1,x2,y2);
  var pts = circleLineIntersection(circle, line);

  // No intersection
  if (pts.length === 0) return [];

  var pt1 = pts[0];
  var includePt1 = pointInRectangle(pt1,x1,y1,x2,y2);

  // Check for unique intersection
  if (pts.length === 1) {
    if (includePt1) return [pt1];
    return [];
  }

  var pt2 = pts[1];
  var includePt2 = pointInRectangle(pt2,x1,y1,x2,y2);

  // Check for remaining intersections
  if (includePt1 && includePt2) return [pt1, pt2];
  if (includePt1) return [pt1];
  if (includePt2) return [pt2];
  return [];

}

Круг действительно плохой парень. Так что хороший способ - избежать истинного круга, если сможете. Если вы делаете проверку на столкновение в играх, вы можете пойти с некоторыми упрощениями и иметь только 3 продукта-точки и несколько сравнений.

Я называю эту «жирную точку» или «тонкий круг». своего рода эллипс с нулевым радиусом в направлении, параллельном отрезку. но полный радиус в направлении, перпендикулярном сегменту

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

s0s1 = B-A;
s0qp = C-A;
rSqr = r*r;

Во-вторых, индекс h в hvec2f означает вектор должен поддерживать горизонтальные операции, такие как точка () / det (). Это означает, что его компоненты должны быть помещены в отдельные регистры xmm, чтобы избежать перетасовки / hadd'ing / hsub'ing. И здесь мы идем с самой совершенной версией самого простого обнаружения столкновения для 2D-игры:

bool fat_point_collides_segment(const hvec2f& s0qp, const hvec2f& s0s1, const float& rSqr) {
    auto a = dot(s0s1, s0s1);
    //if( a != 0 ) // if you haven't zero-length segments omit this, as it would save you 1 _mm_comineq_ss() instruction and 1 memory fetch
    {
        auto b = dot(s0s1, s0qp);
        auto t = b / a; // length of projection of s0qp onto s0s1
        //std::cout << "t = " << t << "\n";
        if ((t >= 0) && (t <= 1)) // 
        {
            auto c = dot(s0qp, s0qp);
            auto r2 = c - a * t * t;
            return (r2 <= rSqr); // true if collides
        }
    }   
    return false;
}

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