# AI 꾸러미 — 보로노이 지역 · 나라 나누기 — Voronoi diagram
> 씨앗 점마다 가장 가까운 땅을 한 지역으로 나누고, 씨앗을 무게중심으로 옮기기를 되풀이해 지역 크기를 고르게 한다.  
> 견본: https://ai-techstudio.web.app/#t/i246

이 문서를 코드 도우미(Claude Code · Cursor · ChatGPT 등)에 그대로 주면 돼요. 「## 주문서」 가 할 일, 나머지는 참고 자료예요.

## 주문서

### 만들어 줘: 보로노이 지역 · 나라 나누기 — Voronoi diagram

#### 1. 목표
나라 나누기 지도를 보로노이 지역으로 나누고 로이드 완화로 크기를 고르게 다듬어 줘 — 씨앗이 무게중심으로 옮겨 가는 화살표가 보이게. 분위기는 양피지 옛 지도.

#### 2. 핵심 기술 용어
- **Voronoi diagram** — 가장 가까운 씨앗끼리 묶은 지역 나누기
- **Lloyd's relaxation** — 씨앗을 제 지역의 무게중심으로 옮기기를 되풀이
- **Half-plane clipping** — 두 씨앗의 수직이등분선으로 다각형 자르기
- **Polygon centroid (shoelace)** — 신발끈 공식으로 넓이 · 무게중심

#### 3. 환경
- 플랫폼: HTML Canvas 2D (TypeScript), requestAnimationFrame 루프, 라이브러리 없이
- 화면: 2D · 브라우저 — PC 와 폰(390px 폭) 모두, devicePixelRatio 맞춰 또렷하게, 60fps 목표

#### 4. 조건
- 지역 다각형은 바깥 네모(판 전체)에서 시작해 반평면으로 잘라 만들기 — 판 밖으로 넘치지 않게
- 로이드 한 번마다 「화살표(옛 자리 → 무게중심)」 → 「씨앗이 부드럽게 옮겨 감」 순서로 보이기
- 넓이가 0 인 다각형(무게중심을 못 구함)은 씨앗을 그대로 두기
- 씨앗 수 · 로이드 켬/끔 · 시드를 바꿀 수 있게

#### 5. 완성 기준 (이게 보이면 성공)
- 씨앗이 하나씩 뿌려지며 지역이 나뉘고, 국경선이 판 끝까지 정확히 이어진다
- 로이드 완화가 돌면 몰려 있던 씨앗이 퍼지고 「넓이 차이 ±%」 숫자가 줄어든다
- 로이드를 끄면 씨앗이 처음 자리에 머물고 지역 크기가 제각각이다
- 씨앗 48개에서도 화면이 끊기지 않는다

#### 6. 진행 방식
- 핵심 코드 위주로, 설명은 짧게. 내 프로젝트에 끼워 넣기 쉬운 함수 · 클래스로 나눠 줘.
- 처음 화면에 바로 결과가 보이게, 그리고 켬/끔(또는 전/후) 비교를 할 수 있게 만들어 줘.
- 그림 · 소리 · 모델 파일이 필요하면 코드로 만든 임시 대체물로 먼저 돌아가게 하고, 진짜 파일로 바꿀 자리를 표시해 줘.
- 마지막에 「확인 방법」(무엇을 보면 성공인지)과 「조절할 값」 목록을 짧게 정리해 줘.
- 답변과 코드 주석은 한국어로 해 줘.

## 원리
- 씨앗 i 의 지역 = 온 땅에서 씨앗 i 가 가장 가까운 점들. 두 씨앗의 수직이등분선 한쪽만 남기기를 다른 모든 씨앗과 하면 그 다각형이 나온다.
- 자를 때 반평면 식은 n·p ≤ c, 여기서 n = (다른 씨앗 − 내 씨앗), c = n·(두 씨앗의 가운데).
- 다각형 무게중심은 신발끈 공식(꼭짓점 쌍의 외적 합)으로 구한다.
- 로이드 완화: 모든 씨앗을 제 지역 무게중심으로 옮기고 다시 나누기를 몇 번(견본 8회) 하면 지역 넓이가 고르게 된다.
- 넓이 차이(표준편차 ÷ 평균)를 막대로 보이면 되풀이할수록 줄어드는 것이 숫자로 보인다.

