Вопрос по algorithm, math – Алгоритм обнаружения столкновений отрезков круговой линии?

180

У меня есть линия от A до B и круг, расположенный в C с радиусом R.

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

На данный момент, нет, все алгоритмы, которые я здесь пробовал, заметно не замедляют работу приложения. Mizipzor
В этом случае это конечный отрезок. Является "линией" называется что-то еще в зависимости от того, является ли оно конечным или бесконечным? Mizipzor
Хм. Один вопрос: вы говорите о бесконечной прямой через А и В или о конечном отрезке от А до Б? Jason S
@Mizipzor да, они называются как-то иначе: линияsegments, Если вы просто скажете «строка» это подразумевает бесконечность. MestreLion
Есть ли требования к производительности? Это должен быть быстрый метод? chmike

Ваш Ответ

23   ответа
1

Еще один в 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;
        }

        // ******************************************************************
    }
}
186

принятие

  1. E is the starting point of the ray,
  2. L is the end point of the ray,
  3. C is the center of sphere you're testing against
  4. r is the radius of that sphere

Вычислите:
d = L - E (Вектор направления луча от начала до конца)
f = E - C (Вектор от центральной сферы к началу луча)

Тогда перекресток найден ..
Подключив:
P = E + t * d
Это параметрическое уравнение:
пx = Ex + тдx
пy = Ey + тдy
в
(x - h)2 + (y - k)2 = r2
(h, k) = центр круга.

Note: We've simplified the problem to 2D here, the solution we get applies also in 3D

to get:

  1. Expand
    x2 - 2xh + h2 + y2 - 2yk + k2 - r2 = 0
  2. Plug
    x = ex + tdx
    y = ey + tdy
    ( ex + tdx )2 - 2( ex + tdx )h + h2 + ( ey + tdy )2 - 2( ey + tdy )k + k2 - r2 = 0
  3. Explode
    ex2 + 2extdx + t2dx2 - 2exh - 2tdxh + h2 + ey2 + 2eytdy + t2dy2 - 2eyk - 2tdyk + k2 - r2 = 0
  4. Group
    t2( dx2 + dy2 ) + 2t( exdx + eydy - dxh - dyk ) + ex2 + ey2 - 2exh - 2eyk + h2 + k2 - r2 = 0
  5. Finally,
    t2( _d * _d ) + 2t( _e * _d - _d * _c ) + _e * _e - 2( _e*_c ) + _c * _c - r2 = 0
    *Where _d is the vector d and * is the dot product.*
  6. And then,
    t2( _d * _d ) + 2t( _d * ( _e - _c ) ) + ( _e - _c ) * ( _e - _c ) - r2 = 0
  7. Letting _f = _e - _c
    t2( _d * _d ) + 2t( _d * _f ) + _f * _f - r2 = 0

Итак, мы получаем:
t2 * (d DOT d) + 2t*( f DOT d ) + ( f DOT f - r2 ) = 0
Итак, решение квадратного уравнения:

float a = d.Dot( d ) ;
float b = 2*f.Dot( d ) ;
float c = f.Dot( f ) - r*r ;

