在无重叠的矩形上获取随机坐标

Question

我有一个非常大的矩形(100，000x100，000)，我试图在上面随机放置许多不同大小的圆。我目前的解决方案是将以前使用的所有坐标对存储在一个地图中，然后随机生成一个新的对，并检查它是否存在于地图中。

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
}

因为我生成了很多坐标，所以这个方法会变得有点慢。有没有一个更好，最重要的是更快的方法来得到矩形上的随机坐标，也许也有一个方法来得到它们而不是圆重叠？

Answer 1

在不存储以前添加的圆的坐标的情况下计算出圆重叠是相当棘手的。好的一点是，在你添加了一个圆之后，它将覆盖给定半径的区域。如果不使用更有针对性的算法并继续依赖于随机性，您将检查您所拥有的圆圈并确定它们是否重叠，这是通过基本的几何公式来完成的，比如中心之间的距离，这里有一个例子，它没有经过大量优化，但它应该给你一个起点，它没有检查圆的中心+半径是否在画布的范围内，它包括将结果绘制到输出文件中的代码，在这个例子中，我使用的是一个小画布，但它可以根据你的矩形大小进行调整，代码应该产生如下的图像：

注意：代码不是以优化的方式编写的，有许多地方可以改进，例如使用指针而不是结构，或者在绘制时删除循环，或者使用更好的算法而不是使用随机性来生成每个圆的X、Y和半径。

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)
}