圆线段碰撞检测算法？

Question

我有一条从A到B的线和一条位于C的圆,半径为R.

用于检查线是否与圆相交的好算法是什么？它沿圆圈边缘的坐标发生了什么？

Answer 1

以

1. E是射线的起点,
2. L是光线的终点,
3. C是您正在测试的球体的中心
4. r是该球体的半径

计算:
d = L - E(射线的方向矢量,从开始到结束)
f = E - C(从中心球到射线开始的矢量)

然后找到交点.
插入:
P = E + t*d
这是一个参数方程:
P _x = E _x + td _x
P _y = E _y + td _y
into
(x - h)² +(y - k)² = r ²
(h,k)=圆心.

注意:我们在这里将问题简化为2D,我们得到的解决方案也适用于3D

要得到:

1. 展开
   x ² - 2xh + h ² + y ² - 2yk + k ² - r ² = 0
2. 插头
   x = e _x + td _x
   y = e _y + td _y
   (e _x + td _x)² - 2(e _x + td _x)h + h ² +(e _y + td _y)² - 2(e _y + td _y)k + k ² - r ² = 0
3. 爆炸
   e _x ² + 2e _x td _x + t ² d _x ² - 2e _x h - 2td _x h + h ² + e _y ² + 2e _y td _y + t ² d _y ² - 2e _y k - 2td _y k + k ² - r ² = 0
4. 组
   t ²(d _x ² + d _y ²)+ 2t(e _x d _x + e _y d _y - d _x h - d _y k)+ e _x ² + e _y ² - 2e _x h - 2e _y k + h ² + k ² - r ² = 0
5. 最后,
   t ²(_d*_d)+ 2t(_e*_d - _d*_c)+ _e*_e - 2(_e*_c)+ _c*_c - r ² = 0
   *其中_d是向量d,*是点积.*
6. 然后,
   t ²(_d*_d)+ 2t(_d*(_ e - _c))+(_ e - _c)*(_ e - _c) - r ² = 0
7. 让_f = _e - _c
   t ²(_d*_d)+ 2t(_d*_f)+ _f*_f - r ² = 0

所以得到:
t ²*(d DOT d)+ 2t*(f DOT d)+(f DOT f - r ²)= 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 ;
}

Answer 2

似乎没有人考虑投影,我完全偏离这里吗？

将矢量AC投影到AB.投影向量AD给出了新的观点D.
如果之间的距离D和C小于(或等于)R,我们有一个交叉点.

像这样:

Answer 3

我会用这个算法计算一个点(圆心)和一个线(AB线)之间的距离.然后,这可以用于确定线与圆的交点.

假设我们有点A,B,C.Ax和Ay是A点的x和y分量.B和C相同.标量R是圆半径.

该算法要求A,B和C是不同的点,并且R不是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

Answer 4

好的,我不会给你代码,但既然你已经标记了这个算法,我认为这对你不重要.首先,你必须得到一个垂直于线的矢量.

你将有一个未知的变量y = ax + c ( c将是未知的)
为了解决这个问题,当线穿过圆心时计算它的值.

也就是说,
将圆心的位置插入线方程并求解c.
然后计算原始线与其法线的交点.

这将为您提供圆圈线上的最近点.
计算此点与圆心之间的距离(使用矢量的大小).
如果这小于圆的半径 - 瞧,我们有一个交叉点!

Answer 5

另一种方法使用三角形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 )
{
    ...
}        

更新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不同,并且段长度不为空.

Answer 6

我写了一个小脚本,通过将圆的中心点投射到线上来测试交叉点.

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/

Answer 7

这是 Javascript 中的一个实现。我的方法是首先将线段转换为无限直线，然后找到交点。从那里我检查找到的点是否在线段上。该代码有详细记录，您应该能够遵循。

您可以在此现场演示中尝试此处的代码。该代码取自我的算法存储库。

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

}

Answer 8

我发现这个解决方案似乎比其他一些更容易.

考虑:

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's然后减去y's,并将它们放到一个新的点,以防万一有人不知道.

反正我现在解决与直线的方程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

这几乎可以简化.最后,用±分离出方程式:

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

然后简单地将这两个方程的结果插入到xin中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];
    }
}

我希望这有帮助!

PS如果有人发现任何错误或有任何建议,请发表评论.我很新,欢迎所有帮助/建议.