我正在寻找一个算法来检测圆形是否与同一平面中的任何其他圆形相交（假设同一平面内可能有多个圆形）。
我发现一种方法是进行分离轴测试。其原理是：
如果能找到一条线将两个对象分开，即所有对象或对象的点都在该线的不同侧，则这两个对象不相交。
但是，我不知道如何将此方法应用于我的情况。
有人能帮帮我吗？
我发现一种方法是进行分离轴测试。其原理是：
如果能找到一条线将两个对象分开，即所有对象或对象的点都在该线的不同侧，则这两个对象不相交。
但是，我不知道如何将此方法应用于我的情况。
有人能帮帮我吗？
7个回答
77
当且仅当两个圆心之间的距离在它们的半径之和和差之间时，两个圆相交。给定两个圆 (x0, y0, R0) 和 (x1, y1, R1)，公式如下：
ABS(R0 - R1) <= SQRT((x0 - x1)^2 + (y0 - y1)^2) <= (R0 + R1)
如果你的输入是整数, 那么两边同时平方可避免使用缓慢的SQRT, 且保持整数形式:
(R0 - R1)^2 <= (x0 - x1)^2 + (y0 - y1)^2 <= (R0 + R1)^2
由于您只需要进行一个是/否测试，因此此检查比计算确切的交点更快。
上述解决方案即使针对“一个圆在另一个圆内”的情况也应该可以工作。
- Sergey Kalinichenko
7
9
假设填充圆的交集（即：一个圆在另一个圆内部被视为有交集）。
其中：
其中：
- x0、y0、r0 = 圆0的中心和半径。
- x1、y1、r1 = 圆1的中心和半径。
boolean intersects = Math.hypot(x0-x1, y0-y1) <= (r0 + r1);
- Craigo
3
1这里应该用 < 还是 <=？比如说... (y0-y1) <= (r0 + r1) ？ - Stéphane
@Stéphane 从技术上讲，如果您不关心边缘交叉，则使用< =。然而，在实际操作中，这很少有区别，因为“Math.hypot”不太可能给您一个精确的值。 - Craigo
6
XNA / C#解决方案
class Circle
{
public Vector2 Center;
public float Radius;
public bool Intersects(Circle circle)
{
float distanceX = Center.X - circle.Center.X;
float distanceY = Center.Y - circle.Center.Y;
float radiusSum = circle.Radius + Radius;
return distanceX * distanceX + distanceY * distanceY <= radiusSum * radiusSum;
}
public bool Contains(Circle circle)
{
if (circle.Radius > Radius)
return false;
float distanceX = Center.X - circle.Center.X;
float distanceY = Center.Y - circle.Center.Y;
float radiusD = Radius - circle.Radius;
return distanceX * distanceX + distanceY * distanceY <= radiusD * radiusD;
}
}- Peter Gruden
2
如果两个圆心之间的距离不超过它们半径之和，但至少大于等于它们半径之差的绝对值，则这些圆在某一点相交。
“至少差异”部分仅适用于您只关心圆本身而不关心其内部区域的情况。如果您关心圆所围绕的区域是否共享任何点 - 也就是说，如果一个圆完全位于另一个圆内则视为它们相交 - 那么您可以省略“至少差异”检查。
- cHao
0
我尝试了这里给出的公式，这是一个被认为是答案并且得到了众多投票支持的公式，但是它有严重的缺陷。我用JavaFX编写了一个程序，允许用户通过更改每个圆心和半径的值来测试两个圆是否相交，但是这个公式绝对不起作用，除了一种方式……我想不出为什么，但是当我将圆2移动到圆1附近时，它起作用了，但是当我将圆1移动到另一侧靠近圆2时，它就不起作用了.....??? 这有点奇怪....我认为应该以相反的方式测试该公式，因此我尝试了一下，但它也没有起作用。
这个是可以运行的：
if (Math.abs(circle1Radius - circle2Radius) <=
Math.sqrt(Math.pow((circle1X - circle2X), 2)
+ Math.pow((circle1Y - circle2Y), 2)) &&
Math.sqrt(Math.pow((circle1X - circle2X), 2)
+ Math.pow((circle1X - circle2Y), 2)) <=
(circle1Radius + circle2Radius)} {
return true;
} else {
return false;
}
这个是可以运行的：
// dx and dy are the vertical and horizontal distances
double dx = circle2X - circle1X;
double dy = circle2Y - circle1Y;
// Determine the straight-line distance between centers.
double d = Math.sqrt((dy * dy) + (dx * dx));
// Check Intersections
if (d > (circle1Radius + circle2Radius)) {
// No Solution. Circles do not intersect
return false;
} else if (d < Math.abs(circle1Radius - circle2Radius)) {
// No Solution. one circle is contained in the other
return false;
} else {
return true;
}
点击此处获取公式两圆交点
使用的公式并非我所创，所有功劳归于Paul Bourke（1997年4月）
First calculate the distance d between the center of the circles. d = ||P1 - P0||.
If d > r0 + r1 then there are no solutions, the circles are separate.
If d < |r0 - r1| then there are no solutions because one circle is contained within the other.
If d = 0 and r0 = r1 then the circles are coincident and there are an infinite number of solutions.
Considering the two triangles P0P2P3 and P1P2P3 we can write
a2 + h2 = r02 and b2 + h2 = r12
Using d = a + b we can solve for a,
a = (r02 - r12 + d2 ) / (2 d)
It can be readily shown that this reduces to r0 when the two circles touch at one point, ie: d = r0 + r1
Solve for h by substituting a into the first equation, h2 = r02 - a2
So
P2 = P0 + a ( P1 - P0 ) / d
And finally, P3 = (x3,y3) in terms of P0 = (x0,y0), P1 = (x1,y1) and P2 = (x2,y2), is
x3 = x2 +- h ( y1 - y0 ) / d
y3 = y2 -+ h ( x1 - x0 ) / d
- John Conner
1
另外，我想感谢lorenzo-s为我提供这个页面的链接。 - John Conner
-1
Swift 4 解决方案：
struct Circle {
let radius: CGFloat
let position: CGPoint
}
func circlesIntersect(circleA: Circle, circleB: Circle) -> Bool {
let Δr² = pow(circleA.radius - circleB.radius, 2)
let Δx² = pow(circleA.position.x - circleB.position.x, 2)
let Δy² = pow(circleA.position.y - circleB.position.y, 2)
let ΣΔx²Δy² = Δx² + Δy²
let Σr² = pow(circleA.radius + circleB.radius, 2)
return Δr² <= ΣΔx²Δy² && ΣΔx²Δy² <= Σr²
}
- bojan4
1
当 CGPoint 包含负值时，或者半径非常大以至于圆的“左”侧在其轴的负值中时，这是否有效？我认为它不会。 - xaphod
-2
这个Java解决方案使用了上述描述的数学表达式：
/**
*
* @param values
* { x0, y0, r0, x1, y1, r1 }
* @return true if circles is intersected
*
* Check if circle is intersect to another circle
*/
public static boolean isCircleIntersect(double... values) {
/*
* check using mathematical relation: ABS(R0-R1) <=
* SQRT((x0-x1)^2+(y0-y1)^2) <= (R0+R1)
*/
if (values.length == 6) {
/* get values from first circle */
double x0 = values[0];
double y0 = values[1];
double r0 = values[2];
/* get values from second circle */
double x1 = values[3];
double y1 = values[4];
double r1 = values[5];
/* returun result */
return (Math.abs(r0 - r1) <= Math.sqrt(Math.pow((x0 - x1), 2)
+ Math.pow((y0 - y1), 2)))
&& (Math.sqrt(Math.pow((x0 - x1), 2)
+ Math.pow((y0 - y1), 2)) <= (r0 + r1));
} else {
/* return default result */
return false;
}
}
- Sergiu
2
与其仅提供链接，最好在此包含回答的基本部分，并仅提供链接以供参考。如果您无法完成此任务，则应考虑在问题上留下评论而不是发布答案。但是，由于这可能只是接受答案的一种实现方式，并且该问题没有提到Java，因此我认为这并不是很有用。 - Bernhard Barker
我修复了你的帖子，你所做的不符合我们自己制定的标准。我强烈建议你在你的网站上（我假设这是你的）添加一些代码标记，以便它实际可读。不仅如此，还要确保字体没有任何花哨的东西：我不得不替换所有减号和三个点，因为它们在Eclipse中根本不是有效字符。阅读Dukeling提供的链接，避免在未来的帖子中出现这种情况。 - Jeroen Vannevel
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
i != j应该能轻松解决这个问题，对吧？ - Sergey Kalinichenko