title: algorithm to randomly & efficiently place 100 circles without any overlap?
body: <p>I am trying to write a script to place 100 circles of varying sizes onto a stage. I've outlined the concise requirements below.</p>
  
  <p><strong>Given the following:</strong></p>
  
  <pre><code>var stage;       // contains a "width" and "height" property.
  var circle;      // the circle class. contains x, y, radius &amp; a unique id property.
  var circleArray; // contains 100 circle instances
  </code></pre>
  
  <p><strong>requirements:</strong></p>
  
  <ul>
  <li>write a function to place 100 circles of varying radius onto the stage.</li>
  <li>placements must be random but evenly distributed (no clumping).</li>
  <li>placement must be performant - this will be executing on a mobile web browser.</li>
  <li>circles must not intersect/overlap other circles.</li>
  <li><code>circle.x &gt;= 0</code> must be true.</li>
  <li><code>circle.y &gt;= 0 &amp;&amp; circle.y &lt;= stage.height</code> must be true.</li>
  <li>circles may have any of the following radius sizes (assigned at creation):
  
  <ul>
  <li>150</li>
  <li>120</li>
  <li>90</li>
  <li>80</li>
  <li>65</li>
  </ul></li>
  </ul>
  
  <hr>
  
  <p><strong>My current attempt is a brute-force method, which does not operate efficiently. If I attempt to insert any more than ~10 circles, the browser hangs. Below is my current implementation, which I am completely OK with throwing away in favor of a more performant / better one.</strong></p>
  
  <p><strong>Here is a live demo (NOTE: there is no actual drawing code, just the logic, but it will still lock up the browser so be warned!!) <a href="http://jsbin.com/muhiziduxu/2/edit?js,console" rel="nofollow">http://jsbin.com/muhiziduxu/2/edit?js,console</a></strong></p>
  
  <pre><code>function adjustForOverlap (circleArray) {
    // a reference to the circle that is invoking this function.
    var _this = this;
  
    // remove this circle from the array we are iterating over.
    var arr = circleArray.filter(function (circle){
      return circle.id !== _this.id;
    });
  
    // while repeat == true, the circle may be overlapping something.
    var repeat = true;
    while(repeat) {
      var hasOverlap = false;
      for (var i=0; i&lt;arr.length; i++) {
        var other = arr[i];
        var dx = _self.x - other.x;
        var dy = _self.y - other.y;
        var rr = _self.radius + other.radius;
        if (dx * dx + dy * dy &lt; rr * rr) {
          // if here, then an overlap was detected.
          hit = true;
          break;
        }
      }
      // if hit is false, the circle didn't overlap anything, so break.
      if (hit === false) {
        repeat = false;
        break;
      } else {
        // an overlap was detected, so randomize position.
        _self.x = Math.random() * (stage.width*2);
        _self.y = Math.random() * stage.height;
      }
    }
  }
  </code></pre>