我有一条从a到B的直线和一个半径为R的圆。
用什么算法来检查直线是否与圆相交?它在圆边的哪个坐标上?
我有一条从a到B的直线和一个半径为R的圆。
用什么算法来检查直线是否与圆相交?它在圆边的哪个坐标上?
当前回答
在此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。
其他回答
圆真的是一个坏人:)所以一个好办法是避免真正的圆,如果可以的话。如果你正在为游戏做碰撞检查,你可以进行一些简化,只做3个点积,并进行一些比较。
我称之为“胖点”或“瘦圈”。它是平行于线段方向上半径为0的椭圆。而是垂直于线段方向的全半径
首先,我会考虑重命名和切换坐标系统,以避免过多的数据:
s0s1 = B-A;
s0qp = C-A;
rSqr = r*r;
其次,hvec2f中的索引h意味着vector必须支持水平操作,如dot()/det()。这意味着它的组件被放置在一个单独的xmm寄存器中,以避免shuffle /hadd'ing/hsub'ing。现在我们开始,最简单的2D游戏碰撞检测的最佳性能版本:
bool fat_point_collides_segment(const hvec2f& s0qp, const hvec2f& s0s1, const float& rSqr) {
auto a = dot(s0s1, s0s1);
//if( a != 0 ) // if you haven't zero-length segments omit this, as it would save you 1 _mm_comineq_ss() instruction and 1 memory fetch
{
auto b = dot(s0s1, s0qp);
auto t = b / a; // length of projection of s0qp onto s0s1
//std::cout << "t = " << t << "\n";
if ((t >= 0) && (t <= 1)) //
{
auto c = dot(s0qp, s0qp);
auto r2 = c - a * t * t;
return (r2 <= rSqr); // true if collides
}
}
return false;
}
我怀疑你能进一步优化它。我正在用它进行神经网络驱动的赛车碰撞检测,处理数百万个迭代步骤。
似乎没人考虑投影,我是不是完全跑题了?
将向量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};
}
这是一个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 [];
}
这里你需要一些数学知识:
假设A = (Xa, Ya), B = (Xb, Yb), C = (Xc, Yc)。从A到B的直线上的任意一点都有坐标(*Xa + (1-)Xb, * ya + (1-)*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公式应用到这个方程来求解,并使用alpha的解来计算P的坐标,你会得到交点,如果存在的话。
也许有另一种方法来解决这个问题,使用坐标系的旋转。
通常,如果一个线段是水平的或垂直的,这意味着平行于x轴或y轴,交点的求解很容易,因为我们已经知道交点的一个坐标,如果有的话。剩下的显然是用圆的方程找到另一个坐标。
受此启发,我们可以利用坐标系旋转,使一个轴的方向与线段的方向重合。
让我们以圆x^2+y^2=1和线段P1-P2为例,P1(-1.5,0.5)和P2(-0.5,-0.5)在x-y系统中。下面的方程提醒你旋转的原理,其中是逆时针方向的角度,x'-y'是旋转后的方程组:
x'=x*cos () + y*sin () y' = - x*sin () + y*cos ()
和反向
X = X ' * cos - y' * sin Y = x' * sin + Y ' * cos
考虑P1-P2方向(用-x表示为45°),我们可以取=45°。将第二个旋转方程转化为x-y系统中的圆方程:x^2+y^2=1,经过简单的运算,我们得到x'-y'系统中的“相同”方程:x'^2+y'^2=1。
利用第一个旋转方程=> P1(-根号(2)/2,根号(2)),P2(-根号(2)/ 2,0),线段端点变成x'-y'系统。
假设交点为p,在x'-y'中,Px = -根号2 /2。使用新的圆方程,我们得到Py = +根号(2)/2。将P转换成原始的x-y系统,最终得到P(-1,0)
为了实现这个数值,我们可以先看看线段的方向:水平,垂直或不垂直。如果它属于前两种情况,很简单。如果是最后一种情况,应用上述算法。
为了判断是否有交集,我们可以将解与端点坐标进行比较,看看它们之间是否有一个根。
我相信只要我们有了它的方程,这个方法也可以应用于其他曲线。唯一的缺点是,我们应该在x'-y'坐标系下解方程,这可能很难。