圆-矩形碰撞检测(交叉点)
如何判断圆形和矩形在二维欧几里德空间中是否相交? (即经典的二维几何)
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
如何判断圆形和矩形在二维欧几里德空间中是否相交? (即经典的二维几何)
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
接受
或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论(27)
这是我的做法:
这是它的工作原理:
第一对行计算绝对值圆心与矩形中心之间的 x 和 y 差值。 这会将四个象限合并为一个,这样计算就不必进行四次。 该图像显示了圆心现在必须位于的区域。 请注意,仅显示了单个象限。 矩形是灰色区域,红色边框勾勒出关键区域,该区域距矩形边缘正好一个半径。 圆心必须位于该红色边框内才能发生相交。
第二对线消除了圆距矩形足够远(在任一方向)以致不可能相交的简单情况。 这对应于图像中的绿色区域。
第三对线处理简单的情况,其中圆足够接近矩形(在任一方向)以保证相交。 这对应于图像中的橙色和灰色部分。 请注意,此步骤必须在步骤 2 之后完成,逻辑才有意义。
其余的行计算圆可能与矩形的角相交的困难情况。 求解时,计算圆心到角点的距离,然后验证该距离不大于圆的半径。 对于中心位于红色阴影区域内的所有圆,此计算返回 false;对于中心位于白色阴影区域内的所有圆,此计算返回 true。
Here is how I would do it:
Here's how it works:
The first pair of lines calculate the absolute values of the x and y difference between the center of the circle and the center of the rectangle. This collapses the four quadrants down into one, so that the calculations do not have to be done four times. The image shows the area in which the center of the circle must now lie. Note that only the single quadrant is shown. The rectangle is the grey area, and the red border outlines the critical area which is exactly one radius away from the edges of the rectangle. The center of the circle has to be within this red border for the intersection to occur.
The second pair of lines eliminate the easy cases where the circle is far enough away from the rectangle (in either direction) that no intersection is possible. This corresponds to the green area in the image.
The third pair of lines handle the easy cases where the circle is close enough to the rectangle (in either direction) that an intersection is guaranteed. This corresponds to the orange and grey sections in the image. Note that this step must be done after step 2 for the logic to make sense.
The remaining lines calculate the difficult case where the circle may intersect the corner of the rectangle. To solve, compute the distance from the center of the circle and the corner, and then verify that the distance is not more than the radius of the circle. This calculation returns false for all circles whose center is within the red shaded area and returns true for all circles whose center is within the white shaded area.
圆与矩形相交只有两种情况:
请注意,这并不要求矩形与轴平行。
(查看此问题的一种方法:如果没有一条边在圆内有一个点(如果所有边都完全在圆“外部”),那么圆的唯一方法如果它完全位于多边形内部,仍然可以与多边形相交。)
有了这种洞察力,类似下面的东西就可以工作,其中圆的中心为 P ,半径为 R ,并且矩形具有按顺序排列的顶点
A
、B
、C
、D
(不是完整代码):如果当你正在编写任何几何图形时,你的库中可能已经有上述函数了。 另外,
pointInRectangle()
可以通过多种方式实现; 任何一般的多边形中的点方法都可以工作,但是对于矩形,您可以检查这是否有效:并且
intersectCircle()
也很容易实现:一种方法是检查从P
到直线的垂直线的底部是否足够近并且位于端点之间,并检查端点。很酷的是,相同的想法不仅适用于矩形,而且适用于圆与任何 简单的多边形 - 甚至不必是凸的!
There are only two cases when the circle intersects with the rectangle:
Note that this does not require the rectangle to be axis-parallel.
(One way to see this: if none of the edges has a point in the circle (if all the edges are completely "outside" the circle), then the only way the circle can still intersect the polygon is if it lies completely inside the polygon.)
With that insight, something like the following will work, where the circle has centre
P
and radiusR
, and the rectangle has verticesA
,B
,C
,D
in that order (not complete code):If you're writing any geometry you probably have the above functions in your library already. Otherwise,
pointInRectangle()
can be implemented in several ways; any of the general point in polygon methods will work, but for a rectangle you can just check whether this works:And
intersectCircle()
is easy to implement too: one way would be to check if the foot of the perpendicular fromP
to the line is close enough and between the endpoints, and check the endpoints otherwise.The cool thing is that the same idea works not just for rectangles but for the intersection of a circle with any simple polygon — doesn't even have to be convex!
这是另一个实现起来非常简单(而且速度也非常快)的解决方案。 它将捕获所有交叉点,包括球体完全进入矩形时的交叉点。
对于任何像样的数学库,都可以缩短到 3 或 4 行。
Here is another solution that's pretty simple to implement (and pretty fast, too). It will catch all intersections, including when the sphere has fully entered the rectangle.
With any decent math library, that can be shortened to 3 or 4 lines.
我想出的最简单的解决方案非常简单。
它的工作原理是找到矩形中最接近圆的点,然后比较距离。
您可以通过一些操作来完成所有这些操作,甚至可以避免使用 sqrt 函数。
就是这样! 上述解决方案假设原点位于世界的左上角,x 轴向下。
如果您想要一个处理移动圆和矩形之间碰撞的解决方案,那么它要复杂得多并且涵盖在我的另一个答案中。
The simplest solution I've come up with is pretty straightforward.
It works by finding the point in the rectangle closest to the circle, then comparing the distance.
You can do all of this with a few operations, and even avoid the sqrt function.
And that's it! The above solution assumes an origin in the upper left of the world with the x-axis pointing down.
If you want a solution to handling collisions between a moving circle and rectangle, it's far more complicated and covered in another answer of mine.
你的球体和矩形相交 IIF
圆心和矩形的一个顶点之间的距离小于球体的半径
或
圆心和矩形的一条边之间的距离小于球体的半径([点线距离])
或
圆心在矩形内
点到点距离:
点到线距离:
矩形内圆心:
采用分离轴方法:如果存在将矩形与点分开的线上的投影,则它们不会相交,
您将点投影到与矩形的边平行的线上,然后可以轻松确定它们是否相交。 如果它们不在所有 4 个投影上相交,则它们(点和矩形)不能相交。
你只需要内积( x= [x1,x2] , y = [y1,y2] , x*y = x1*y1 + x2*y2 )
你的测试看起来像这样:
这不假设轴 -对齐的矩形,并且可以轻松扩展以测试凸集之间的交集。
your sphere and rect intersect IIF
the distance between the circle-center and one vertex of your rect is smaller than the radius of your sphere
OR
the distance between the circle-center and one edge of your rect is smaller than the radius of your sphere ([point-line distance ])
OR
the circle center is inside the rect
point-point distance:
point-line distance:
circle center inside rect:
take an seperating axis aproach: if there exists a projection onto a line that seperates the rectangle from the point, they do not intersect
you project the point on lines parallel to the sides of your rect and can then easily determine if they intersect. if they intersect not on all 4 projections, they (the point and the rectangle) can not intersect.
you just need the inner-product ( x= [x1,x2] , y = [y1,y2] , x*y = x1*y1 + x2*y2 )
your test would look like that:
this does not assume an axis-aligned rectangle and is easily extendable for testing intersections between convex sets.
这是最快的解决方案:
注意执行顺序,宽度/高度的一半是预先计算的。 此外,平方是“手动”完成的,以节省一些时钟周期。
This is the fastest solution:
Note the order of execution, and half the width/height is pre-computed. Also the squaring is done "manually" to save some clock cycles.
事实上,这要简单得多。 你只需要两件事。
首先,您需要找到从圆心到矩形每条线的四个正交距离。 那么,如果其中任何三个大于圆半径,则圆将不会与矩形相交。
其次,你需要找到圆心和矩形中心之间的距离,那么如果距离大于矩形对角线长度的一半,你的圆就不会在矩形内部。
祝你好运!
Actually, this is much more simple. You need only two things.
First, you need to find four orthogonal distances from the circle centre to each line of the rectangle. Then your circle will not intersect the rectangle if any three of them are larger than the circle radius.
Second, you need to find the distance between the circle centre and the rectangle centre, then you circle will not be inside of the rectangle if the distance is larger than a half of the rectangle diagonal length.
Good luck!
如果您对甚至可以在(平面内)旋转矩形上工作的更加图形化的解决方案感兴趣。
演示: https://jsfiddle.net/exodus4d/94mxLvqh/2691/
这个想法是:
[0, 0]
If you are interested in a more graphical solution which even works on (in plane) rotated rectangles..
Demo: https://jsfiddle.net/exodus4d/94mxLvqh/2691/
The idea is:
[0, 0]
这是我的 C 代码,用于解决球体和非轴对齐框之间的碰撞。 它依赖于我自己的几个库例程,但它可能对某些人有用。 我在游戏中使用它并且效果非常好。
Here's my C code for resolving a collision between a sphere and a non-axis aligned box. It relies on a couple of my own library routines, but it may prove useful to some. I'm using it in a game and it works perfectly.
要进行可视化,请使用键盘的小键盘。 如果键“5”代表矩形,则所有键 1-9 代表空间的 9 个象限,除以构成矩形的线(其中 5 为内部)。
1) 如果圆的中心位于象限 5 (即在矩形内部)然后两个形状相交。
排除了这一点,有两种可能的情况:
a) 圆与矩形的两个或多个相邻边相交。
b) 圆与矩形的一条边相交。
第一种情况很简单。 如果圆与矩形的两个相邻边相交,则它必须包含连接这两个边的角。 (它的中心位于象限 5,我们已经介绍过。另请注意,圆仅与矩形的两个相对边相交的情况也已介绍。)
2) 如果矩形的任意一个角 A、B、C、D 位于圆内,则两个形状相交。
第二种情况比较棘手。 需要注意的是,只有当圆心位于 2、4、6 或 8 象限之一时,才会发生这种情况。(事实上,如果圆心位于 1、3、7、8 象限中的任何一个,则相应的角将是距离它最近的点。)
现在我们遇到的情况是圆的中心位于“边缘”象限之一,并且它仅与相应的边缘相交。 然后,最接近圆心的边缘上的点必须位于圆内部。
3) 对于每条线 AB、BC、CD、DA,构造通过圆心 P 的垂线 p(AB,P)、p(BC,P)、p(CD,P)、p(DA,P)。每条垂线,如果与原边的交点位于圆内,则两个形状相交。
最后一步有一个捷径。 如果圆的中心位于象限 8 且边 AB 为顶边,则交点将具有 A 和 B 的 y 坐标以及圆心 P 的 x 坐标。
您可以构造四个线交点并检查如果它们位于相应的边上,或者找出 P 位于哪个象限并检查相应的交点。 两者都应简化为相同的布尔方程。 请注意,上述步骤 2 并不排除 P 位于“角”象限之一; 它只是寻找一个交叉点。
编辑:事实证明,我忽略了一个简单的事实,即#2 是上面#3 的子情况。 毕竟,角也是边缘上的点。 请参阅下面@ShreevatsaR 的回答以获得很好的解释。 同时,请忘记上面的#2,除非您想要快速但多余的检查。
To visualise, take your keyboard's numpad. If the key '5' represents your rectangle, then all the keys 1-9 represent the 9 quadrants of space divided by the lines that make up your rectangle (with 5 being the inside.)
1) If the circle's center is in quadrant 5 (i.e. inside the rectangle) then the two shapes intersect.
With that out of the way, there are two possible cases:
a) The circle intersects with two or more neighboring edges of the rectangle.
b) The circle intersects with one edge of the rectangle.
The first case is simple. If the circle intersects with two neighboring edges of the rectangle, it must contain the corner connecting those two edges. (That, or its center lies in quadrant 5, which we have already covered. Also note that the case where the circle intersects with only two opposing edges of the rectangle is covered as well.)
2) If any of the corners A, B, C, D of the rectangle lie inside the circle, then the two shapes intersect.
The second case is trickier. We should make note of that it may only happen when the circle's center lies in one of the quadrants 2, 4, 6 or 8. (In fact, if the center is on any of the quadrants 1, 3, 7, 8, the corresponding corner will be the closest point to it.)
Now we have the case that the circle's center is in one of the 'edge' quadrants, and it only intersects with the corresponding edge. Then, the point on the edge that is closest to the circle's center, must lie inside the circle.
3) For each line AB, BC, CD, DA, construct perpendicular lines p(AB,P), p(BC,P), p(CD,P), p(DA,P) through the circle's center P. For each perpendicular line, if the intersection with the original edge lies inside the circle, then the two shapes intersect.
There is a shortcut for this last step. If the circle's center is in quadrant 8 and the edge AB is the top edge, the point of intersection will have the y-coordinate of A and B, and the x-coordinate of center P.
You can construct the four line intersections and check if they lie on their corresponding edges, or find out which quadrant P is in and check the corresponding intersection. Both should simplify to the same boolean equation. Be wary of that the step 2 above did not rule out P being in one of the 'corner' quadrants; it just looked for an intersection.
Edit: As it turns out, I have overlooked the simple fact that #2 is a subcase of #3 above. After all, corners too are points on the edges. See @ShreevatsaR's answer below for a great explanation. And in the meanwhile, forget #2 above unless you want a quick but redundant check.
此函数检测圆形和矩形之间的碰撞(相交)。 他在回答中的工作方式类似于 e.James 方法,但是这个方法检测矩形所有角度(不仅仅是右上角)的碰撞。
注意:
aRect.origin.x 和 aRect.origin.y 是矩形左下角的坐标!
aCircle.x 和 aCircle.y 是圆心的坐标!
This function detect collisions (intersections) between Circle and Rectangle. He works like e.James method in his answer, but this one detect collisions for all angles of rectangle (not only right up corner).
NOTE:
aRect.origin.x and aRect.origin.y are coordinates of bottom left angle of rectangle!
aCircle.x and aCircle.y are coordinates of Circle Center!
稍微改进一下e.James的答案:
这减去了
rect.w / 2
并且rect.h / 2
一次而不是最多三次。Improving a little bit the answer of e.James:
This subtracts
rect.w / 2
andrect.h / 2
once instead of up to three times.我有一种方法,如果没有必要,可以避免昂贵的毕达哥拉斯 - 即。 当矩形和圆形的边界框不相交时。
它也适用于非欧几里德:
normedDist = dist*dist;
查看完整的BBox 和 Circle 我的 GraphHopper 项目。
I've a method which avoids the expensive pythagoras if not necessary - ie. when bounding boxes of the rectangle and the circle do not intersect.
And it'll work for non-euclidean too:
dLat=(lat-circleY); dLon=(lon-circleX); normed=dLat*dLat+dLon*dLon
. Of course if you use that normDist method you'll need to do create anormedDist = dist*dist;
for the circleSee the full BBox and Circle code of my GraphHopper project.
我创建了处理形状的类
希望你喜欢
I created class for work with shapes
hope you enjoy
这是修改后的代码 100% 工作:
Bassam Alugili
Here is the modfied code 100% working:
Bassam Alugili
这是对此的快速单行测试:
这是轴对齐的情况,其中 rect_halves 是从矩形中间指向角的正向量。
length()
中的表达式是从center
到矩形中最近点的增量向量。 这在任何维度都有效。Here's a fast one-line test for this:
This is the axis-aligned case where
rect_halves
is a positive vector pointing from the rectangle middle to a corner. The expression insidelength()
is a delta vector fromcenter
to a closest point in the rectangle. This works in any dimension.它很高效,因为:
It's efficient, because:
对我有用(仅当矩形角度为 180 时才有效)
worked for me (only work when angle of rectangle is 180)
对于那些必须使用 SQL 计算地理坐标中的圆/矩形碰撞的人,
这是我在 e.James 建议算法 的 oracle 11 中的实现。
在输入中,它需要圆坐标、以公里为单位的圆半径和矩形的两个顶点坐标:
For those have to calculate Circle/Rectangle collision in Geographic Coordinates with SQL,
this is my implementation in oracle 11 of e.James suggested algorithm.
In input it requires circle coordinates, circle radius in km and two vertices coordinates of the rectangle:
有效,一周前才发现这一点,现在才开始测试。
Works, just figured this out a week ago, and just now got to testing it.
我在制作这个游戏时开发了这个算法:https://mshwf.github.io/mates/
如果圆与正方形相交,则圆的中心线与正方形的中心线之间的距离应等于
(直径+边长)/2
。因此,让我们有一个名为
touching
的变量来保存该距离。 问题是:我应该考虑哪条中心线:水平还是垂直?考虑这个框架:
< img src="https://1.bp.blogspot.com/-kUQjhsDgT2o/XwOb5sln4TI/AAAAAAAAQms/S_K6EW0XRRE8j79h2PI_QN3gKXrs5E-kACK4BGAsYHg/s499/collision%2Balgo-2.jpg" alt="在此处输入图像描述">
每条中心线给出不同的距离,只有一个是无碰撞的正确指示,但使用我们人类的直觉是理解自然算法如何工作的开始。
它们没有接触,这意味着两条中心线之间的距离应该大于
接触
,这意味着自然算法会选择水平中心线(垂直中心线表明存在碰撞!)。 通过观察多个圆圈,您可以看出:如果圆与正方形的垂直延伸线相交,那么我们选择垂直距离(水平中心线之间),如果圆与水平延伸线相交,我们选择水平距离:另一个示例,圆圈数字4:它与正方形的水平延伸相交,那么我们考虑等于接触的水平距离。
好的,最困难的部分已经揭开了,现在我们知道算法是如何工作的,但是我们如何知道圆与哪个扩展相交呢?
实际上很简单:我们计算最右
x
和最左x
(圆形和正方形)之间的距离,y 轴也是如此,值较大的轴是其延伸部分与圆相交的轴(如果它大于直径+边,则圆位于两个正方形延伸部分之外,如圆#7)。 代码如下:I developed this algorithm while making this game: https://mshwf.github.io/mates/
If the circle touches the square, then the distance between the centerline of the circle and the centerline of the square should equal
(diameter+side)/2
.So, let's have a variable named
touching
that holds that distance. The problem was: which centerline should I consider: the horizontal or the vertical?Consider this frame:
Each centerline gives different distances, and only one is a correct indication to a no-collision, but using our human intuition is a start to understand how the natural algorithm works.
They are not touching, which means that the distance between the two centerlines should be greater than
touching
, which means that the natural algorithm picks the horizontal centerlines (the vertical centerlines says there's a collision!). By noticing multiple circles, you can tell: if the circle intersects with the vertical extension of the square, then we pick the vertical distance (between the horizontal centerlines), and if the circle intersects with the horizontal extension, we pick the horizontal distance:Another example, circle number 4: it intersects with the horizontal extension of the square, then we consider the horizontal distance which is equal to touching.
Ok, the tough part is demystified, now we know how the algorithm will work, but how we know with which extension the circle intersects?
It's easy actually: we calculate the distance between the most right
x
and the most leftx
(of both the circle and the square), and the same for the y-axis, the one with greater value is the axis with the extension that intersects with the circle (if it's greater thandiameter+side
then the circle is outside the two square extensions, like circle #7). The code looks like:有一种非常简单的方法可以做到这一点,您必须在 x 和 y 中夹住一个点,但在正方形内部,而圆心位于垂直轴之一的两个正方形边界点之间,您需要夹住这些点坐标到平行轴,只要确保夹紧的坐标不超出正方形的限制即可。
然后获取圆心与夹紧坐标之间的距离,并检查该距离是否小于圆的半径。
这是我的做法(前 4 个点是方坐标,其余是圆点):
There is an incredibly simple way to do this, you have to clamp a point in x and y, but inside the square, while the center of the circle is between the two square border points in one of the perpendicular axis you need to clamp those coordinates to the parallel axis, just make sure the clamped coordinates do not exeed the limits of the square.
Then just get the distance between the center of the circle and the clamped coordinates and check if the distance is less than the radius of the circle.
Here is how I did it (First 4 points are the square coordinates, the rest are circle points):
我的方法:
(最近点将位于边缘/角落或内部)
(平方距离避免平方根)
My method:
(Closest point will lie on an edge/corner or inside)
(Squared distance avoids a square root)
使用下面我的Java版本的圆-方形碰撞/相交检测的答案:
原始答案:圆-矩形碰撞检测(相交)
Using the answer below my Java version of circle - square collision/intersection detection:
Original answer: Circle-Rectangle collision detection (intersection)
假设您有矩形的四个边,检查从边缘到圆心的距离,如果小于半径,则形状相交。
Assuming you have the four edges of the rectangle check the distance from the edges to the center of the circle, if its less then the radius, then the shapes are intersecting.