Sample non-overlapping circles from a uniform square - useful for initialization of multiple objects

nonoverlapping_random_circles.sh

#!/bin/bash

function draw_uniform {
  # generates a random float in [a b)
  # n.b.: a, b must be ints
  a=$1
  b=$2
  echo "$((a+RANDOM%(b-a))).$((RANDOM%999))"
}

function draw_nonoverlapping_circles {
  # Samples n non-overlapping circles from a uniform square with radius r
  n=$1
  r=$2
  w=$3
  h=$4

  # range of box, centered at the origin (int for draw_uniform)
  w1=$(echo "scale=0;$w / 2.0 * -1" | bc)
  w2=$(echo "scale=0;$w / 2.0" | bc)
  h1=$(echo "scale=0;$h / 2.0 * -1" | bc)
  h2=$(echo "scale=0;$h / 2.0" | bc)

  circles_x=()
  circles_y=()

  while [ ${#circles_x[@]} -lt $n ]; do
    # Sample a new circle
    x=$(draw_uniform $w1 $w2)
    y=$(draw_uniform $h1 $h2)

    # Compare where the new circle is w.r.t the old circles 
    overlapped=false
    for i in "${!circles_x[@]}"; do
      # calculate distance from center of new circle to this circle
      dx=$(echo "$x - ${circles_x[$i]}" | bc)
      dy=$(echo "$y - ${circles_y[$i]}" | bc)
      d=$(echo "scale=4;sqrt($dx * $dx + $dy * $dy)" | bc)
          
      # skip if it is too close to previously sampled circles
      if (( $(echo "$d < 2 * $r" | bc -l)  )); then
        overlapped=true
        break
      fi  
    done

    # If we've made it here, this circle does not overlap
    if [ "$overlapped" = false ]; then
      circles_x+=($x)
      circles_y+=($y)
    fi
  done
}

draw_nonoverlapping_circles 20 0.75 30 30
echo "${circles_x[@]}"
echo "${circles_y[@]}"