float discriminant = b*b-4*a*c;
if( discriminant < 0 )
{
  // no intersection
}
else
{
  // ray didn't totally miss sphere,
  // so there is a solution to
  // the equation.

  discriminant = sqrt( discriminant );

  // either solution may be on or off the ray so need to test both
  // t1 is always the smaller value, because BOTH discriminant and
  // a are nonnegative.
  float t1 = (-b - discriminant)/(2*a);
  float t2 = (-b + discriminant)/(2*a);

  // 3x HIT cases:
  //          -o->             --|-->  |            |  --|->
  // Impale(t1 hit,t2 hit), Poke(t1 hit,t2>1), ExitWound(t1<0, t2 hit), 

  // 3x MISS cases:
  //       ->  o                     o ->              | -> |
  // FallShort (t1>1,t2>1), Past (t1<0,t2<0), CompletelyInside(t1<0, t2>1)

  if( t1 >= 0 && t1 <= 1 )
  {
    // t1 is the intersection, and it's closer than t2
    // (since t1 uses -b - discriminant)
    // Impale, Poke
    return true ;
  }

  // here t1 didn't intersect so we are either started
  // inside the sphere or completely past it
  if( t2 >= 0 && t2 <= 1 )
  {
    // ExitWound
    return true ;
  }

  // no intn: FallShort, Past, CompletelyInside
  return false ;
}
h и k - центр круга, против которого вы пересекаетесь. t является параметром уравнения линии. В коде t1 и t2 являются решениями. t1 и t2 сообщают вам, "как далеко вдоль луча" пересечение произошло.
Кажется, работает, если я делаю прямое копирование и вставку, но я пытаюсь понять это. В (x-h) ^ 2 + (y-k) ^ 2 = r ^ 2 что такое h и k? Является ли k постоянной величиной, на которой линия / луч увеличивается на y по x? А что такое т? Глядя на код, кажется, вы приняли его 1 (поэтому он просто "удален"). У этих формул есть имя или что-то? Может быть, я могу посмотреть их подробно на Вольфраме. Mizipzor
Не уверен, почему, но код, похоже, не работает для случая Impale. Это происходит, когда я добавляю, если t1 & lt; = 0 & amp; & amp; t1 & lt; -1 & amp; & amp; t2 & lt; = 0 & amp; t2 & gt; = -1 как истинное условие, но затем оно также дает ложный положительный результат на одной стороне конечной линии, когда окружность находится на "бесконечной" часть. Я пока не понимаю математику, но копируй / вставляй, будь осторожен.
P = E + t * d Что такоеt?
Хорошо понял. Точечное произведение просто вычисляется по трем элементам (x, y, z) векторов. Я переключу свой код на этот алгоритм.
0

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

  1. Translate coordinates so that the circle is at the origin.
  2. Express the line segment as parametrized functions of t for both the x and y coordinates. If t is 0, the function's values are one end point of the segment, and if t is 1, the function's values are the other end point.
  3. Solve, if possible, the quadratic equation resulting from constraining values of t that produce x, y coordinates with distances from the origin equal to the circle's radius.
  4. Throw out solutions where t is < 0 or > 1 ( <= 0 or >= 1 for an open segment). Those points are not contained in the segment.
  5. Translate back to original coordinates.

Значения для 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.

Вот код Голанга для функции:

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 & gt; 0 или t & lt; 1, но не оба.

7

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

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/

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

Другой метод использует формулу области ABC треугольника. Тест пересечения является более простым и более эффективным, чем метод проецирования, но поиск координат точки пересечения требует больше работы. По крайней мере, это будет отложено до того момента, когда это необходимо.

Формула для вычисления площади треугольника: area = bh / 2

где b - базовая длина, а h - высота. Мы выбрали сегмент AB в качестве основы, чтобы h было кратчайшим расстоянием от C, центра круга, до линии.

Поскольку площадь треугольника также может быть вычислена произведением векторной точки, мы можем определить h.

// compute the triangle area times 2 (area = area2/2)
area2 = abs( (Bx-Ax)*(Cy-Ay) - (Cx-Ax)(By-Ay) )

// compute the AB segment length
LAB = sqrt( (Bx-Ax)² + (By-Ay)² )

// compute the triangle height
h = area2/LAB

// if the line intersects the circle
if( h < R )
{
    ...
}        

UPDATE 1 :

Вы можете оптимизировать код, используя описанные быстрые вычисления обратного квадратного корняВот чтобы получить хорошее приближение 1 / LAB.

Вычислить точку пересечения не так сложно. Вот оно идет

// compute the line AB direction vector components
Dx = (Bx-Ax)/LAB
Dy = (By-Ay)/LAB

// compute the distance from A toward B of closest point to C
t = Dx*(Cx-Ax) + Dy*(Cy-Ay)

// t should be equal to sqrt( (Cx-Ax)² + (Cy-Ay)² - h² )

// compute the intersection point distance from t
dt = sqrt( R² - h² )

// compute first intersection point coordinate
Ex = Ax + (t-dt)*Dx
Ey = Ay + (t-dt)*Dy

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

