圆线段相交 [英] Circle and Line segment intersection

问题描述

• 我有一个线段(x1，y1，x2，y2结束(D = 5可以说))和一个圆(半径R，中心x3，y3)

如何检查线段是否与圆相交?

How can I check that if my line segment intersects my circle?

推荐答案

作为初步检查，您可以使用叉积来计算点与线之间的距离:

As a preliminary check, you can just calculate the distance between a point and a line using a cross product:

(x1,y1) = p1, (x2,y2) = p2
(cx, cy) = c = circle center
delta = p2 - p1 (the difference vector)
unit = delta/norm(delta) (the unit vector along the line segment)
(c-p1) x unit = (cx-x1) * unity - (cy-y1) * unitx = d (distance of the circle center to the line)

请注意， d 具有方向(符号).

Note that d has a direction (sign).

如果 d 不在[-R，R]范围内，则线段不能与圆相交.

if d is outside the range [-R,R], then the line segment can not intersect the circle.

如果线段的移动幅度不大，则可以保存单位矢量以备后用.

If your line segments don't move around so much, you can save the unit vector for later reuse.

如果圆确实与线相交(相对于线段)，则它可能仍不与线段相交.检查以下三个条件:

If the circle does indeed intersect with the line (as opposed to the line segment) it might still not intersect with the line segment. Check these three conditions:

• p1 位于圆内；范数(p1-c)<R
• p2 位于圆内；范数(p2-c)<R
• 从直线到圆心的最近点位于 p1 和 p2 之间:

• p1 lies within the circle; norm(p1-c) < R
• p2 lies within the circle; norm(p2-c) < R
• the closest point from the line to the circle center lies between p1 and p2:

(单位.p1<单位c<单位p2)或(单位.p2<单位c<单位p1)其中.是矢量点积.

如果这些条件都不成立，则它们不相交.

If none of these conditions hold, then they don't intersect.

您可能还需要知道它们相交的位置:

You might also need to know where they intersect:

perp = (-unity, unitx) (The perpendicular vector)
pclosest = perp * d + c (The point on the line closest to the circle center)
dline = sqrt(R^2 - d^2) (The distance of the intersection points from pclosest)
i{1,2} = ±dline * unit + pclosest

您显然需要分别检查 i {1,2} 是否位于 p1 和 p2 之间，就像我们在第三篇中所做的一样以上条件.

You obviously need to check separately whether i{1,2} lie between p1 and p2, just like we did in the third condition above.

这篇关于圆线段相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！