Circle Separation Distance - Nearest Neighbor Problem

Question

I have a set of circles with given locations and radii on a two dimensional plane. I want to determine for every circle if it is intersecting with any other circle and the distance that is needed to separate the two. Under my current implementation, I just go through all the possible combinations of circles and then do the calculations. Unfortunately, this algorithm is O(n^2), which is slow.

The circles will generally be clustered in groups, and they will have similar (but different) radii. The approximate maximum for the number of circles is around 200. The algorithm does not have to be exact, but it should be close.

Here is a (slow) implementation I currently have in 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) {
            var c1 = points[i],
                c2 = points[j],
                radiiSum = c1.radius+c2.radius,
                deltaX = Math.abs(c1.x-c2.x);

            if (deltaX < radiiSum) {
                var deltaY = Math.abs(c1.y-c2.y);

                if (deltaY < radiiSum) {
                    var distance = Math.sqrt(deltaX*deltaX+deltaY*deltaY);

                    if (distance < radiiSum) {
                        var separation = radiiSum - distance;
                        console.log(c1,c2,separation);
                    }
                }
            }
        }
    }

    k++;
}

Also, I would appreciate it if you explained a good algorithm (KD Tree?) in plain English :-/

Answer 1

For starters, your algorithm above will be greatly sped-up if you just skipped the SQRT call. That's the most well known simple optimization for comparing distances. You can also precompute the "squared radius" distance so you don't redundantly recompute it.

Also, there looks to be lots of other little bugs in some of your algorithms. Here's my take on how to fix it below.

Also, if you want to get rid of the O(N-Squared) algorithm, you can look at using a kd-tree. There's an upfront cost of building the KD-Tree but with the benefit of searching for nearest neighbors as much faster.

function Distance_Squared(c1, c2) {

    var deltaX = (c1.x - c2.x);
    var deltaY = (c1.y - c2.y);
    return (deltaX * deltaX + deltaY * deltaY);
}



// returns false if it's possible that the circles intersect.  Returns true if the bounding box test proves there is no chance for intersection
function TrivialRejectIntersection(c1, c2) {
    return ((c1.left >= c2.right) || (c2.right <= c1.left) || (c1.top >= c2.bottom) || (c2.bottom <= c1.top));
}

    var circle = function(x,y,radius) {
        return {
            x:x,
            y:y,
            radius:radius,

            // some helper properties
            radius_squared : (radius*radius), // precompute the "squared distance"
            left : (x-radius),
            right: (x+radius),
            top : (y - radius),
            bottom : (y+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;
    var len = points.length;
    var c1, c2;
    var distance_squared;
    var deltaX, deltaY;
    var min_distance;
    var seperation;

    for (var i = 0; i < len; i++) {
        for (var j = (i+1); j < len; j++) {
            c1 = points[i];
            c2 = points[j];

            // try for trivial rejections first. Jury is still out if this will help
            if (TrivialRejectIntesection(c1, c2)) {
                 continue;
            }



            //distance_squared is the actual distance between c1 and c2 'squared'
            distance_squared = Distance_Squared(c1, c2);

            // min_distance_squared is how much "squared distance" is required for these two circles to not intersect
            min_distance_squared = (c1.radius_squared + c2.radius_squared + (c1.radius*c2.radius*2)); // D**2 == deltaX*deltaX + deltaY*deltaY + 2*deltaX*deltaY

            // and so it follows
            if (distance_squared < min_distance_squared) {

                // intersection detected

                // now subtract actual distance from "min distance"
                seperation = c1.radius + c2.radius - Math.sqrt(distance_squared);
                Console.log(c1, c2, seperation);
            }
        }
    }