Getting random coordinates on a rectagle without overlapping

Question

I have a very big rectangle (100,000 x 100,000) and i am trying to position a lot of circles with different sizes randomly on it. My current solution is to store all previously used coordinate pairs in a map and then randomly generate a new pair and check if it exists in the map.

func randomCoords(xCoordinateMap map[int]bool, yCoordinateMap map[int]bool, radius int) (int, int) {
    x := rand.Intn((width-radius)-radius) + radius
    y := rand.Intn((height-radius)-radius) + radius

    for xCoordinateMap[x] && yCoordinateMap[y] {
        x = rand.Intn((width-radius)-radius) + radius
        y = rand.Intn((height-radius)-radius) + radius
    }

    xCoordinateMap[x] = true
    yCoordinateMap[y] = true

    return x, y
}

Because i'm generating a lot of coordinates, this method can get a little slow. Is there a better and most importantly faster way of getting random coordinates on a rectangle and maybe also a way to get them without the circles overlapping?

Answer 1

Figuring out circle overlap without storing the coordinates of previously added circles is quite tricky. The good thing is that after you've added a circle, it will cover an area with the given radius. Without using more targeted algorithms and continuing to rely on randomness you'll have check against the circles that you have and determine whether they overlap or not, that is done through basic Geometry formulas such as distance between centers, here's an example it's not heavily optimized but it should give you a starting point it does not check whether the circle's center + radius are within bounds of the canvas, it includes code to draw the result into an output file, in the example I'm using a small canvas but it could be adjusted to your rectangle size, the code should produce an image like this:

NOTE: The code was not written in an optimized way, there are many things that could be improved, for example using pointers instead of structs or removing looping when drawing or a better algorithm instead of using randomness to generate the X, Y and Radius for each circle.

package main

import (
    "fmt"
    "image"
    "image/color"
    "image/png"
    "math"
    "math/rand"
    "os"
)

const (
    width  int = 100
    height int = 200
)

type Circle struct {
    Center image.Point
    Radius int
}

func main() {
    circles := map[Circle]bool{}
    bounds := image.Rectangle{image.Point{0, 0}, image.Point{width, height}}
    for i := 0; i < 20; i++ {
        c := randomCircle(bounds)

        if overlaped(c, circles) {
            continue
        }
        circles[c] = true
    }

    fmt.Println(circles)

    file, err := os.Create("out.png")
    if err != nil {
        fmt.Println(err)
        os.Exit(1)
    }

    draw(width, height, circles, file)
    file.Close()
}

// Determines if the circle overlaps with any in the given
// circles collection.
func overlaped(c Circle, circles map[Circle]bool) bool {
    for circle := range circles {
        if overlap(circle, c) {
            return true
        }
    }

    return false
}

// Create a random circle within the
func randomCircle(rect image.Rectangle) Circle {
    radius := randomRadius(rect.Max.X, rect.Max.Y) - 1
    x := randDim(width-radius, 0)
    y := randDim(height-radius, 0)

    return Circle{
        Center: image.Point{X: x, Y: y},
        Radius: radius,
    }
}

func randomRadius(width, height int) int {
    if width < height {
        return rand.Intn(width / 2)
    } else {
        return rand.Intn(height / 2)
    }
}

func randDim(max, min int) int {
    return rand.Intn(max) + min
}

func distance(a, b image.Point) int {
    return int(math.Sqrt(math.Pow(float64(b.X-a.X), 2) + math.Pow(float64(b.Y-a.Y), 2)))
}

func overlap(a, b Circle) bool {
    return distance(a.Center, b.Center) < a.Radius+b.Radius
}

// Utility function to draw into a file object
func draw(width, height int, circles map[Circle]bool, file *os.File) error {
    img := image.NewRGBA(image.Rect(0, 0, width, height))

    // Looping is probably very inefficient, but I'm not that familiar with the draw package
    for circle := range circles {
        for a := 0; a < 360; a++ {
            var rads float64 = float64(a) * 0.017453
            x := float64(circle.Center.X) + float64(circle.Radius)*math.Cos(rads)
            y := float64(circle.Center.Y) + float64(circle.Radius)*math.Sin(rads)
            img.Set(int(x), int(y), color.RGBA{R: 255, G: 0, B: 0, A: 255})
        }
    }

    for x := 0; x < width; x++ {
        img.Set(int(x), 0, color.RGBA{R: 0, G: 0, B: 255, A: 255})
        img.Set(int(x), height-1, color.RGBA{R: 0, G: 0, B: 255, A: 255})
    }

    for y := 0; y < height; y++ {
        img.Set(width-1, y, color.RGBA{R: 0, G: 0, B: 255, A: 255})
        img.Set(0, y, color.RGBA{R: 0, G: 0, B: 255, A: 255})
    }

    return png.Encode(file, img)
}