algorithm来检测圆与相同平面中的任何其他圆相交
我正在寻找一种algorithm来检测一个圆是否与同一平面上的任何其他圆相交，因为在一个平面上可以有多个圆。
我发现的标准方法是做分离轴testing（没有谷歌search）。
它说：
Two objects don't intersect if you can find a line that separates the two objects. eg the objects / all points of an object are on different sides of the line. 但我不知道如何将其应用于圆圈。
有人可以帮我吗？
两个圆相交，当且仅当它们的中心之间的距离在它们的半径的和与差之间时。 给定两个圆（x0，y0，R0）和（x1，y1，R1），公式如下：
ABS(R0-R1) <= SQRT((x0-x1)^2+(y0-y1)^2) <= (R0+R1)
平方双方让你避免缓慢的SQRT，并保持整数，如果你的input是整数：
(R0-R1)^2 <= (x0-x1)^2+(y0-y1)^2 <= (R0+R1)^2
由于您只需要是/否testing，所以此检查比计算确切的交点要快。
编辑：纠正“其他”一案的情况。
XNA / C＃解决scheme
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; } }
假设实心圆交点（即：一个圆内的另一个交点）。
哪里：
- x0，y0，r0 =圆的中心和半径0。
- x1，y1，r1 =圆1的中心和半径。
码：
boolean intersects = Math.hypot(x0-x1, y0-y1) <= (r0 + r1);
如果两个圆的中心之间的距离至多是它们的半径之和，但至less是半径之差的绝对值，则这些圆本身在某一点上相交。
如果你只关心自己的圈子，而不关心他们的内心区域，那么“至less有区别”的部分是适用的。 如果你关心的是圈子还是他们所在的区域共享任何点 – 也就是说，如果一个圈子完全在另一个圈子内被视为“相交”，那么你可以放弃“至less差异”检查。
Swift 4解决scheme：
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² }
Java中的这个解决scheme使用了上面描述的mathexpression式：
/** * * @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; } }
我尝试了这里给出的公式，这是一个假设的答案，每个人都投了赞成票，虽然这是严重的缺陷。 我在JavaFX中编写了一个程序，允许用户通过改变每个圆centerX，centerY和Radius的值来testing两个圆是否相交，这个公式绝对不能用，除了一种方法…我找不到原因，但是当我移动圆2附近圆1它的作品，但是当我把圆1移动到另一边附近圆2它不起作用….. ????? 这有点奇怪…计算公式需要被testing相反的方式，所以尝试了，它不工作
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; }
去这里找两个圆的交点
所用的公式并不是我的公式，保罗·伯克（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
