是否可以比平方距离算法更快地测试两个圆的交点？(Is it possible to test intersection of two circles faster than with squared

是否可以比平方距离算法更快地测试两个圆的交点？(Is it possible to test intersection of two circles faster than with squared-distance algorithm?)

我有这个代码来计算this圆是否与another圆相交。 我想要一个更快的版本，这可能吗？

this.CheckIntersection = function(another){ var xC = this.x; var yC = this.y; var GxC = another.x; var GyC = another.y; var distSq = (xC - GxC) * (xC - GxC) + (yC - GyC) * (yC - GyC); return distSq < (this.r + another.r) * (this.r + another.r); }

I have this code to calculate whether this circle intersections with another circle. I want a faster version, is that possible?

this.CheckIntersection = function(another){ var xC = this.x; var yC = this.y; var GxC = another.x; var GyC = another.y; var distSq = (xC - GxC) * (xC - GxC) + (yC - GyC) * (yC - GyC); return distSq < (this.r + another.r) * (this.r + another.r); }

最满意答案

那么你可以尝试改进这一点，如下所示：

this.CheckIntersection = function(another){ var dx = this.x-another.x; var dy = this.y-another.y; dx = dx*dx+dy*dy; dy = this.r+another.r; return dx < dy*dy; }

由于您节省了一些减法，因此速度会快一些，并且您使用的变量更少，因此运行时环境将更容易使用寄存器分配/缓存。

但就时间复杂性而言，你无能为力。 因此，您仅限于窥孔优化，例如寻找重复计算并尝试仅计算一次。

Well you can try to improve this a little bit as follows:

this.CheckIntersection = function(another){ var dx = this.x-another.x; var dy = this.y-another.y; dx = dx*dx+dy*dy; dy = this.r+another.r; return dx < dy*dy; }

This will be a bit faster since you save some subtractions, and you use less variables so the runtime environment will have an easier job with register allocation/caching.

But in terms of time complexity there is not much you can do. So you are limited to peephole optimization like for instance looking for duplicated computation and try to compute them only once.