圆线段碰撞检测算法？

我有一条从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
成
（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 + _t d _x ） ² -2（e _x + _t d _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. 接着，
   （_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: // -> oo -> | -> | // 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是圆半径。

这是算法

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

Answer 4

好吧，我不会给你代码，但是因为你已经标记了这个算法 ，我不认为这对你是重要的。 首先，你必须得到一个垂直于该线的矢量。

你将有一个未知的变量在y = ax + c （ c将是未知的）
为了解决这个问题，当线通过圆的中心时计算它的值。

那是，
将圆心的位置插入线方程并求解c 。
然后计算原线与其正常的交点。

这会给你一个最接近圆的线。
计算此点与圆心之间的距离（使用矢量的大小）。
如果这小于圆的半径 – 瞧，我们有一个十字路口！

Answer 5

另一种方法使用三角形ABC面积公式。 交点测试比投影方法更简单，更高效，但找到交点的坐标需要更多的工作。 至少它会被推迟到需要的地步。

计算三角形面积的公式是：面积= 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和段长度不为null，如果这可能发生在您的应用程序。

Answer 6

我发现这个解决方案似乎更容易跟随其他的一些。

考虑：

 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 

这几乎就要简化了。 最后，用±来分解方程：

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

然后简单地将这两个方程的结果插入到mx + b的x中。 为了清楚起见，我写了一些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 - cx, y:p1.y - cy} //shifted line points var p4 = {x:p2.x - cx, y:p2.y - cy} 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如果有人发现任何错误或有任何建议，请评论。 我很新，欢迎所有帮助/建议。

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

Answer 8

你可以在矢量AB上投影矢量AC，找到离圆心最近的无限长线上的一个点。 计算该点与圆心之间的距离。 如果它大于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 } } 

编辑：添加代码来检查找到的交点实际上是否在线段内。

Answer 9

奇怪的是我可以回答，但不能评论…我喜欢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+cx, y:m*t1+b+cy};

整个功能就变成：

 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 - cx, y:p1.y - cy}; //shifted line points var p4 = {x:p2.x - cx, y:p2.y - cy}; 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+cx, y:m*t1+b+cy}; //intercept point 1 var i2 = {x:t2+cx, y:m*t2+b+cy}; //intercept point 2 return [i1, i2]; } } 

Answer 10

你需要一些数学在这里：

假设A =（Xa，Ya），B =（Xb，Yb）和C =（Xc，Yc）。 从A到B的线上的任何点都有坐标（alpha * Xa +（1-alpha） Xb，alpha Ya +（1-alpha）* 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的坐标，则可以得到交点（如果存在的话）。

Answer 11

如果你发现球体的中心（因为它是三维的，我假设你的意思是球体而不是圆的）和线之间的距离，那么检查这个距离是否小于半径。

碰撞点显然是线和球体之间的最近点（当你计算球体和线之间的距离时，将会计算出这个点）

点与线之间的距离：
http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html

Answer 12

如果线的坐标是Ax，Ay和Bx，By和圆心是Cx，Cy，那么线的公式是：

x = Ax * t + Bx *（1-t）

y = Ay * t + By *（1-t）

其中0 <= t <= 1

和圆是

（Cx-x）^ 2 +（Cy-y）^ 2 = R ^ 2

如果将线的x和y公式替换为圆公式，则可以得到t的二阶方程，其解是交点（如果有的话）。 如果你得到的是小于0或大于1，那么它不是一个解决方案，但它表明该线是“指向”的方向的圆。

Answer 13

只是除了这个线程…下面是由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)); } 

Answer 14

我已经为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; } 

Answer 15

这个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; } 

Answer 16

 ' 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 

Answer 17

另一个在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; } // ****************************************************************** } } 

Answer 18

Here's an implementation in Javascript. My approach is to first convert the line segment into an infinite line then find the intersection point(s). From there I check if the point(s) found are on the line segment. The code is well documented, you should be able to follow along.

You can try out the code here on this live demo . The code was taken from my algorithms 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 (xX)^2 + (yY)^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 = (-BD)/(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 19

Here is good solution in JavaScript (with all required mathematics and live illustration) https://bl.ocks.org/milkbread/11000965

Though is_on function in that solution needs modifications:

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