*Randomly generate 2D graphs for toy visualizations.*

Random graphs are a vast research area of graph theory, but I just need something simple for a few visualizations. I want to make graphs that represent a rail network between cities, such that neighbouring cities are somewhat connected, and there aren't any long edges that jump halfway across the graph.

## Points

The cities or nodes of the graph are randomly generated 2D points in `[0,1]`

. But placing the cities purely at random results in
clusters which make it difficult to distinguish individual nodes.

type Point struct { X, Y float64 } type Edge struct { U, V Point }

I can prevent this by finding the closest existing node before adding another, and rejecting the new point if it would be too close. This is an O(n²) algorithm which is fine for my small n (but there are interesting possible optimizations). There's a danger this loop won't terminate, so I added a hard limit.

// closest returns the distance from p to the closest point in ps. func closest(p Point, ps []Point) float64 { min := 2.0 for _, q := range ps { if d := dist2(p, q); d < min { min = d } } return min } // dist2 returns the Euclidean distance squared between two points. func dist2(a, b Point) float64 { x := a.X - b.X y := a.Y - b.Y return x*x + y*y } // points returns n nodes so that they're no less that minDist2 apart. func points(n int, minDist2 float64) []Point { ps := []Point{ // top-left and bottom-right {0, 0}, {1, 1}, } // prevent infinite loop for i := 0; len(ps) < numPoints && i < 1e4; i++ { p := Point{rand.Float64(), rand.Float64()} if closest(p, ps) < minDist2 { continue } ps = append(ps, p) } return ps }