圆线段碰撞检测算法？

Question

圆线段碰撞检测算法？

我有一条从A到B的直线，在C上有一个半径为R的圆。

检查直线是否与圆相交的好算法是什么？在圆周边缘的什么坐标上发生了这种情况？

Answer 1

取E是射线的起点，L是射线的终点，C是你要测试的球体的中心r是那个球体的半径计算：d=L-E(射线的方向矢量，从头到尾)f=E-C(从中心球到射线起始的矢量)然后交叉口被.。堵塞：P=E+t*d这是一个参数方程：Px=Ex+TDxPy=Ey+TDy进(X-h)2+(y-k)2=r2(h，k)=圆心。注意：我们将问题简化为2D，我们得到的解决方案也适用于3D得到：扩张x2-2xh+h2+y2-2yk+k2-r2&nbsp;= 0塞子X=ex+TDxY=ey+TDy(E)x+TDx&nbsp;)2-2(E)x+TDx)h+h2+(E)y+TDy&nbsp;)2-2(E)y+TDy)k+k2-r2&nbsp;= 0爆炸ex2+2Ex白破疫苗x+t2dx2-2exH-2TdxH+h2+ey2+2Ey白破疫苗y+t2dy2-2eyK-2tdyK+k2-r2&nbsp;= 0群t2(D)x2+dy2)+2t(E)xdx+eydy-dx氢-dyk)+ex2+ey2-2ex氢-2eyK+h2+k2-r2&nbsp;= 0最后，t2(_d*_d)+2t(_e*_d-_d*_c)+_e*_e-2(_e*_c)+_c*_c-r2&nbsp;= 0*其中_d是向量d，*是点积。然后,t2(_d*_d)+2t(_d*(_e-c)+(_e-c)*(_e-c)-r2&nbsp;= 0让f=_e-_ct2(_d*_d)+2t(_d*_f)+_f*_f-r2&nbsp;= 0所以我们得到：t2*(D DOT D)+2t*(F DOT D)+(f DOT f-r)2&nbsp;) = 0所以解二次方程：float&nbsp;a&nbsp;=&nbsp;d.Dot(&nbsp;d&nbsp;)&nbsp;; float&nbsp;b&nbsp;=&nbsp;2*f.Dot(&nbsp;d&nbsp;)&nbsp;; float&nbsp;c&nbsp;=&nbsp;f.Dot(&nbsp;f&nbsp;)&nbsp;-&nbsp;r*r&nbsp;; float&nbsp;discriminant&nbsp;=&nbsp;b*b-4*a*c; if(&nbsp;discriminant&nbsp;<&nbsp;0&nbsp;) { &nbsp;&nbsp;//&nbsp;no&nbsp;intersection } else { &nbsp;&nbsp;//&nbsp;ray&nbsp;didn't&nbsp;totally&nbsp;miss&nbsp;sphere, &nbsp;&nbsp;//&nbsp;so&nbsp;there&nbsp;is&nbsp;a&nbsp;solution&nbsp;to &nbsp;&nbsp;//&nbsp;the&nbsp;equation. &nbsp;&nbsp;discriminant&nbsp;=&nbsp;sqrt(&nbsp;discriminant&nbsp;); &nbsp;&nbsp;//&nbsp;either&nbsp;solution&nbsp;may&nbsp;be&nbsp;on&nbsp;or&nbsp;off&nbsp;the&nbsp;ray&nbsp;so&nbsp;need&nbsp;to&nbsp;test&nbsp;both &nbsp;&nbsp;//&nbsp;t1&nbsp;is&nbsp;always&nbsp;the&nbsp;smaller&nbsp;value,&nbsp;because&nbsp;BOTH&nbsp;discriminant&nbsp;and &nbsp;&nbsp;//&nbsp;a&nbsp;are&nbsp;nonnegative. &nbsp;&nbsp;float&nbsp;t1&nbsp;=&nbsp;(-b&nbsp;-&nbsp;discriminant)/(2*a); &nbsp;&nbsp;float&nbsp;t2&nbsp;=&nbsp;(-b&nbsp;+&nbsp;discriminant)/(2*a); &nbsp;&nbsp;//&nbsp;3x&nbsp;HIT&nbsp;cases: &nbsp;&nbsp;//&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-o->&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;--|-->&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;--|-> &nbsp;&nbsp;//&nbsp;Impale(t1&nbsp;hit,t2&nbsp;hit),&nbsp;Poke(t1&nbsp;hit,t2>1),&nbsp;ExitWound(t1<0,&nbsp;t2&nbsp;hit),&nbsp; &nbsp;&nbsp;//&nbsp;3x&nbsp;MISS&nbsp;cases: &nbsp;&nbsp;//&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;->&nbsp;&nbsp;o&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;o&nbsp;->&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;->&nbsp;| &nbsp;&nbsp;//&nbsp;FallShort&nbsp;(t1>1,t2>1),&nbsp;Past&nbsp;(t1<0,t2<0),&nbsp;CompletelyInside(t1<0,&nbsp;t2>1) &nbsp;&nbsp;if(&nbsp;t1&nbsp;>=&nbsp;0&nbsp;&&&nbsp;t1&nbsp;<=&nbsp;1&nbsp;) &nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;t1&nbsp;is&nbsp;the&nbsp;intersection,&nbsp;and&nbsp;it's&nbsp;closer&nbsp;than&nbsp;t2 &nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;(since&nbsp;t1&nbsp;uses&nbsp;-b&nbsp;-&nbsp;discriminant) &nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;Impale,&nbsp;Poke &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;true&nbsp;; &nbsp;&nbsp;} &nbsp;&nbsp;//&nbsp;here&nbsp;t1&nbsp;didn't&nbsp;intersect&nbsp;so&nbsp;we&nbsp;are&nbsp;either&nbsp;started &nbsp;&nbsp;//&nbsp;inside&nbsp;the&nbsp;sphere&nbsp;or&nbsp;completely&nbsp;past&nbsp;it &nbsp;&nbsp;if(&nbsp;t2&nbsp;>=&nbsp;0&nbsp;&&&nbsp;t2&nbsp;<=&nbsp;1&nbsp;) &nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;ExitWound &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;true&nbsp;; &nbsp;&nbsp;} &nbsp;&nbsp;//&nbsp;no&nbsp;intn:&nbsp;FallShort,&nbsp;Past,&nbsp;CompletelyInside &nbsp;&nbsp;return&nbsp;false&nbsp;; }

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。这是算法//&nbsp;compute&nbsp;the&nbsp;euclidean&nbsp;distance&nbsp;between&nbsp;A&nbsp;and&nbsp;B LAB&nbsp;=&nbsp;sqrt(&nbsp;(Bx-Ax)²+(By-Ay)²&nbsp;) //&nbsp;compute&nbsp;the&nbsp;direction&nbsp;vector&nbsp;D&nbsp;from&nbsp;A&nbsp;to&nbsp;B Dx&nbsp;=&nbsp;(Bx-Ax)/LAB Dy&nbsp;=&nbsp;(By-Ay)/LAB //&nbsp;the&nbsp;equation&nbsp;of&nbsp;the&nbsp;line&nbsp;AB&nbsp;is&nbsp;x&nbsp;=&nbsp;Dx*t&nbsp;+&nbsp;Ax,&nbsp;y&nbsp;=&nbsp;Dy*t&nbsp;+&nbsp;Ay&nbsp;with&nbsp;0&nbsp;<=&nbsp;t&nbsp;<=&nbsp;LAB. //&nbsp;compute&nbsp;the&nbsp;distance&nbsp;between&nbsp;the&nbsp;points&nbsp;A&nbsp;and&nbsp;E,&nbsp;where //&nbsp;E&nbsp;is&nbsp;the&nbsp;point&nbsp;of&nbsp;AB&nbsp;closest&nbsp;the&nbsp;circle&nbsp;center&nbsp;(Cx,&nbsp;Cy) t&nbsp;=&nbsp;Dx*(Cx-Ax)&nbsp;+&nbsp;Dy*(Cy-Ay)&nbsp;&nbsp;&nbsp;&nbsp; //&nbsp;compute&nbsp;the&nbsp;coordinates&nbsp;of&nbsp;the&nbsp;point&nbsp;E Ex&nbsp;=&nbsp;t*Dx+Ax Ey&nbsp;=&nbsp;t*Dy+Ay //&nbsp;compute&nbsp;the&nbsp;euclidean&nbsp;distance&nbsp;between&nbsp;E&nbsp;and&nbsp;C LEC&nbsp;=&nbsp;sqrt((Ex-Cx)²+(Ey-Cy)²) //&nbsp;test&nbsp;if&nbsp;the&nbsp;line&nbsp;intersects&nbsp;the&nbsp;circle if(&nbsp;LEC&nbsp;<&nbsp;R&nbsp;) { &nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;compute&nbsp;distance&nbsp;from&nbsp;t&nbsp;to&nbsp;circle&nbsp;intersection&nbsp;point &nbsp;&nbsp;&nbsp;&nbsp;dt&nbsp;=&nbsp;sqrt(&nbsp;R²&nbsp;-&nbsp;LEC²) &nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;compute&nbsp;first&nbsp;intersection&nbsp;point &nbsp;&nbsp;&nbsp;&nbsp;Fx&nbsp;=&nbsp;(t-dt)*Dx&nbsp;+&nbsp;Ax &nbsp;&nbsp;&nbsp;&nbsp;Fy&nbsp;=&nbsp;(t-dt)*Dy&nbsp;+&nbsp;Ay &nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;compute&nbsp;second&nbsp;intersection&nbsp;point &nbsp;&nbsp;&nbsp;&nbsp;Gx&nbsp;=&nbsp;(t+dt)*Dx&nbsp;+&nbsp;Ax &nbsp;&nbsp;&nbsp;&nbsp;Gy&nbsp;=&nbsp;(t+dt)*Dy&nbsp;+&nbsp;Ay } //&nbsp;else&nbsp;test&nbsp;if&nbsp;the&nbsp;line&nbsp;is&nbsp;tangent&nbsp;to&nbsp;circle else&nbsp;if(&nbsp;LEC&nbsp;==&nbsp;R&nbsp;) &nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;tangent&nbsp;point&nbsp;to&nbsp;circle&nbsp;is&nbsp;E else &nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;line&nbsp;doesn't&nbsp;touch&nbsp;circle