Circle separation distance is the closest adjacent problem.

Question

I have a set of circles with given locations and radii on a two-dimensional plane. I want to determine for each circle if it intersects with any other circle and the distance that is needed to separate the two. In 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.

Circles are usually grouped into groups, and they will have the same (but different) radii. The approximate maximum for the number of circles is about 200. The algorithm does not have to be accurate, but it should be close.

Here is the (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 if you could explain a good algorithm (KD Tree?) In plain English: - /

Answer 1

For starters, your algorithm above will be significantly accelerated if you just skip the SQRT call. This is the most famous simple optimization for comparing distances. You can also pre-comprehend the "square of radius" distance so as not to unnecessarily recalculate it.

In addition, some of your algorithms have many other errors. Here I take it upon myself how to fix it below.

In addition, if you want to get rid of the O (N-Squared) algorithm, you can look at kd-tree . There is the initial cost of building a KD-Tree, but with the benefit of finding nearby neighbors 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 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); } } } 

Answer 2

This article was inactive for a long time, but I ran into this problem and solved this problem quite well, so I will publish it so that others do not have to do the same head scratches.

You can consider the immediate problem of the nearest environment as searching for the nearest neighbor of a 3d point in the kd or octree tree. Define the distance between the two circles A and B as

 D(A,B) = sqrt( (xA - xB)^2 + (yA - yB)^2 ) - rA - rB 

This is a negative value if the circles overlap. For this discussion, I'll take an octet, but the kd tree with k = 3 is similar.

Save the triple (x, y, r) in an octet for each circle.

To find the closest neighbor to the target circle T, use the standard algorithm:

 def search(node, T, nst) if node is a leaf update nst with node (x,y,r) nearest to T else for each cuboid C subdividing node (there are 8 of them) if C contains any point nearer to T than nst search(C, T, nst) end end 

Here nst is a link to the closest circle to T found so far. It is initially null.

It's a little tricky to determine if C contains any point nearer to T than nst . To do this, it is enough to consider a single point (x, y, r) inside C, which is Euclidean, closest to T in x and y and has the maximum value of the range r contained in the cuboid. In other words, a cuboid is a set of circles with centers located above a rectangular area in x and y and with a range of radii. The point you want to check is a point representing a circle with the center closest to T and with the largest radius.

Note that the radius T does not play any role in the algorithm. You only agree with how far the center of T. is located inside any other circle (I would like it to be as obvious in the beginning as it seems now ...)