Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>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.</p> <p>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.</p> <p>Also, if you want to get rid of the O(N-Squared) algorithm, you can look at using a <a href="http://en.wikipedia.org/wiki/Kd-tree" rel="nofollow">kd-tree</a>. There's an upfront cost of building the KD-Tree but with the benefit of searching for nearest neighbors as much faster.</p> <pre><code>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 &gt;= c2.right) || (c2.right &lt;= c1.left) || (c1.top &gt;= c2.bottom) || (c2.bottom &lt;= 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 &lt; len; i++) { for (var j = (i+1); j &lt; 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 &lt; 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); } } } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POCircle Separation Distance - Nearest Neighbor Problem
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USselbie
    1. USselbie
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COMade a few edits along the way. Might be an optimization to prevent a redundant calculation or two.
      singulars
      1. PO
      1. USselbie
    2. COnot bad, but what if the intersection between the two circles was not exactly from left, right, top or down. If the the intersection happened in any of the corners this will be useless !!
      singulars
      1. PO
      1. USSeem
    3. CO@Seem - I didn't know circles had corners. Thanks!
      singulars
      1. PO
      1. USselbie
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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