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

问题描述

我正在寻找一种算法来检测一个圆是否与同一平面上的任何其他圆相交(假设一个平面上可以有多个圆).

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.

有人可以帮我吗?

推荐答案

两个圆相交当且仅当它们的圆心之间的距离在半径之和与差之间.给定两个圆(x0, y0, R0)和(x1, y1, R1)，公式如下:

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)

对两边进行平方可以避免缓慢的SQRT，如果您的输入是整数，则使用整数:

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屋！