# 機能設計書 172-ShapeUtils

## 概要

本ドキュメントは、Three.jsのシェイプ処理ユーティリティクラス「ShapeUtils」の機能設計について記述する。ShapeUtilsは2Dポリゴンの面積計算、巻き順判定、三角形分割（トリアンギュレーション）機能を提供する。

### 本機能の処理概要

ShapeUtilsクラスは、2D形状（Shape）を3Dジオメトリに変換する際に必要となる数学的処理を提供するユーティリティクラスである。特に、複雑な2Dポリゴンを三角形の集合に分割する機能は、3Dメッシュ生成の基盤となる重要な処理である。

**業務上の目的・背景**：3DグラフィックスのレンダリングAPIは三角形を基本単位として扱うため、任意の2Dシェイプを3Dメッシュとして表示するには三角形分割が必須である。また、穴（hole）を含む複雑なポリゴンも正しく処理する必要がある。ShapeUtilsはこれらの処理を統一されたインターフェースで提供し、ShapeGeometry、ExtrudeGeometryなどのジオメトリクラスから利用される。

**機能の利用シーン**：
- 2Dパスやシェイプから3Dジオメトリを生成する場合（ShapeGeometry）
- テキストや図形を押し出して3Dオブジェクトを作成する場合（ExtrudeGeometry）
- SVGパスを3Dオブジェクトに変換する場合
- カスタムシェイプを定義して3Dモデルを作成する場合

**主要な処理内容**：
1. area: 2Dポリゴンの面積を計算（Shoelace formula使用）
2. isClockWise: ポリゴンの巻き順（時計回りかどうか）を判定
3. triangulateShape: ポリゴンと穴を含むシェイプを三角形に分割

**関連システム・外部連携**：
- Earcutモジュール: 高性能な三角形分割アルゴリズムを提供
- Shapeクラス: 2Dシェイプの定義を管理
- ShapeGeometry/ExtrudeGeometry: 三角形分割結果を使用してメッシュを生成

**権限による制御**：特になし（クライアントサイドで実行される汎用ユーティリティ）

## 関連画面

画面機能マッピングに直接的な関連画面の登録なし。本機能は内部ユーティリティとしてジオメトリ生成機能から呼び出される。

## 機能種別

計算処理 / ジオメトリ変換 / ユーティリティ

## 入力仕様

### 入力パラメータ

#### area メソッド

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| contour | Array\<Vector2\> | Yes | 2D点の配列（ポリゴンの輪郭） | 最低3点必要 |

#### isClockWise メソッド

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| pts | Array\<Vector2\> | Yes | 2D点の配列（ポリゴンの輪郭） | 最低3点必要 |

#### triangulateShape メソッド

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| contour | Array\<Vector2\> | Yes | 外側輪郭の2D点配列 | 最低3点必要 |
| holes | Array\<Array\<Vector2\>\> | Yes | 穴の配列（各穴は2D点配列） | 空配列可 |

### 入力データソース

- Vector2オブジェクトの配列: x, yプロパティを持つ2D座標点
- Shapeクラス: getPoints()で取得したポイント配列
- Pathクラス: getPoints()で取得したポイント配列

## 出力仕様

### 出力データ

#### area メソッド

| 項目名 | 型 | 説明 |
|--------|-----|------|
| area | number | ポリゴンの符号付き面積（正=反時計回り、負=時計回り） |

#### isClockWise メソッド

| 項目名 | 型 | 説明 |
|--------|-----|------|
| isClockwise | boolean | true=時計回り、false=反時計回り |

#### triangulateShape メソッド

| 項目名 | 型 | 説明 |
|--------|-----|------|
| faces | Array\<Array\<number\>\> | 三角形の頂点インデックス配列の配列 |

### 出力先

- メモリ上のオブジェクト（戻り値として返却）

## 処理フロー

### 処理シーケンス

#### area

