🔮 :: Circle Packing 2D - Greedy Algorithm

Cargo.toml 의존성 추가:
[dependencies]
nannou = "0.19"
rand = "0.8"

📝 Rust Code

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

// 사용자 설정 상수
const NUM_CANDIDATES: usize = 2000;  // 후보 중심점 샘플 수
const R_MIN: f32 = 2.0;              // 최소 원 반지름
const R_MAX: f32 = 50.0;             // 최대 원 반지름
const RELAX_ITERS: usize = 30;       // 위치 최적화 반복 횟수
const RELAX_STEP: f32 = 0.5;         // 최적화 시 이동 스텝 크기
const SEED: u64 = 42;                // 랜덤 시드
const EDGE_EPS: f32 = 1e-6;          // 경계선 판정 허용 오차

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

struct Model {
    circles: Vec<Circle>,
    polygon: Vec<Vec2>,
    _window: window::Id,
}

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

fn model(app: &App) -> Model {
    let _window = app.new_window()
        .size(1080, 1080)
        .view(view)
        .build()
        .unwrap();
    
    // 기본 다각형 정의 (사각형)
    let polygon = vec![
        Vec2::new(-540.0, -540.0),
        Vec2::new(540.0, -540.0),
        Vec2::new(540.0, 540.0),
        Vec2::new(-540.0, 540.0),
    ];
    
    // Circle packing 실행
    let circles = run_circle_packing(&polygon);
    
    Model {
        circles,
        polygon,
        _window,
    }
}

fn update(_app: &App, _model: &mut Model, _update: Update) {
    // 업데이트 로직 (필요시 추가)
}

fn view(app: &App, model: &Model, frame: Frame) {
    let draw = app.draw();
    
    // 배경을 검은색으로 설정
    draw.background().color(BLACK);
    
    // 다각형 경계선 그리기 (옵션)
    for i in 0..model.polygon.len() {
        let start = model.polygon[i];
        let end = model.polygon[(i + 1) % model.polygon.len()];
        draw.line()
            .start(start)
            .end(end)
            .color(GRAY)
            .stroke_weight(1.0);
    }
    
    // 원들 그리기 (흰색)
    for circle in &model.circles {
        draw.ellipse()
            .xy(circle.position)
            .radius(circle.radius)
            // .color(WHITE)
            .color(hsv(random_range(0.0, 1.0), 0.5, 0.9))
            .stroke_weight(0.0);
    }
    
    draw.to_frame(app, &frame).unwrap();
}

fn run_circle_packing(polygon: &[Vec2]) -> Vec<Circle> {
    println!("샘플 후보 생성 중...");
    let candidates = sample_candidates(polygon, NUM_CANDIDATES);
    println!("후보 수: {}", candidates.len());
    
    println!("그리디 패킹 수행 중...");
    let mut circles = greedy_pack(polygon, &candidates, R_MIN, R_MAX);
    println!("초기 배치된 원 수: {}", circles.len());
    
    if RELAX_ITERS > 0 && !circles.is_empty() {
        println!("로컬 릴랙세이션 수행 중...");
        circles = relax_circles(polygon, circles, RELAX_ITERS, RELAX_STEP);
    }
    
    println!("완료. 생성된 원 수: {}", circles.len());
    circles
}

// 점에서 선분까지의 최단거리 계산 (2D)
fn dist_point_segment_2d(p: Vec2, a: Vec2, b: Vec2) -> f32 {
    let pa = p - a;
    let ba = b - a;
    let ba_len_squared = ba.length_squared();
    
    if ba_len_squared == 0.0 {
        return (p - a).length();
    }
    
    let t = (pa.dot(ba) / ba_len_squared).clamp(0.0, 1.0);
    let proj = a + ba * t;
    (p - proj).length()
}

// 점이 다각형 내부에 있는지 판단 (ray casting + edge check)
fn point_in_poly_2d(pt: Vec2, poly_verts: &[Vec2]) -> bool {
    let n = poly_verts.len();
    if n < 3 {
        return false;
    }
    
    // 1) 경계선 체크
    for i in 0..n {
        let a = poly_verts[i];
        let b = poly_verts[(i + 1) % n];
        if dist_point_segment_2d(pt, a, b) <= EDGE_EPS {
            return true;
        }
    }
    
    // 2) Ray casting 알고리즘
    let mut inside = false;
    let x = pt.x;
    let y = pt.y;
    
    for i in 0..n {
        let xi = poly_verts[i].x;
        let yi = poly_verts[i].y;
        let xj = poly_verts[(i + 1) % n].x;
        let yj = poly_verts[(i + 1) % n].y;
        
        if (yi > y) != (yj > y) {
            let x_int = xi + (y - yi) * (xj - xi) / (yj - yi);
            if x < x_int {
                inside = !inside;
            }
        }
    }
    
    inside
}

// 점에서 다각형 경계선까지의 최단거리
fn distance_to_boundary(p: Vec2, poly_verts: &[Vec2]) -> f32 {
    let mut min_dist = f32::INFINITY;
    let n = poly_verts.len();
    
    for i in 0..n {
        let a = poly_verts[i];
        let b = poly_verts[(i + 1) % n];
        let d = dist_point_segment_2d(p, a, b);
        if d < min_dist {
            min_dist = d;
        }
    }
    
    min_dist
}

