小编use*_*828的帖子

我在二维平面上有一组给定位置和半径的圆.我想确定每个圆圈是否与任何其他圆相交,以及将两者分开所需的距离.在我目前的实现中,我只是通过所有可能的圆组合然后进行计算.不幸的是,这个算法是O(n ^ 2),这很慢.

圆圈通常会成组聚集,并且它们具有相似(但不同)的半径.圆圈的近似最大值约为200.算法不必精确,但应该接近.

这是我目前在JavaScript中的一个(慢)实现:

// Makes a new circle
var circle = function(x,y,radius) {
    return {
        x:x,
        y:y,
        radius:radius
    };
};

// These points are not representative of the true data set. I just made them up.
var points = [
    circle(3,3,2),
    circle(7,5,4),
    circle(16,6,4),
    circle(17,12,3),
    circle(26,20,1)
];


var k = 0,
    len = points.length;
for (var i = 0; i < len; i++) {
    for (var j = k; j < len; j++) {
        if (i !== j) { …