algorithm - Optimizing a function to place circle in position which does not overlap other circles -

i have algorithm places circles in xy-plane. record programming in php @ moment, question in regards larger algorithm.

so here basic algorithmic code:

function create_circles($n) {   ($i = 0; $i < $n; $i++) {     $x = rand_x();     $y = rand_y();     $coord = array($x, $y);     $radius = rand_radius();     if ($i !== 0) {       ($m = 0; $m < $i; $m++) {         $distance = distance($coord, $position[$m]);         if ($radius + $radii[$m] > $distance) {           //repeat function again         } else {           continue;         }       }     }     //if function completes correctly     $radii[$i] = $radius;     $position[$i] = $coord;   } } 

this simplified code , did not include variable declarations or auxiliary functions. hope enough info.

as stands, function works, takes hours place 100 circles. looking way streamline function , cut down on execution time.

edit

ok, address comment , answer. first thank much. second provide little more information.

the environment dimensions infinite , important, random position generator favors positions closer origin (0, 0). therefore final result should include majority of circles located in center. distribution represented 1/x.

the circles plotted along spiral path (ie. y=atsint, x=atcos) random offset included.

i don't need complete randomness, simulation of randomness if improve performance, ie. consider narrowing random min, max in favor increasing speed.

you use strategy:

1. create random coordinates first , assume 0 radius each them
2. calculate each distance closest other point in set. upper limit radius can set given circle: max_radius
3. choose circle has highest max_radius among circles did not definitive radius in algorithm
4. generate random radius should stay below max_radius
5. check distances other points have new circle, , reduce max_radius if needed.
6. repeat step 3 until there no more circles without radius.

this process runs in o(n²). further optimised, found 100 circles result immediate:

<?php function rand_x() {     // use own code , random distribution here. mock.     return rand(10, 490);  } function rand_y() {     // use own code , random distribution here. mock.     return rand(10, 290); } function rand_radius($max) {     // use own code , random distribution here. mock.     // however: should not generate number higher parameter value!     return rand(0, min($max, 50)); } function distance($a, $b) {     return sqrt(pow(($a[0]-$b[0]),2) + pow(($a[1]-$b[1]),2)); }  function create_circles($n) {     $position = array();     // generate circles radius 0     ($i = 0; $i < $n; $i++) {         $circles[] = array(             "id" => $i,             "position" => array(rand_x(), rand_y()),             "radius" => 0,             "max_radius" => 1e100 // "infinity"         );     }     function &adjustradiitocircle(&$ref_circle, &$circles) {         $selected_circle = null;         foreach ($circles &$circle) {             if ($circle['radius'] == 0 , $ref_circle['id'] !== $circle['id']) { // not yet assigned radius                 $distance = distance($circle['position'], $ref_circle['position']);                 $circle['max_radius'] = min($circle['max_radius'], $distance - $ref_circle['radius']);                 if ($selected_circle == null or $circle['max_radius'] > $selected_circle['max_radius']) {                     $selected_circle = &$circle;                 }             }         }         return $selected_circle;     }     // calculate maxium radius each circle can have     // , remember 1 highest value     $selected_circle = null;     foreach ($circles $circle) {         // set or adapt max_distance circles in relation circle         $selected_circle = &adjustradiitocircle($circle, $circles);         // nb: ignore return value, except last iteration     }      // choose n times circle give random radius     foreach ($circles $ignore){         // random radius selected circle.         // rand_radius function gets argument, can make sure not generate         // greater that.               $selected_circle['radius'] = rand_radius($selected_circle['max_radius']);         $selected_circle = &adjustradiitocircle($selected_circle, $circles);     };     return $circles; }     $circles = create_circles(100);  ?> <canvas width="500" height="300" style="border: 1px solid"></canvas> <script> var circles = <?=json_encode($circles)?>; var canvas = document.queryselector('canvas'); var ctx = canvas.getcontext('2d');  (var circle of circles) {     console.log(circle.position[0],circle.position[1],circle.radius);     ctx.beginpath();     ctx.arc(circle.position[0],circle.position[1], circle.radius, 0, 2 * math.pi, false);     ctx.fillstyle = 'yellow';     ctx.fill();     ctx.linewidth = 2;     ctx.stroke(); } </script> 

i added javascript in php, draws circles on canvas. here example of script generated, show result:

var circles = [{"id":0,"position":[318,82],"radius":3,"max_radius":51.6623654124},{"id":1,"position":[397,52],"radius":10,"max_radius":15.8113883008},{"id":2,"position":[150,113],"radius":21,"max_radius":27.7308492477},{"id":3,"position":[296,194],"radius":1,"max_radius":15.0512483795},{"id":4,"position":[251,194],"radius":3,"max_radius":20.8086520467},{"id":5,"position":[97,253],"radius":3,"max_radius":3.49285568454},{"id":6,"position":[484,16],"radius":25,"max_radius":73},{"id":7,"position":[76,141],"radius":16,"max_radius":16.1245154966},{"id":8,"position":[133,195],"radius":2,"max_radius":6.39607805437},{"id":9,"position":[361,287],"radius":1,"max_radius":34.8281495345},{"id":10,"position":[57,282],"radius":19,"max_radius":41.4366987102},{"id":11,"position":[252,270],"radius":2,"max_radius":12.0830459736},{"id":12,"position":[67,73],"radius":10,"max_radius":19.2353840617},{"id":13,"position":[356,117],"radius":5,"max_radius":10.9317121995},{"id":14,"position":[152,238],"radius":11,"max_radius":21.3775583264},{"id":15,"position":[394,273],"radius":14,"max_radius":17.0293863659},{"id":16,"position":[43,180],"radius":2,"max_radius":12.0830459736},{"id":17,"position":[53,111],"radius":14,"max_radius":19.4164878389},{"id":18,"position":[478,202],"radius":18,"max_radius":18.3847763109},{"id":19,"position":[18,143],"radius":10,"max_radius":11.0453610172},{"id":20,"position":[174,66],"radius":3,"max_radius":3.60555127546},{"id":21,"position":[175,101],"radius":2,"max_radius":6.73084924772},{"id":22,"position":[117,145],"radius":14,"max_radius":19.2353840617},{"id":23,"position":[391,144],"radius":11,"max_radius":12.8617393793},{"id":24,"position":[78,157],"radius":0,"max_radius":0.124515496597},{"id":25,"position":[233,77],"radius":7,"max_radius":8.94427191},{"id":26,"position":[247,281],"radius":1,"max_radius":3.04536101719},{"id":27,"position":[90,182],"radius":22,"max_radius":23.3452350599},{"id":28,"position":[102,259],"radius":1,"max_radius":7.46424919657},{"id":29,"position":[489,147],"radius":2,"max_radius":15.2626765016},{"id":30,"position":[346,234],"radius":4,"max_radius":15.5600808897},{"id":31,"position":[214,225],"radius":6,"max_radius":27.6586333719},{"id":32,"position":[203,154],"radius":0,"max_radius":1.76305461424},{"id":33,"position":[72,115],"radius":1,"max_radius":5.41648783895},{"id":34,"position":[106,51],"radius":2,"max_radius":6.80441152621},{"id":35,"position":[419,162],"radius":9,"max_radius":12.0415945788},{"id":36,"position":[177,64],"radius":0,"max_radius":0.605551275464},{"id":37,"position":[428,170],"radius":3,"max_radius":3.04159457879},{"id":38,"position":[335,196],"radius":24,"max_radius":33.5261092285},{"id":39,"position":[34,239],"radius":10,"max_radius":17},{"id":40,"position":[100,154],"radius":1,"max_radius":5.23538406167},{"id":41,"position":[38,201],"radius":1,"max_radius":6.76972864801},{"id":42,"position":[241,73],"radius":0,"max_radius":1.94427191},{"id":43,"position":[153,199],"radius":14,"max_radius":20.3960780544},{"id":44,"position":[64,92],"radius":4,"max_radius":7.9544984001},{"id":45,"position":[88,238],"radius":14,"max_radius":17.4928556845},{"id":46,"position":[54,175],"radius":7,"max_radius":10.0830459736},{"id":47,"position":[289,148],"radius":7,"max_radius":39.9624824054},{"id":48,"position":[60,210],"radius":17,"max_radius":23.769728648},{"id":49,"position":[428,95],"radius":2,"max_radius":13.0208242989},{"id":50,"position":[424,213],"radius":10,"max_radius":17.88854382},{"id":51,"position":[418,68],"radius":9,"max_radius":26.4007575649},{"id":52,"position":[451,211],"radius":8,"max_radius":23.6008474424},{"id":53,"position":[385,176],"radius":6,"max_radius":29.8516480713},{"id":54,"position":[193,243],"radius":17,"max_radius":21.6586333719},{"id":55,"position":[208,170],"radius":15,"max_radius":16.7630546142},{"id":56,"position":[176,142],"radius":4,"max_radius":5.09901951359},{"id":57,"position":[131,242],"radius":1,"max_radius":10.3775583264},{"id":58,"position":[345,164],"radius":6,"max_radius":9.52610922848},{"id":59,"position":[251,238],"radius":4,"max_radius":9.20459156783},{"id":60,"position":[416,197],"radius":5,"max_radius":7.88854382},{"id":61,"position":[310,273],"radius":5,"max_radius":6.89173349139},{"id":62,"position":[132,68],"radius":11,"max_radius":23.7234787586},{"id":63,"position":[217,110],"radius":20,"max_radius":22.5610283454},{"id":64,"position":[452,94],"radius":11,"max_radius":22.3882694814},{"id":65,"position":[329,229],"radius":1,"max_radius":9.5410196625},{"id":66,"position":[21,154],"radius":0,"max_radius":1.40175425099},{"id":67,"position":[486,275],"radius":17,"max_radius":43.1856457634},{"id":68,"position":[121,226],"radius":2,"max_radius":18.8679622641},{"id":69,"position":[268,182],"radius":5,"max_radius":17.8086520467},{"id":70,"position":[300,276],"radius":3,"max_radius":5.44009029334},{"id":71,"position":[98,276],"radius":10,"max_radius":17.4642491966},{"id":72,"position":[212,132],"radius":1,"max_radius":2.56102834536},{"id":73,"position":[384,43],"radius":1,"max_radius":5.81138830084},{"id":74,"position":[484,89],"radius":10,"max_radius":32.3882694814},{"id":75,"position":[457,243],"radius":15,"max_radius":22.2036033112},{"id":76,"position":[465,166],"radius":4,"max_radius":21.0950231097},{"id":77,"position":[379,66],"radius":1,"max_radius":2},{"id":78,"position":[377,66],"radius":0,"max_radius":1},{"id":79,"position":[279,201],"radius":8,"max_radius":12.4499705536},{"id":80,"position":[251,73],"radius":1,"max_radius":3.40175425099},{"id":81,"position":[232,158],"radius":8,"max_radius":11.83281573},{"id":82,"position":[365,137],"radius":11,"max_radius":12.319604517},{"id":83,"position":[236,282],"radius":8,"max_radius":11.0453610172},{"id":84,"position":[118,12],"radius":34,"max_radius":40.8044115262},{"id":85,"position":[290,242],"radius":30,"max_radius":35.4400902933},{"id":86,"position":[470,225],"radius":1,"max_radius":6.35159132377},{"id":87,"position":[384,116],"radius":16,"max_radius":28.0178514522},{"id":88,"position":[107,166],"radius":0,"max_radius":1.34523505986},{"id":89,"position":[248,62],"radius":8,"max_radius":11.401754251},{"id":90,"position":[413,130],"radius":1,"max_radius":16.2024843762},{"id":91,"position":[19,231],"radius":5,"max_radius":7},{"id":92,"position":[482,231],"radius":5,"max_radius":11.2745623366},{"id":93,"position":[485,219],"radius":0,"max_radius":0.38477631085},{"id":94,"position":[486,164],"radius":2,"max_radius":17.0950231097},{"id":95,"position":[216,148],"radius":4,"max_radius":8.40939982144},{"id":96,"position":[383,260],"radius":3,"max_radius":3.02938636593},{"id":97,"position":[19,154],"radius":0,"max_radius":1.04536101719},{"id":98,"position":[175,147],"radius":0,"max_radius":1.09901951359},{"id":99,"position":[242,170],"radius":1,"max_radius":15.6204993518}];  var canvas = document.queryselector('canvas');  var ctx = canvas.getcontext('2d');    (var circle of circles) {      ctx.beginpath();      ctx.arc(circle.position[0],circle.position[1], circle.radius, 0, 2 * math.pi, false);      ctx.fillstyle = 'yellow';      ctx.fill();      ctx.linewidth = 2;      ctx.stroke();  }

<canvas width="500" height="300" style="border: 1px solid"></canvas>