Если h = R, то прямая AB касается окружности, а значения dt = 0 и E = F. Координаты точек соответствуют координатам E и F.

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

t = Dx * (Cx-Ax) + Dy * (Cy-Ax) должно читаться как t = Dx * (Cx-Ax) + Dy * (Cy-Ay)
Мне нравится простота в этом методе. Возможно, я мог бы адаптировать некоторый окружающий код так, чтобы он не нуждался в реальной точке столкновения, я посмотрим, что произойдет, если я использую A или B, а не вычисленную точку между ними. Mizipzor
Это правильно. Спасибо за указание на это. Я исправил это в посте.
только что отредактированный - первая строка вычисляет площадь треугольника, используяcross продукт, а не точечный продукт. проверено кодом здесь:stackoverflow.com/questions/2533011/…
также обратите внимание, что в первой половине этого ответа проверяется пересечение с линией, а не с отрезком (как задано в вопросе).
3

Здесь вам понадобится немного математики:

Предположим, что A = (Xa, Ya), B = (Xb, Yb) и C = (Xc, Yc). Любая точка на линии от А до В имеет координаты (альфа * Ха + (1 альфа)Xb, alphaЯ + (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, используя решение (я) для альфы, вы получите точки пересечения, если таковые существуют.

0

Мне просто нужно было это, поэтому я придумал это решение. Язык 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)
)
3

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

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

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

Я не математик, так что я подумал, что мне лучше изложить общий подход и предоставить другим возможность выяснить конкретные математики (хотя я выгляжу довольно тривиально)
mathworld.wolfram.com/Point-LineDistance3-Dimensional.html а такжеmathworld.wolfram.com/Point-LineDistance2-Dimensional.html лучше & amp; с более авторитетного сайта
Это в 2D, а не в 3D; как вы говорите, это не имеет значения
Я объяснил немного лучше о ближайшей точке и связался с mathworld вместо pbourke :)
+1 с сильным голосом. (хотя я бы дал ссылку на другой сайт, сайт pbourke выглядит запутанным) Все остальные ответы пока слишком сложны. Хотя ваш комментарий "Эта точка также является точкой пересечения на линии" неверно, нет точки, которая была построена в процессе вычисления.
2

enter image description here

' VB.NET - Code

Function CheckLineSegmentCircleIntersection(x1 As Double, y1 As Double, x2 As Double, y2 As Double, xc As Double, yc As Double, r As Double) As Boolean
    Static xd As Double = 0.0F
    Static yd As Double = 0.0F
    Static t As Double = 0.0F
    Static d As Double = 0.0F
    Static dx_2_1 As Double = 0.0F
    Static dy_2_1 As Double = 0.0F

    dx_2_1 = x2 - x1
    dy_2_1 = y2 - y1

    t = ((yc - y1) * dy_2_1 + (xc - x1) * dx_2_1) / (dy_2_1 * dy_2_1 + dx_2_1 * dx_2_1)

    If 0 <= t And t <= 1 Then
        xd = x1 + t * dx_2_1
        yd = y1 + t * dy_2_1

        d = Math.Sqrt((xd - xc) * (xd - xc) + (yd - yc) * (yd - yc))
        Return d <= r
    Else
        d = Math.Sqrt((xc - x1) * (xc - x1) + (yc - y1) * (yc - y1))
        If d <= r Then
            Return True
        Else
            d = Math.Sqrt((xc - x2) * (xc - x2) + (yc - y2) * (yc - y2))
            If d <= r Then
                Return True
            Else
                Return False
            End If
        End If
    End If
End Function
работает отлично! Я попробовал это на Google координаты :)
45

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

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

Этот алгоритм требует, чтобы A, B и C были разными точками и чтобы R & # xA0; не было 0.

Вот алгоритм

// 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

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

// compute the distance between the points A and E, where
// E is the point of AB closest the circle center (Cx, Cy)
t = Dx*(Cx-Ax) + Dy*(Cy-Ay)    