```
1. 輪郭点の数を取得
2. 面積変数を0で初期化
3. 各辺について外積を計算してループ
   └─ 隣接する2点の外積成分を累積
4. 結果を2で割って返却（Shoelace formula）
```

#### isClockWise

```
1. areaメソッドで面積を計算
2. 面積が負の場合はtrue（時計回り）を返却
3. それ以外はfalse（反時計回り）を返却
```

#### triangulateShape

```
1. 頂点配列、穴インデックス配列、面配列を初期化
2. 輪郭から重複する終端点を削除
3. 輪郭の点をフラット配列に追加
4. 穴インデックスの開始位置を記録
5. 各穴について：
   └─ 重複する終端点を削除
   └─ 穴インデックスを記録
   └─ 穴の点をフラット配列に追加
6. Earcut.triangulateで三角形分割を実行
7. 結果を3つずつグループ化して面配列を生成
8. 面配列を返却
```

### フローチャート

```mermaid
flowchart TD
    A[開始: triangulateShape] --> B[頂点配列を初期化]
    B --> C[輪郭の重複終端点を削除]
    C --> D[輪郭点をフラット配列に追加]
    D --> E{穴が存在する?}
    E -->|Yes| F[各穴をループ処理]
    F --> G[穴の重複終端点を削除]
    G --> H[穴インデックスを記録]
    H --> I[穴の点をフラット配列に追加]
    I --> F
    F -->|完了| J[Earcut.triangulateを実行]
    E -->|No| J
    J --> K[結果を3点ずつグループ化]
    K --> L[面配列を返却]
    L --> M[終了]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-172-01 | 重複点除去 | ポリゴンの最初と最後の点が同一の場合、最後の点を除去 | triangulateShape実行時 |
| BR-172-02 | 巻き順判定 | 面積が負の場合を時計回りとして判定 | isClockWise実行時 |
| BR-172-03 | 穴インデックス | 穴の開始インデックスは外側輪郭の点数から始まる | triangulateShape実行時 |
| BR-172-04 | 座標フラット化 | x, y座標を交互に配置したフラット配列を生成 | Earcut呼び出し前 |

### 計算ロジック

**Shoelace formula（靴紐公式）による面積計算**：
```
A = (1/2) * |Σ(x[i] * y[i+1] - x[i+1] * y[i])|
```
ここで、i は 0 から n-1 まで、インデックスは n で 0 に戻る。

**符号付き面積**：
- 正の値：反時計回り（CCW: Counter-Clockwise）
- 負の値：時計回り（CW: Clockwise）

## データベース操作仕様

本機能はデータベース操作を行わない。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | 実行時エラー | 入力配列が空または点数が不足 | Earcutが空の結果を返す |
| - | 計算エラー | 自己交差するポリゴン | Earcutが最善努力で処理 |

### リトライ仕様

リトライ処理は実装されていない（同期処理のため）

## トランザクション仕様

トランザクション処理は適用されない（メモリ上の処理のみ）

## パフォーマンス要件

- area/isClockWise: O(n)の計算量（nは頂点数）
- triangulateShape: Earcutアルゴリズムに依存（通常O(n log n)、最悪O(n^2)）

## セキュリティ考慮事項

特になし（純粋な数学計算処理）

## 備考

- Earcutライブラリは高性能な耳刈り法（ear clipping）の実装
- 自己交差するポリゴンは完全にはサポートされていないが、多くの場合で動作する
- 穴は外側輪郭と同じ巻き順で定義する必要がある

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | Vector2.js | `src/math/Vector2.js` | x, yプロパティを持つ2Dベクトルクラス |
| 1-2 | ShapeUtils.js | `src/extras/ShapeUtils.js` | 8行目でクラス定義を確認 |

**読解のコツ**: 入力となるVector2配列の構造を理解することが重要。各点はx, yプロパティを持つオブジェクト。

#### Step 2: エントリーポイントを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | ShapeUtils.js | `src/extras/ShapeUtils.js` | 3つの静的メソッド（area, isClockWise, triangulateShape）を確認 |

**主要処理フロー**:
1. **16-29行目**: areaメソッド - Shoelace formulaによる面積計算
2. **21-25行目**: 外積計算ループ - p=n-1から開始してq=0から進む形で隣接点の外積を累積
3. **37-41行目**: isClockWiseメソッド - areaが負なら時計回り
4. **50-87行目**: triangulateShapeメソッド - 三角形分割の本体
5. **56-57行目**: 輪郭処理 - removeDupEndPtsとaddContour呼び出し
6. **75行目**: Earcut.triangulate呼び出し - 実際の三角形分割

#### Step 3: 依存関係を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | Earcut.js | `src/extras/Earcut.js` | triangulateメソッド - 耳刈り法による三角形分割 |

**主要処理フロー**:
- **Earcut.triangulate**: フラット配列と穴インデックスを受け取り、頂点インデックスの配列を返す

#### Step 4: ヘルパー関数を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | ShapeUtils.js | `src/extras/ShapeUtils.js` | 91-101行目 removeDupEndPts関数 |
| 4-2 | ShapeUtils.js | `src/extras/ShapeUtils.js` | 103-112行目 addContour関数 |

**主要処理フロー**:
- **91-101行目**: removeDupEndPts - 最初と最後の点が同じなら最後を削除
- **95行目**: Vector2.equals()を使用して点の同一性を判定
- **103-112行目**: addContour - Vector2配列をフラット配列（[x0, y0, x1, y1, ...]）に変換

### プログラム呼び出し階層図

```
ShapeUtils.triangulateShape(contour, holes)
    │
    ├─ removeDupEndPts(contour)
    │      └─ points[].equals()  [Vector2メソッド]
    │
    ├─ addContour(vertices, contour)
    │
    ├─ holes.forEach(removeDupEndPts)
    │
    ├─ holes[i] → addContour(vertices, holes[i])
    │
    └─ Earcut.triangulate(vertices, holeIndices)  [Earcut.js]

