::BASIC_32_circle_packing

📝 Rust Code

use nannou::prelude::*;
use rand::prelude::*;

const NUM_CANDIDATES: usize = 2000;
const R_MIN: f32 = 5.0;
const R_MAX: f32 = 120.0;
const SEED: u64 = 42;
const BOX: f32 = 540.0;

#[derive(Clone, Copy, Debug)]
struct Circle {
    position: Vec2,
    radius: f32,
}

struct Model {
    circles: Vec<Circle>,
}

fn main() {
    nannou::app(model).run();
}

fn model(app: &App) -> Model {
    app.new_window()
        .size(1080, 1080)
        .view(view)
        .build()
        .unwrap();

    let polygon = vec![
        Vec2::new(-BOX, -BOX),
        Vec2::new(BOX, -BOX),
        Vec2::new(BOX, BOX),
        Vec2::new(-BOX, BOX),
    ];

    let circles = run_circle_packing(&polygon);

    Model { circles }
}

fn view(app: &App, model: &Model, frame: Frame) {
    let draw = app.draw();
    draw.background().color(rgb(0.05, 0.05, 0.05));

    for circle in &model.circles {
        // 크기에 따라 hue, val 값 매핑: 작은 원 ~ 큰 원
        let hue = map_range(circle.radius, R_MIN, R_MAX, 0.5, 0.6);
        let val = map_range(circle.radius, R_MIN, R_MAX, 0.1, 0.9);
        draw.ellipse()
            .xy(circle.position)
            .radius(circle.radius)
            .color(hsv(hue, 0.8, val));
    }

    draw.to_frame(app, &frame).unwrap();
}

fn run_circle_packing(polygon: &[Vec2]) -> Vec<Circle> {
    let candidates = sample_candidates(polygon, NUM_CANDIDATES);
    greedy_pack(polygon, &candidates, R_MIN, R_MAX)
}

fn point_in_polygon(pt: Vec2, poly: &[Vec2]) -> bool {
    let mut inside = false;
    let n = poly.len();
    for i in 0..n {
        let j = (i + 1) % n;
        let xi = poly[i].x;
        let yi = poly[i].y;
        let xj = poly[j].x;
        let yj = poly[j].y;
        if (yi > pt.y) != (yj > pt.y) && pt.x < (xj - xi) * (pt.y - yi) / (yj - yi) + xi {
            inside = !inside;
        }
    }
    inside
}

fn distance_to_edge(pt: Vec2, poly: &[Vec2]) -> f32 {
    let mut min_dist = f32::INFINITY;
    let n = poly.len();
    for i in 0..n {
        let a = poly[i];
        let b = poly[(i + 1) % n];
        let pa = pt - a;
        let ba = b - a;
        let t = (pa.dot(ba) / ba.length_squared()).clamp(0.0, 1.0);
        let dist = (pt - (a + ba * t)).length();
        min_dist = min_dist.min(dist);
    }
    min_dist
}

fn sample_candidates(poly: &[Vec2], num: usize) -> Vec<Vec2> {
    let mut rng = StdRng::seed_from_u64(SEED);
    let min_x = poly.iter().map(|v| v.x).fold(f32::INFINITY, f32::min);
    let max_x = poly.iter().map(|v| v.x).fold(f32::NEG_INFINITY, f32::max);
    let min_y = poly.iter().map(|v| v.y).fold(f32::INFINITY, f32::min);
    let max_y = poly.iter().map(|v| v.y).fold(f32::NEG_INFINITY, f32::max);

    let mut candidates = Vec::new();
    while candidates.len() < num {
        let pt = vec2(rng.gen_range(min_x..max_x), rng.gen_range(min_y..max_y));
        if point_in_polygon(pt, poly) {
            candidates.push(pt);
        }
    }
    candidates
}

fn greedy_pack(poly: &[Vec2], candidates: &[Vec2], r_min: f32, r_max: f32) -> Vec<Circle> {
    let mut sorted: Vec<_> = candidates
        .iter()
        .map(|&p| (p, distance_to_edge(p, poly).min(r_max)))
        .filter(|(_, r)| *r >= r_min)
        .collect();
    sorted.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap());

    let mut circles = Vec::new();
    for (pos, max_r) in sorted {
        let min_dist = circles
            .iter()
            .map(|c: &Circle| (pos - c.position).length() - c.radius)
            .fold(f32::INFINITY, f32::min);
        
        let radius = max_r.min(min_dist);
        if radius >= r_min {
            circles.push(Circle { position: pos, radius });
        }
    }
    circles
}