// compute the coordinates of the point E
Ex = t*Dx+Ax
Ey = t*Dy+Ay

// compute the euclidean distance between E and 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
если любая линия, которая не пересекает окружность и обе ее точки p1 и p2, находятся внутри окружности. в таком случае как работает ваш алгоритм ??
Спасибо chmike за отличный ответ
@ Matt W Вы имеете в виду "Как определить, происходит ли пересечение за пределами конечных точек отрезка AB"? Просто подумайте о т как мера расстояния вдоль линии. Точка А находится вt=0, Точка B вt=LAB, Когда обе точки пересечения (t1=t-td а такжеt2=t+td) имеют отрицательные значения, чем пересечения находятся за пределами сечения (за точкой А, если смотреть со стороны сечения точки). Когда t1 и t2 больше, чем LAB, они тоже находятся снаружи (на этот раз за точкой B). Пересечение t1 (или t2) происходит между A и B, только когда t1 (или t2) находится между 0 и LAB.
Поскольку точка пересечения с окружностью находится на «расстоянии»t+dt а такжеt-dt на линии.t это точка на линии, ближайшей к центру круга. Точки пересечения с окружностью находятся на симметричном расстоянии отt, Точки пересечения находятся на «расстояниях»;t-dt а такжеt+dt, Я процитировал расстояние, потому что это не евклидово расстояние. Чтобы получить евклидово расстояние отA гдеt=0, вы должны умножить значение наLAB.
Вы должны проверить t-dt и t + dt. Если t-dt & lt; 0, чем p1 находится внутри круга. Если t + dt & gt; 1, чем p2 внутри круга. Это верно, если LEC & lt; R конечно.
2

Если координаты линии: A.x, A.y и B.x, B.y, а центр окружностей - C.x, C.y, то формулы линий будут следующими:

x = A.x * t + B.x * (1 - t)

y = A.y * t + B.y * (1 - t)

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

и круг

(C.x - x) ^ 2 + (C.y - y) ^ 2 = R ^ 2

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

3

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

(https://i.stack.imgur.com/3o6do.png)Image 1. Finding vectors E and D

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

(https://i.stack.imgur.com/7098a.png)Image 2. Finding vector X

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

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

(https://i.stack.imgur.com/p9WIr.png)Image 3. Finding closest point

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

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

(https://i.stack.imgur.com/QJ63q.png)Image 4. Checking for collision

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

Я прошу прощения, мое намерение не было коммерческого характера.
Добро пожаловать в переполнение стека! К сожалению, включив свои контактные данные в свое сообщение, вы отключили некоторые из спам-фильтров сообщества, а значит и отрицательные отзывы. Мы работаем над тем, чтобы отозвать их.
Да, не беспокойся. Вы можете оставить их в своем профиле, это назначенное для них место.
2

Просто дополнение к этой теме ... Ниже приведена версия кода, опубликованного 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));
    }
В C # / XNA вы можете использоватьRay.Intersects(BoundingSphere)
1

Вот хорошее решение в 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;
}

Спасибо и FWIW, я не проголосовал.
1

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

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

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

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

Во-вторых, индекс h в hvec2f означает, что вектор должен благоприятствовать горизонтальным операциям, таким как dot () / det (). Это означает, что его компоненты должны быть помещены в отдельные xmm-регистры, чтобы избежать случайного перемешивания / хаддинга / hsub. И вот мы с самой производительной версией простейшего обнаружения столкновений для 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;
}

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

122

Кажется, никто не рассматривает проекцию, я совершенно не в курсе?

Спроектировать векторAC наAB, Спроецированный вектор,AD, дает новую точкуD.
Если расстояние междуD а такжеC меньше чем (или равно)R у нас есть пересечение.

Как это:
Image by SchoolBoy

Есть много деталей, чтобы принять во внимание: D лежит между AB? Перпендикулярно ли расстояние C к линии больше радиуса? Все это включает в себя величину вектора, то есть квадратный корень.
@ Паук, это не имеет значения. В общем, так как это вариант проблемы пересечения сфер и линий, стратегия Мизипзора совершенно верна.CD это проекция, она перпендикулярна по определению.
Я писал свой ответ на основании того, что вы опубликовали этот ответ :) Вы правы, это хороший способ проверить, существует ли пересечение.
Хорошая идея, но как тогда вычислить две точки пересечения?
4

