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

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
}

因为我正在生成很多坐标，所以这种方法可能会有点慢。是否有更好的、更快的方法来获取矩形上的随机坐标，并且可能还有一种不重叠的圆形坐标的方法？

- Milan

---

泊松盘采样，也许是吗？https://www.jasondavies.com/poisson-disc/ - Severin Pappadeux

参见：https://observablehq.com/@mbostock/best-candidate-circles - Peter O.

Answer 1

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

注意：代码并没有以最佳方式编写，有很多可以改进的地方，例如使用指针而不是结构体，或者在绘制时去除循环，或者使用更好的算法来生成每个圆的X、Y和半径，而不是使用随机性。保留HTML标签。

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

- Tristian