go - 在不重叠的情况下在矩形上获取随机坐标

Question

我有一个非常大的矩形 (100,000 x 100,000)，我试图在其上随机放置许多不同大小的圆圈。我目前的解决方案是将所有以前使用过的坐标对存储在一个 map 中，然后随机生成一个新的坐标对并检查它是否存在于 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
}

因为我要生成很多坐标，所以这种方法可能会有点慢。有没有一种更好、最重要的是更快的方法来获取矩形上的随机坐标，也许还有一种方法可以在不重叠圆圈的情况下获取它们？

Answer 1

在不存储先前添加的圆的坐标的情况下找出圆重叠是非常棘手的。好处是，在您添加一个圆之后，它将覆盖一个具有给定半径的区域。在不使用更有针对性的算法并继续依赖随机性的情况下，您将检查您拥有的圆圈并确定它们是否重叠，这是通过基本的几何公式​​(例如中心之间的距离)完成的，这是一个没有进行大量优化的示例但它应该给你一个起点它不检查圆的中心+半径是否在 Canvas 的范围内，它包含将结果绘制到输出文件中的代码，在我使用的示例中我使用的是小 Canvas 但它可以调整为您的矩形大小，代码应生成如下图像:

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