圆和线段碰撞

Question

什么是一个很好的算法来检查线是否与圆相交？沿着圆周边缘发生什么坐标？

Answer 1

按照here的描述计算圆的中心和直线之间的距离。

检查最近的点是否在线段的端点之间。如果在它们之间，检查距离是否小于半径;否则检查其中一个边缘点是否在圆内。

Answer 2

使用this link的数学算法，这里是返回所有交点的函数。输入是圆的中心点和半径，以及高程m和y轴的偏移c。

添加到链接的数学解决方案我已添加代码为垂直行。对于这些集合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."; 
}