Странно я могу ответить, но не комментировать ... Мне понравился подход 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];
    }
}
Копия вставлена в js, работает. +1
Примечание: это хорошо работает для линий, но не работает для отрезков.
предложения: во-первых, пусть он обрабатывает случай, когда линейный отрезок является вертикальным (то есть имеет бесконечный наклон). Во-вторых, пусть он возвращает только те точки, которые фактически попадают в диапазон исходного сегмента линии, - я считаю, что он успешно возвращает все точки, которые попадают на бесконечную линию, даже если эти точки лежат вне сегмента линии.
5

Это решение, которое я нашел, казалось немного легче следовать, чем некоторые другие.

Принимая:

p1 and p2 as the points for the line, and
c as the center point for the circle and r for the radius

Я бы решил для уравнения линии в форме пересечения наклона. Тем не менее, я не хотел иметь дело с трудными уравнениями сc в качестве точки, поэтому я просто сместил систему координат так, чтобы круг0,0

p3 = p1 - c
p4 = p2 - c

Кстати, всякий раз, когда я вычитал очки друг от друга, я вычиталxи затем вычитаяyи помещая их в новую точку, на тот случай, если кто-то не знал.

Во всяком случае, теперь я решаю для уравнения линии сp3 а такжеp4:

m = (p4_y - p3_y) / (p4_x - p3) (the underscore is an attempt at subscript)
y = mx + b
y - mx = b (just put in a point for x and y, and insert the m we found)

Хорошо. Теперь мне нужно установить эти уравнения равными. Сначала мне нужно решить уравнение круга дляx

x^2 + y^2 = r^2
y^2 = r^2 - x^2
y = sqrt(r^2 - x^2)

Тогда я установил их равными:

mx + b = sqrt(r^2 - x^2)

И решить для квадратного уравнения (0 = ax^2 + bx + c):

(mx + b)^2 = r^2 - x^2
(mx)^2 + 2mbx + b^2 = r^2 - x^2
0 = m^2 * x^2 + x^2 + 2mbx + b^2 - r^2
0 = (m^2 + 1) * x^2 + 2mbx + b^2 - r^2

Теперь у меня есть мойa, b, а такжеc.

a = m^2 + 1
b = 2mb
c = b^2 - r^2

Я положил это в квадратную формулу:

(-b ± sqrt(b^2 - 4ac)) / 2a

И подставьте значения, затем максимально упростите:

(-2mb ± sqrt(b^2 - 4ac)) / 2a
(-2mb ± sqrt((-2mb)^2 - 4(m^2 + 1)(b^2 - r^2))) / 2(m^2 + 1)
(-2mb ± sqrt(4m^2 * b^2 - 4(m^2 * b^2 - m^2 * r^2 + b^2 - r^2))) / 2m^2 + 2
(-2mb ± sqrt(4 * (m^2 * b^2 - (m^2 * b^2 - m^2 * r^2 + b^2 - r^2))))/ 2m^2 + 2
(-2mb ± sqrt(4 * (m^2 * b^2 - m^2 * b^2 + m^2 * r^2 - b^2 + r^2)))/ 2m^2 + 2
(-2mb ± sqrt(4 * (m^2 * r^2 - b^2 + r^2)))/ 2m^2 + 2
(-2mb ± sqrt(4) * sqrt(m^2 * r^2 - b^2 + r^2))/ 2m^2 + 2
(-2mb ± 2 * sqrt(m^2 * r^2 - b^2 + r^2))/ 2m^2 + 2
(-2mb ± 2 * sqrt(m^2 * r^2 + r^2 - b^2))/ 2m^2 + 2
(-2mb ± 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2

Это почти настолько, насколько это упростит. Наконец, выделите уравнения с помощью & # xB1 ;:

(-2mb + 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2 or     
(-2mb - 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2 

Затем просто вставьте результат обоих этих уравнений вx вmx + b, Для ясности я написал некоторый код JavaScript, чтобы показать, как его использовать:

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((Math.pow(r,2)*(Math.pow(m,2)+1)),2)-Math.pow(b,2)); //the value under the square root sign 

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

Надеюсь, это поможет!

Постскриптум Если кто-то обнаружит какие-либо ошибки или у вас есть предложения, пожалуйста, оставьте комментарий. Я очень новичок и приветствую любую помощь / предложения.

СunderRadical дополнительные ")"
Если возможно, также публикуйте образцы значений, чтобы мы могли быстро понять процесс.
Это на самом деле не работает, смотрите ответ @Duq
17

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

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

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

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

круто, рад помочь
Это было на самом деле то, что я хотел. Я хочу теорию, поиск в Google алгоритма столкновения линии с окружностью показывает только код, насколько я могу видеть. Mizipzor
+1 Потрясающее объяснение! Но я думаю, что это предполагает линию, а не отрезок. Таким образом, если бы ближайшая точка на этой линии к центру круга не находилась между точками A и B, она все равно была бы подсчитана.
Мы не предполагаем, что m равно нулю; сначала мы рассчитываем градиент (чтобы уравнение линии выглядело как y = 2x + m в качестве примера), а затем, получив градиент, мы можем решить его для m, подключив центр круга к y и x ,
Ой, извините - я использую простое уравнение линии с градиентом и смещением (декартово уравнение). Я предположил, что вы сохраняете линию как такое уравнение - в этом случае вы используете отрицательный градиент для k. Если у вас нет такой строки, вы можете рассчитать k как (y2-y1) / (x2-x1)
1

Эта функция 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;
}
4

Вы можете найти точку на бесконечной прямой, ближайшую к центру окружности, проецируя вектор 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
  }
}

РЕДАКТИРОВАТЬ: добавлен код, чтобы проверить, действительно ли найденные точки пересечения находятся в отрезке.

Первоначальный вопрос касался отрезков, а не пересечения окружностей, что гораздо проще.
@ADB на самом деле мой алгоритм работает только для бесконечных линий, а не отрезков. Есть много случаев, когда он не обрабатывает отрезки.
Вы пропустили один случай, так как мы говорим о отрезке линии: когда отрезок заканчивается кружком.
2

Я создал эту функцию для iOS, следуя ответуchmike

+ (NSArray *)intersectionPointsOfCircleWithCenter:(CGPoint)center withRadius:(float)radius toLinePoint1:(CGPoint)p1 andLinePoint2:(CGPoint)p2
{
    NSMutableArray *intersectionPoints = [NSMutableArray array];

    float Ax = p1.x;
    float Ay = p1.y;
    float Bx = p2.x;
    float By = p2.y;
    float Cx = center.x;
    float Cy = center.y;
    float R = radius;


    // compute the euclidean distance between A and B
    float LAB = sqrt( pow(Bx-Ax, 2)+pow(By-Ay, 2) );

    // compute the direction vector D from, A to B
    float Dx = (Bx-Ax)/LAB;
    float 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)
    float 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
    float Ex = t*Dx+Ax;
    float Ey = t*Dy+Ay;

    // compute the euclidean distance from E to C
    float LEC = sqrt( pow(Ex-Cx, 2)+ pow(Ey-Cy, 2) );

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

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

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

        [intersectionPoints addObject:[NSValue valueWithCGPoint:CGPointMake(Fx, Fy)]];
        [intersectionPoints addObject:[NSValue valueWithCGPoint:CGPointMake(Gx, Gy)]];
    }

    // else test if the line is tangent to circle
    else if( LEC == R ) {
        // tangent point to circle is E
        [intersectionPoints addObject:[NSValue valueWithCGPoint:CGPointMake(Ex, Ey)]];
    }
    else {
        // line doesn't touch circle
    }

    return intersectionPoints;
}
3

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

Вы можете попробовать код здесь на этомживое демо. The code was taken from my алгоритмы репо.

enter image description here

// 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 [];

}

Похожие вопросы