## 핵심 코드 — 반평면 자르기로 보로노이 + 무게중심 + 로이드 한 번
(발췌: demos/demosMapA.ts clipHalf · voronoi · centroid 를 정리)
```ts
type P2 = [number, number];
// 다각형에서 n·p <= c 쪽만 남긴다
function clipHalf(poly: P2[], nx: number, ny: number, c: number): P2[] {
  const out: P2[] = [];
  for (let k = 0; k < poly.length; k++) {
    const a = poly[k], b = poly[(k + 1) % poly.length];
    const da = nx * a[0] + ny * a[1] - c, db = nx * b[0] + ny * b[1] - c;
    if (da <= 0) out.push(a);
    if ((da <= 0) !== (db <= 0)) { const t = da / (da - db); out.push([a[0] + (b[0] - a[0]) * t, a[1] + (b[1] - a[1]) * t]); }
  }
  return out;
}
function voronoi(sites: P2[], W: number, H: number): P2[][] {
  return sites.map((s, i) => {
    let poly: P2[] = [[0, 0], [W, 0], [W, H], [0, H]];
    for (let j = 0; j < sites.length && poly.length > 2; j++) {
      if (j === i) continue;
      const o = sites[j], nx = o[0] - s[0], ny = o[1] - s[1];
      poly = clipHalf(poly, nx, ny, (nx * (o[0] + s[0]) + ny * (o[1] + s[1])) / 2); // 수직이등분선
    }
    return poly;
  });
}
function centroid(poly: P2[]): [number, number, number] {
  let a = 0, cx = 0, cy = 0;
  for (let k = 0; k < poly.length; k++) {
    const p = poly[k], q = poly[(k + 1) % poly.length];
    const cr = p[0] * q[1] - q[0] * p[1]; // 신발끈
    a += cr; cx += (p[0] + q[0]) * cr; cy += (p[1] + q[1]) * cr;
  }
  a *= 0.5;
  return Math.abs(a) < 1e-9 ? [poly[0][0], poly[0][1], 0] : [cx / (6 * a), cy / (6 * a), Math.abs(a)];
}
// 로이드 한 번: 씨앗 → 제 지역 무게중심
const lloyd = (sites: P2[], W: number, H: number): P2[] =>
  voronoi(sites, W, H).map((p, i) => { const c = centroid(p); return c[2] > 0 ? [c[0], c[1]] : sites[i]; });
```

## 흔한 실수 · 확인 목록
- [ ] **다른 씨앗과의 수직이등분선 방향을 반대로 잡으면 지역이 사라진다** — n = 다른 씨앗 − 내 씨앗, 남기는 쪽은 n·p ≤ c (내 씨앗 쪽).
- [ ] **넓이 0 인 다각형의 무게중심을 쓰면 NaN 이 퍼진다** — 넓이가 거의 0 이면 씨앗을 옮기지 않는다.
- [ ] **씨앗을 한 번에 순간 이동시키면 로이드가 무엇을 하는지 안 보인다** — 화살표를 먼저 보이고, 그다음 ease 로 옮겨 가게 한다.

## 완성 기준 체크리스트
- [ ] 씨앗이 하나씩 뿌려지며 지역이 나뉘고, 국경선이 판 끝까지 정확히 이어진다
- [ ] 로이드 완화가 돌면 몰려 있던 씨앗이 퍼지고 「넓이 차이 ±%」 숫자가 줄어든다
- [ ] 로이드를 끄면 씨앗이 처음 자리에 머물고 지역 크기가 제각각이다
- [ ] 씨앗 48개에서도 화면이 끊기지 않는다

