如何检测同一平面上的圆与任何其他圆之间的交点？ [英] How do I detect intersections between a circle and any other circle in the same plane?

问题描述

我正在寻找一种算法来检测一个圆是否与同一平面上的任何其他圆相交（因为飞机上可能有多个圆）。

我发现的一种方法是进行分离轴测试。它说：

如果您可以找到一条分隔两个对象的线，那么两个对象不会相交，即一条线使得所有对象或者一个对象的点位于该行的不同侧。

然而，我不知道如何将这个方法应用到我的

任何人都可以帮助我吗？当且仅当它们的中心之间的距离在它们的半径的和与差之间时。给定两个圆圈（x0，y0，R0）和（x1，y1，R1），公式如下：

pre $ 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 
  

因为你只需要一个yes / no测试，所以这个检查比计算确切的交点要快。

即使是在另一个圈内情况下也是如此。

I'm looking for an algorithm to detect if a circle intersects with any other circle in the same plane (given that there can be more than one circle in a plane).

One method I have found is to do the separating axis test. It says:

Two objects don't intersect if you can find a line that separates the two objects, i.e. a line such that all objects or points of an object are on different sides of the line.

However, I don't know how to apply this method to my case.

Can anybody help me?

解决方案

Two circles intersect if, and only if, the distance between their centers is between the sum and the difference of their radii. Given two circles (x0, y0, R0) and (x1, y1, R1), the formula is as follows:

ABS(R0 - R1) <= SQRT((x0 - x1)^2 + (y0 - y1)^2) <= (R0 + R1)

Squaring both sides lets you avoid the slow SQRT, and stay with ints if your inputs are integers:

(R0 - R1)^2 <= (x0 - x1)^2 + (y0 - y1)^2 <= (R0 + R1)^2

Since you need only a yes/no test, this check is faster than calculating the exact intersection points.

The above solution should work even for the "one circle inside the other" case.

这篇关于如何检测同一平面上的圆与任何其他圆之间的交点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！