Skip to content

Instantly share code, notes, and snippets.

@plusk01

plusk01/nonoverlapping_random_circles.sh

Last active January 3, 2020 18:54
Download ZIP

Revisions

  1. plusk01 revised this gist Jan 3, 2020. 1 changed file with 35 additions and 25 deletions.
    60 changes: 35 additions & 25 deletions nonoverlapping_random_circles.sh
    View file
    Original file line number Diff line number Diff line change
    @@ -2,46 +2,56 @@

    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 sample_circle {
    x = draw_uniform $1 $2
    y = draw_uniform $3 $4
    }
    function draw_nonoverlapping_circles {
    # Samples n non-overlapping circles from a uniform square with radius r
    n=$1
    r=$2
    w=$3
    h=$4

    n=20
    r=0.75
    w=30
    h=30
    # 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=()
    circles_x=()
    circles_y=()

    while [ ${#circles_x[@]} -lt $n ]; do
    while [ ${#circles_x[@]} -lt $n ]; do
    # Sample a new circle
    x=$(draw_uniform "-$w" $w)
    y=$(draw_uniform "-$h" $h)
    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
    continue
    fi
    # 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
    circles_x+=($x)
    circles_y+=($y)
    done
    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[@]}"
  2. plusk01 created this gist Jan 3, 2020.
    47 changes: 47 additions & 0 deletions nonoverlapping_random_circles.sh
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,47 @@
    #!/bin/bash

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

    function sample_circle {
    x = draw_uniform $1 $2
    y = draw_uniform $3 $4
    }

    n=20
    r=0.75
    w=30
    h=30

    circles_x=()
    circles_y=()

    while [ ${#circles_x[@]} -lt $n ]; do
    # Sample a new circle
    x=$(draw_uniform "-$w" $w)
    y=$(draw_uniform "-$h" $h)

    # Compare where the new circle is w.r.t the old circles
    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
    continue
    fi
    done

    # If we've made it here, this circle does not overlap
    circles_x+=($x)
    circles_y+=($y)
    done

    echo "${circles_x[@]}"
    echo "${circles_y[@]}"