Столкновение между кольцом и линией

Question

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

Answer 1

Рассчитать расстояние между центром круга и линией, как описано here.

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

Answer 2

Использование математики от this link, здесь функция, которая возвращает все точки пересечения. Ввод - это центральная точка и радиус для круга, а для линии - высота m и смещение оси y c.

Добавление в связанное математическое решение Я добавил код для vertical lines. Для этих наборов m = float.PositiveInfinity; и c = y-offset (т. Е. Координата x линии)!

List<PointF> Intersections(PointF cc, float r, float m, float c) 
{ 
    List<PointF> points = new List<PointF>(); 
    // vertical lines: 
    if (float.IsPositiveInfinity(m)) 
     { 
      float b = (float) Math.Sqrt(r * r + (c - cc.X) * (c - cc.X)); 
      points.Add(new PointF(c, cc.Y + b)); 
      points.Add(new PointF(c, cc.Y - b)); 
      return points; 
     } 

    float A = (m * m + 1f); 
    float B = 2*(m * c - m * cc.Y - cc.X); 
    float C = cc.Y * cc.Y - r * r + cc.X * cc.X - 2f * c * cc.Y + c * c; 
    float disc = B * B - 4f * A * C; 
    if (disc < 0) return points; 
    float x1 = (float)(-B - Math.Sqrt(disc))/2f/A; 
    float y1 = m * x1 + c; 
    points.Add(new PointF(x1, y1)); 
    if (disc != 0) 
    { 
     float x2 = (float)(-B + Math.Sqrt(disc))/2f/A; 
     float y2 = m * x2 + c; 
     points.Add(new PointF(x2, y2)); 
    } 
    return points; 
} 

Вот перегрузки для двухточечной формы линии:

List<PointF> Intersections(PointF cc, float r, PointF p1, PointF p2) 
{ 
    float m = 0; float c = 0; 
    if (p1.X == p2.X) { m = float.PositiveInfinity; c = p1.X; } 
    else    { m = (p2.Y - p1.Y)/(p2.X - p1.X);c = p1.Y - m * p1.X; } 
    return Intersections(cc, r, m, c); 
} 

Вот небольшой стендовый с помощью пустой Form:

float radius = 200;   PointF center = new PointF(480,360); 
PointF pt1 = PointF.Empty; PointF pt2 = PointF.Empty; 
List<PointF> pointsM = new List<PointF>(); 

private void Form1_MouseMove(object sender, MouseEventArgs e) 
{ 
    if (e.Button == MouseButtons.Left) 
    { // drag around and watch the points 
     pt2 = e.Location; 
     pointsM = Intersections(center, radius, pt1, pt2, false); 
     Invalidate(); 
    } 
} 

private void Form1_MouseClick(object sender, MouseEventArgs e) 
{ // right-click to set the first point 
    if (e.Button == MouseButtons.Right) pt1 = e.Location; 
    Invalidate(); 
} 

private void Form1_Paint(object sender, PaintEventArgs e) 
{ 
    e.Graphics.DrawEllipse(Pens.Blue, center.X - radius, center.Y - radius, 
          radius * 2, radius * 2); 
    e.Graphics.DrawLine(Pens.Green, pt1, pt2); 
    e.Graphics.FillEllipse(Brushes.Blue, center.X - 4, center.Y - 4, 8, 8); 
    foreach (PointF pt in pointsM) 
     e.Graphics.FillEllipse(Brushes.DarkOrange, pt.X - 4, pt.Y - 4, 8, 8); 
    e.Graphics.FillEllipse(Brushes.Green, pt1.X - 4, pt1.Y - 4, 8, 8); 
    e.Graphics.FillEllipse(Brushes.DeepPink, pt2.X - 4, pt2.Y - 4, 8, 8); 
    Text = pointsM.Count + " intersection points."; 
}