## 이 기술 정보
- id: `i246` · 분류: 지도 · 길찾기 › 지도 생성 (절차) · 2D · 난이도 보통 · 폰 부담 가벼움 (폰 OK) — 씨앗 n 개마다 다른 n − 1 개로 자르니 n² (48개 = 약 2,300번 자르기). 수십 개까지는 매 프레임 다시 계산해도 가볍다.
- 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i246
- 쓰면 좋을 때: 나라 · 영역 지도를 무작위로 만들 때 / 땅따먹기처럼 칸 모양이 제각각이어도 크기는 비슷해야 할 때 / 넓이 · 거리 개념을 그림으로 보여 줄 때
- 쓰지 말 때: 씨앗이 수천 개 — 반평면 자르기는 n² 이라 대신 들로네 삼각분할(d3-delaunay 등)로 / 네모 칸이면 충분한 판 — 대신 보통 격자

## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript)
### centroid — `src/demos/demosMapA.ts:334`
```ts
function centroid(poly: P2[]): [number, number, number] {
  let a = 0;
  let cx = 0;
  let cy = 0;
  for (let k = 0; k < poly.length; k++) {
    const p = poly[k]!;
    const q = poly[(k + 1) % poly.length]!;
    const cr = p[0] * q[1] - q[0] * p[1];
    a += cr;
    cx += (p[0] + q[0]) * cr;
    cy += (p[1] + q[1]) * cr;
  }
  a *= 0.5;
  if (Math.abs(a) < 1e-9) return [poly[0]?.[0] ?? 0, poly[0]?.[1] ?? 0, 0];
  return [cx / (6 * a), cy / (6 * a), Math.abs(a)];
}
```

