我有一条从a到B的直线和一个半径为R的圆。
用什么算法来检查直线是否与圆相交?它在圆边的哪个坐标上?
我有一条从a到B的直线和一个半径为R的圆。
用什么算法来检查直线是否与圆相交?它在圆边的哪个坐标上?
当前回答
另一种方法使用三角形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是否不同,并且段长度不为空。
其他回答
似乎没人考虑投影,我是不是完全跑题了?
将向量AC投影到AB上,投影的向量AD就得到了新的点D。 如果D和C之间的距离小于(或等于)R,我们有一个交点。
是这样的:
社区编辑:
对于稍后无意中看到这篇文章并想知道如何实现这样一个算法的人来说,这里是一个使用常见向量操作函数用JavaScript编写的通用实现。
/**
* Returns the distance from line segment AB to point C
*/
function distanceSegmentToPoint(A, B, C) {
// Compute vectors AC and AB
const AC = sub(C, A);
const AB = sub(B, A);
// Get point D by taking the projection of AC onto AB then adding the offset of A
const D = add(proj(AC, AB), A);
const AD = sub(D, A);
// D might not be on AB so calculate k of D down AB (aka solve AD = k * AB)
// We can use either component, but choose larger value to reduce the chance of dividing by zero
const k = Math.abs(AB.x) > Math.abs(AB.y) ? AD.x / AB.x : AD.y / AB.y;
// Check if D is off either end of the line segment
if (k <= 0.0) {
return Math.sqrt(hypot2(C, A));
} else if (k >= 1.0) {
return Math.sqrt(hypot2(C, B));
}
return Math.sqrt(hypot2(C, D));
}
对于这个实现,我使用了两个常见的矢量操作函数,无论您在什么环境中工作,都可能已经提供了这些函数。但是,如果您还没有这些可用的功能,下面介绍如何实现它们。
// Define some common functions for working with vectors
const add = (a, b) => ({x: a.x + b.x, y: a.y + b.y});
const sub = (a, b) => ({x: a.x - b.x, y: a.y - b.y});
const dot = (a, b) => a.x * b.x + a.y * b.y;
const hypot2 = (a, b) => dot(sub(a, b), sub(a, b));
// Function for projecting some vector a onto b
function proj(a, b) {
const k = dot(a, b) / dot(b, b);
return {x: k * b.x, y: k * b.y};
}
在此post circle中,通过检查圆心与线段上的点(Ipoint)之间的距离来检查线碰撞,该点表示从圆心到线段的法线N(图2)之间的交点。
(https://i.stack.imgur.com/3o6do.png)
在图像1中显示一个圆和一条直线,向量A指向线的起点,向量B指向线的终点,向量C指向圆的中心。现在我们必须找到向量E(从线起点到圆中心)和向量D(从线起点到线终点)这个计算如图1所示。
(https://i.stack.imgur.com/7098a.png)
在图2中,我们可以看到向量E通过向量E与单位向量D的“点积”投影到向量D上,点积的结果是标量Xp,表示向量N与向量D的直线起点与交点(Ipoint)之间的距离。 下一个向量X是由单位向量D和标量Xp相乘得到的。
现在我们需要找到向量Z(向量到Ipoint),它很容易它简单的向量加法向量A(在直线上的起点)和向量x。接下来我们需要处理特殊情况,我们必须检查是Ipoint在线段上,如果不是我们必须找出它是它的左边还是右边,我们将使用向量最接近来确定哪个点最接近圆。
(https://i.stack.imgur.com/p9WIr.png)
当投影Xp为负时,Ipoint在线段的左边,距离最近的向量等于线起点的向量,当投影Xp大于向量D的模时,距离最近的向量在线段的右边,距离最近的向量等于线终点的向量在其他情况下,距离最近的向量等于向量Z。
现在,当我们有最近的向量,我们需要找到从圆中心到Ipoint的向量(dist向量),很简单,我们只需要从中心向量减去最近的向量。接下来,检查向量距离的大小是否小于圆半径,如果是,那么它们就会碰撞,如果不是,就没有碰撞。
(https://i.stack.imgur.com/QJ63q.png)
最后,我们可以返回一些值来解决碰撞,最简单的方法是返回碰撞的重叠(从矢量dist magnitude中减去半径)和碰撞的轴,它的向量d。如果需要,交点是向量Z。
如果直线的坐标为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 < = t < = 1
这个圆是
(C.x - x)²+ (C.y - y)²= R²
如果你把直线的x和y公式代入圆公式,你会得到一个t的二阶方程,它的解是交点(如果有的话)。如果你得到的t小于0或大于1,那么它不是一个解,但它表明这条线“指向”圆的方向。
只是这个线程的一个补充… 下面是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));
}
虽然我认为使用线圆交点,然后检查交点是否在端点之间更好,可能更便宜,但我想添加这个更直观的解决方案。
我喜欢把这个问题想象成“香肠上的点问题”,在不改变算法的情况下,它可以在任何维度上工作。 这个解找不到交点。
以下是我想到的:
(我使用“小于”,但“小于或等于”也可以使用,这取决于我们测试的内容。)
确保Circle_Point小于到无限线的半径距离。(这里使用最喜欢的方法)。 计算从两个Segment_Points到Circle_Point的距离。 测试较大的Circle_Point-Segment_Point距离是否小于根号(Segment_Length^2+Radius^2)。 (这是从一个分段点到一个理论点的距离,也就是从另一个分段点到无限线(直角)的半径距离。见图片)。
3 t。如果为true: Circle_Point在sausage内部。 3 f。如果为false:如果较小的Circle_Point- segment_point距离小于Radius,则Circle_Point在sausage内部。
图片:最粗的线段是选定的线段,没有示例圆。有点粗糙,有些像素有点不对。
function boolean pointInSausage(sp1,sp2,r,c) {
if ( !(pointLineDist(c,sp1,sp2) < r) ) {
return false;
}
double a = dist(sp1,c);
double b = dist(sp2,c);
double l;
double s;
if (a>b) {
l = a;
s = b;
} else {
l = b;
s = a;
}
double segLength = dist(sp1,sp2);
if ( l < sqrt(segLength*segLength+r*r) ) {
return true;
}
return s < r;
}
如果发现任何问题,告诉我,我会编辑或撤回。