29 static std::vector<Vector2f>
generate(
float width,
float height,
float r,
30 int k = 30, uint64_t seed = 42) {
31 const float cellSize = r / std::sqrt(2.0f);
32 const int gridW = int(width / cellSize) + 1;
33 const int gridH = int(height / cellSize) + 1;
35 std::vector<int> grid(gridW * gridH, -1);
36 std::vector<Vector2f> points;
37 std::vector<int> active;
39 std::mt19937 rng(seed);
40 std::uniform_real_distribution<float> dx(0, width);
41 std::uniform_real_distribution<float> dy(0, height);
42 std::uniform_real_distribution<float> angle(0, 2 * M_PI);
43 std::uniform_real_distribution<float> radius(r, 2 * r);
45 auto insert = [&](
const Vector2f& p) {
47 int gx = int(p.x / cellSize), gy = int(p.y / cellSize);
48 grid[gy * gridW + gx] = int(points.size()) - 1;
49 active.push_back(
int(points.size()) - 1);
52 insert({dx(rng), dy(rng)});
54 while (!active.empty()) {
55 int idx = active[rng() % active.size()];
57 for (
int i = 0; i < k; ++i) {
58 float a = angle(rng), rad = radius(rng);
59 Vector2f cand{ points[idx].x + rad * std::cos(a),
60 points[idx].y + rad * std::sin(a) };
61 if (cand.x < 0 || cand.y < 0 || cand.x >= width || cand.y >= height)
continue;
62 if (isValid(cand, r, grid, cellSize, gridW, gridH, points)) {
69 active.erase(std::remove(active.begin(), active.end(), idx), active.end());