### i246 견본 항목 — `src/demos/demosMapA.ts:655`
```ts
  i246: {
    kind: '2d',
    caption: '씨앗마다 가장 가까운 땅 = 한 나라 — 로이드 완화: 씨앗을 제 나라의 무게중심으로 옮기면 크기가 고르게',
    make() {
      const LW = 1.6;
      const LH = 1;
      let count = 18;
      let lloyd = true;
      let arrows = true;
      let sites: P2[] = [];
      let from: P2[] = [];
      let to: P2[] = [];
      let tk = 0;
      let iter = 0;
      let firstCv = 1;
      const IT = 46;
      const ITERS = 8;
      const COLS = ['#e9c46a', '#f4a261', '#a8d5a2', '#9ecbe0', '#d9a7c7', '#f2d0a4', '#b8c99d', '#c4b5e8', '#f7b7a3', '#8fd3c1'].map(hexV);
      let all: P2[] = [];
      let colorOf: number[] = [];
      const run = runner({
        rate: 60,
        hold: 1.6,
        start(seed) {
          const r = mulberry(seed);
          all = [];
          for (let i = 0; i < count; i++) all.push([0.06 + r() * (LW - 0.12), 0.06 + r() * (LH - 0.12)]);
          // 몰린 곳이 있도록 일부는 한쪽으로
          const cx = 0.3 + r() * 1.0;
          const cy = 0.3 + r() * 0.4;
          for (let i = 0; i < count * 0.35; i++) all[i] = [clamp(cx + (r() - 0.5) * 0.45, 0.03, LW - 0.03), clamp(cy + (r() - 0.5) * 0.4, 0.03, LH - 0.03)];
          colorOf = all.map((_, i) => i % COLS.length);
          sites = [];
          from = [];
          to = [];
          tk = 0;
          iter = 0;
          firstCv = 1;
        },
        step() {
          tk++;
          const sow = count * 3;
          if (tk <= sow) {
            if (tk % 3 === 0) sites.push([...all[tk / 3 - 1]!] as P2);
            if (tk === sow) firstCv = areaCv();
            return false;
          }
          if (!lloyd) return tk > sow + 30;
          const lt = tk - sow - 1;
          const it = Math.floor(lt / IT);
          if (it >= ITERS) return true;
          const f = (lt % IT) / IT;
          if (lt % IT === 0) {
            iter = it + 1;
            from = sites.map((s) => [s[0], s[1]] as P2);
            to = voronoi(sites, LW, LH).map((p, i) => {
              const c = centroid(p);
              return c[2] > 0 ? ([c[0], c[1]] as P2) : from[i]!;
            });
          }
          if (f >= 0.35) {
            const k = ease((f - 0.35) / 0.6);
            sites = from.map((p, i) => [lerp(p[0], to[i]![0], k), lerp(p[1], to[i]![1], k)] as P2);
          }
          return false;
        },
      });
      const areaCv = (): number => {
        const ar = voronoi(sites, LW, LH).map((p) => centroid(p)[2]);
        const mean = ar.reduce((a, b) => a + b, 0) / Math.max(1, ar.length);
        const sd = Math.sqrt(ar.reduce((a, b) => a + (b - mean) * (b - mean), 0) / Math.max(1, ar.length));
        return sd / (mean || 1);
      };
      run.restart();
      return {
        draw(g, w, h, t, dt) {
          reset(g);
          run.tick(dt);
          const u = ui(scaleOf(w, h));
          g.fillStyle = '#1b2a3d';
          g.fillRect(0, 0, w, h);
          const s = Math.min(w / LW, h / LH);
          const ox = (w - LW * s) / 2;
          const oy = (h - LH * s) / 2;
          // 바탕 종이
          g.fillStyle = '#efe3c6';
          g.fillRect(ox, oy, LW * s, LH * s);
          const polys = voronoi(sites, LW, LH);
          polys.forEach((p, i) => {
            if (p.length < 3) return;
            polyPath(g, p, ox, oy, s);
            const c = COLS[colorOf[i]!]!;
            const gr = g.createLinearGradient(0, oy, 0, oy + LH * s);
            gr.addColorStop(0, rgb(mix(c, [255, 255, 255], 0.15)));
            gr.addColorStop(1, rgb(mix(c, [120, 90, 60], 0.12)));
            g.fillStyle = gr;
            g.fill();
          });
          // 종이 결
          g.globalAlpha = 0.08;
          for (let k = 0; k < 40; k++) {
            const yy = oy + ((k * 37) % 100) / 100 * LH * s;
            g.fillStyle = k % 2 ? '#7a5a30' : '#fff';
            g.fillRect(ox, yy, LW * s, 1);
          }
          g.globalAlpha = 1;
          // 국경선
          g.lineJoin = 'round';
          polys.forEach((p) => {
            if (p.length < 3) return;
            polyPath(g, p, ox, oy, s);
            g.strokeStyle = 'rgba(255,250,235,0.7)';
            g.lineWidth = 3.2 * u;
            g.stroke();
          });
          polys.forEach((p) => {
            if (p.length < 3) return;
            polyPath(g, p, ox, oy, s);
            g.strokeStyle = '#6a4a2e';
            g.lineWidth = 1.3 * u;
            g.setLineDash([4 * u, 2.2 * u]);
            g.stroke();
          });
          g.setLineDash([]);
          // 무게중심 화살표
          const lt = tk - count * 3 - 1;
          const f = lt >= 0 ? (lt % IT) / IT : 0;
          if (arrows && lloyd && lt >= 0 && !run.holding && iter > 0) {
            const al = f < 0.35 ? smooth(0, 0.15, f) : 1 - smooth(0.7, 0.95, f);
            g.globalAlpha = al;
            g.strokeStyle = '#c0392b';
            g.fillStyle = '#c0392b';
            g.lineWidth = 1.6 * u;
            to.forEach((c, i) => {
              const a = from[i]!;
              const dx = (c[0] - a[0]) * s;
              const dy = (c[1] - a[1]) * s;
              if (Math.hypot(dx, dy) > 3 * u) arrow(g, ox + a[0] * s, oy + a[1] * s, ox + c[0] * s, oy + c[1] * s, 4.5 * u);
              g.beginPath();
              g.arc(ox + c[0] * s, oy + c[1] * s, 3 * u, 0, TAU);
              g.stroke();
            });
            g.globalAlpha = 1;
          }
          // 수도(씨앗)
          sites.forEach((p, i) => {
            const x = ox + p[0] * s;
            const y = oy + p[1] * s;
            const pop = i === sites.length - 1 && tk <= count * 3 ? 1 + Math.sin((tk % 3) * 1) * 0.4 : 1;
            g.beginPath();
            g.arc(x, y + 0.8 * u, 3.6 * u * pop, 0, TAU);
            g.fillStyle = 'rgba(60,30,10,0.35)';
            g.fill();
            g.beginPath();
            g.arc(x, y, 3.2 * u * pop, 0, TAU);
            g.fillStyle = '#fff';
            g.fill();
            g.lineWidth = 1.4 * u;
            g.strokeStyle = '#3a2614';
            g.stroke();
            g.beginPath();
            g.arc(x, y, 1.2 * u, 0, TAU);
            g.fillStyle = '#c0392b';
            g.fill();
          });
          // 테두리 그늘
          g.strokeStyle = '#5a3e22';
          g.lineWidth = 2 * u;
          g.strokeRect(ox + 1 * u, oy + 1 * u, LW * s - 2 * u, LH * s - 2 * u);
          vignette(g, w, h, 0.25);
          // 정보
          const cvNow = sites.length === count ? areaCv() : 1;
          const label = tk <= count * 3 ? `씨앗 뿌리기 ${sites.length}/${count}` : lloyd ? `로이드 완화 ${iter}회` : '보로노이 지역';
          pill(g, label, 8 * ui(u), 13 * ui(u), 9 * ui(u), 'rgba(58,38,20,0.85)');
          if (sites.length === count) {
            const bw = 70 * u;
            const bx = w - bw - 10 * u;
            const by = 13 * u;
            txt(g, '넓이 차이', bx - 4 * u, by, 8 * u, '#3a2614', 'right', 800);
            rr(g, bx, by - 4 * u, bw, 8 * u, 4 * u);
            g.fillStyle = 'rgba(58,38,20,0.25)';
            g.fill();
            const k = clamp01(cvNow / Math.max(0.6, firstCv));
            rr(g, bx, by - 4 * u, bw * k, 8 * u, 4 * u);
            g.fillStyle = k > 0.5 ? '#d35400' : '#27ae60';
            g.fill();
            txt(g, `±${Math.round(cvNow * 100)}%`, bx + bw / 2, by + 11 * u, 8 * u, '#3a2614', 'center', 800);
          }
          void t;
        },
        controls: [
          seedCtl(run),
          speedCtl(run),
          { type: 'toggle', label: '로이드 완화', value: true, on: (v) => { lloyd = v; run.restart(run.seed); } },
          { type: 'toggle', label: '무게중심 화살표', value: true, on: (v) => { arrows = v; } },
          { type: 'range', label: '씨앗 수', min: 6, max: 48, step: 1, value: 18, on: (v) => { count = v; run.restart(run.seed); } },
        ],
      };
    },
  }
```

## 관련 기술
- 먼저 알면 좋은 기술: [잡음 섬 지도 (높이 → 생물군)](https://ai-techstudio.web.app/ai/t/i245.md) `i245`
- 다음에 해 볼 기술: [등치 지도 (색칠 통계 지도)](https://ai-techstudio.web.app/ai/t/i277.md) `i277` · [육각 타일 행성 (골드버그 다면체)](https://ai-techstudio.web.app/ai/t/i539.md) `i539`
- 참고 문서: [Wikipedia — Voronoi diagram](https://en.wikipedia.org/wiki/Voronoi_diagram) · [Wikipedia — Lloyd's algorithm](https://en.wikipedia.org/wiki/Lloyd%27s_algorithm)