// 점에서 기존 원들까지의 최소 여유거리
fn min_clearance_to_circles(p: Vec2, circles: &[Circle]) -> f32 {
    if circles.is_empty() {
        return f32::INFINITY;
    }
    
    let mut min_clear = f32::INFINITY;
    for circle in circles {
        let d = (p - circle.position).length() - circle.radius;
        if d < min_clear {
            min_clear = d;
        }
    }
    
    min_clear
}

// 다각형 내부에서 무작위 후보점 생성
fn sample_candidates(poly_verts: &[Vec2], num_candidates: usize) -> Vec<Vec2> {
    let mut rng = StdRng::seed_from_u64(SEED);
    
    // AABB 계산
    let xs: Vec<f32> = poly_verts.iter().map(|v| v.x).collect();
    let ys: Vec<f32> = poly_verts.iter().map(|v| v.y).collect();
    let min_x = xs.iter().fold(f32::INFINITY, |a, &b| a.min(b));
    let max_x = xs.iter().fold(f32::NEG_INFINITY, |a, &b| a.max(b));
    let min_y = ys.iter().fold(f32::INFINITY, |a, &b| a.min(b));
    let max_y = ys.iter().fold(f32::NEG_INFINITY, |a, &b| a.max(b));
    
    let mut candidates = Vec::new();
    let mut tries = 0;
    let max_tries = num_candidates * 20;
    
    while candidates.len() < num_candidates && tries < max_tries {
        let x = rng.gen_range(min_x..max_x);
        let y = rng.gen_range(min_y..max_y);
        let pt = Vec2::new(x, y);
        
        if point_in_poly_2d(pt, poly_verts) {
            candidates.push(pt);
        }
        tries += 1;
    }
    
    candidates
}

// 그리디 패킹 알고리즘
fn greedy_pack(poly_verts: &[Vec2], candidates: &[Vec2], r_min: f32, r_max: f32) -> Vec<Circle> {
    // 후보점들을 가능한 반지름 기준으로 정렬
    let mut cand_info: Vec<(Vec2, f32)> = candidates.iter()
        .map(|&p| {
            let r_bound = distance_to_boundary(p, poly_verts).min(r_max);
            (p, r_bound)
        })
        .filter(|(_, r_bound)| *r_bound >= r_min)
        .collect();
    
    // 반지름 내림차순 정렬
    cand_info.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap());
    
    let mut circles = Vec::new();
    
    for (p, r_bound) in cand_info {
        if circles.is_empty() {
            circles.push(Circle {
                position: p,
                radius: r_bound,
            });
            continue;
        }
        
        let min_clear = min_clearance_to_circles(p, &circles);
        let allowed = r_bound.min(min_clear);
        
        if allowed >= r_min {
            circles.push(Circle {
                position: p,
                radius: allowed,
            });
        }
    }
    
    circles
}

// 로컬 릴랙세이션으로 위치 최적화
fn relax_circles(poly_verts: &[Vec2], mut circles: Vec<Circle>, iters: usize, step: f32) -> Vec<Circle> {
    if iters == 0 || circles.is_empty() {
        return circles;
    }
    
    let mut rng = StdRng::seed_from_u64(SEED + 1);
    let n = circles.len();
    
    // 8방향 벡터
    let directions = vec![
        Vec2::new(1.0, 0.0),
        Vec2::new(-1.0, 0.0),
        Vec2::new(0.0, 1.0),
        Vec2::new(0.0, -1.0),
        Vec2::new(0.707, 0.707),
        Vec2::new(-0.707, 0.707),
        Vec2::new(0.707, -0.707),
        Vec2::new(-0.707, -0.707),
    ];
    
    for _ in 0..iters {
        let mut indices: Vec<usize> = (0..n).collect();
        indices.shuffle(&mut rng);
        
        for &i in &indices {
            let pos = circles[i].position;
            let r = circles[i].radius;
            let mut best_pos = pos;
            
            let cur_bound = distance_to_boundary(pos, poly_verts);
            let other_circles: Vec<Circle> = circles.iter().enumerate()
                .filter(|(j, _)| *j != i)
                .map(|(_, c)| *c)
                .collect();
            let cur_other = min_clearance_to_circles(pos, &other_circles);
            let mut best_clear = cur_bound.min(cur_other);
            
            for &dir in &directions {
                let random_factor = rng.gen_range(0.0..1.0f32);
                let move_dist = step * (0.5 + random_factor);
                let cand = pos + dir.normalize() * move_dist;
                
                if !point_in_poly_2d(cand, poly_verts) {
                    continue;
                }
                
                let bound_clear = distance_to_boundary(cand, poly_verts);
                if bound_clear < r {
                    continue;
                }
                
                let other_clear = min_clearance_to_circles(cand, &other_circles);
                if other_clear < 0.0 {
                    continue;
                }
                
                let total_clear = bound_clear.min(other_clear);
                if total_clear > best_clear + 1e-6 {
                    best_clear = total_clear;
                    best_pos = cand;
                }
            }
            
            circles[i].position = best_pos;
        }
    }
    
    circles
}