ShapeUtils.isClockWise(pts)
    └─ ShapeUtils.area(pts)
```

### データフロー図

```
[入力]                         [処理]                           [出力]

Array<Vector2> ───────────▶ area() ────────────────────────▶ number (面積)
  (contour)                    │
                               └─ Shoelace formula計算


Array<Vector2> ───────────▶ isClockWise() ─────────────────▶ boolean
  (pts)                        │
                               └─ area() < 0 判定


Array<Vector2> ───────┐
  (contour)           │
                      ├──────▶ triangulateShape() ─────────▶ Array<Array<number>>
Array<Array<Vector2>> │            │                           (faces)
  (holes)             ┘            │
                                   ├─ removeDupEndPts()
                                   │
                                   ├─ addContour()
                                   │      └─ [x0, y0, x1, y1, ...] フラット配列
                                   │
                                   └─ Earcut.triangulate()
                                          └─ [i0, i1, i2, i3, i4, i5, ...] インデックス配列
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| ShapeUtils.js | `src/extras/ShapeUtils.js` | ソース | シェイプユーティリティの本体 |
| Earcut.js | `src/extras/Earcut.js` | ソース | 三角形分割アルゴリズム（earcut） |
| Vector2.js | `src/math/Vector2.js` | ソース | 2Dベクトルクラス |
| Shape.js | `src/extras/core/Shape.js` | ソース | 2Dシェイプの定義（ShapeUtilsの利用元） |
| ShapeGeometry.js | `src/geometries/ShapeGeometry.js` | ソース | ShapeUtilsを使用してジオメトリを生成 |
| ExtrudeGeometry.js | `src/geometries/ExtrudeGeometry.js` | ソース | ShapeUtilsを使用して押し出しジオメトリを生成 |
