在矩形内取随机坐标避免重叠

在宽广的矩形区域内放置不重叠的圆形时，随机生成坐标并逐一检查重叠的方式效率较低。本文提出了一种更有效的方法，它通过计算圆形的重叠区域来避免重叠。该方法利用几何公式确定圆心之间的距离，从而无需存储先前放置的圆形的坐标。该方法在生成随机坐标时仍然依赖于随机性，但它可以显著提高速度，尤其是在处理大量圆形时。

我有一个非常大的矩形（100,000 x 100,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
}

因为我生成了大量坐标，所以此方法可能会有点慢。是否有更好且最重要的是更快的方法来获取矩形上的随机坐标，并且也许还有一种方法可以在不使圆圈重叠的情况下获取它们？

解决方案

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

注意：代码不是以优化的方式编写的，有很多东西可以改进，例如使用指针而不是结构或在绘图时删除循环或更好的算法而不是使用随机性来生成 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)
}

今天关于《在矩形内取随机坐标避免重叠》的内容就介绍到这里了，是不是学起来一目了然！想要了解更多关于的内容请关注golang学习网公众号！