Databases
StackOverflow2013
Postsdbo
POCircle Separation Distance - Nearest Neighbor Problem
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POCircle Separation Distance - Nearest Neighbor Problem
    text
    copied!<p>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.</p> <p>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.</p> <p>Here is a (slow) implementation I currently have in JavaScript:</p> <pre><code>// 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 &lt; len; i++) { for (var j = k; j &lt; 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 &lt; radiiSum) { var deltaY = Math.abs(c1.y-c2.y); if (deltaY &lt; radiiSum) { var distance = Math.sqrt(deltaX*deltaX+deltaY*deltaY); if (distance &lt; radiiSum) { var separation = radiiSum - distance; console.log(c1,c2,separation); } } } } } k++; } </code></pre> <p>Also, I would appreciate it if you explained a good algorithm (KD Tree?) in plain English :-/</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload