ボロノイ図とドロネー三角形分割の幾何学

Q: ボロノイ図とドロネー三角形分割の幾何学とは何ですか？

平面上の有限個の母点集合 P = \{p_1, p_2, \dots, p_n\} に対し、各母点 p_i に対応する**ボロノイ領域（Voronoi Cell）** V(p_i) は以下のように定義される凸多角形である：

Q: ボロノイ図とドロネー三角形分割の幾何学は社会やプログラミングでどのように使われていますか？

SciPyによるボロノイ図とドロネー分割の計算: 空間データ分析や点群処理で使われるPythonコードです。

コンビニ商圏からキリンの皮膚模様、スマホ基地局、最寄り避難所マップまで

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: 平面上の複数の母点（シード点）に対し、『どの母点に最も近いか』で空間を分割した領域がボロノイ図
2: 各領域の境界線は、隣り合う2つの母点を結ぶ線分の『垂直二等分線』で構成される
3: ボロノイ図の双対（裏返し）がドロネー三角形分割であり、3DCGのメッシュ生成や有限要素法に不可欠

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

『一番近いコンビニはどこ？』という日常の疑問から、キリンやトンボの羽の網目模様、スマートフォンの基地局ハンドオーバーまで。自然界とテクノロジーが空間を最適に分け合う普遍の幾何学です。

身につく武器・思考力

垂直二等分線の幾何学的性質の直感理解、計算幾何学（Computational Geometry）の基礎、空間インデックスのセンス

実社会・ITでの活躍現場

•GIS（地理情報システム）での最寄り病院・避難所の管轄エリア策定
•携帯キャリアの5G基地局・アンテナのサービスカバレッジ解析
•3DCGゲームエンジンでのポリゴンメッシュ生成・地形生成
•材料科学における結晶粒界（グレインバウンダリ）の成長シミュレーション

Layer 1 — 直感・シミュレーター

キャンバス上を自由にクリックして新しい母点を追加したり、ドラッグして動かしてみてください。垂直二等分線によって空間が瞬時に再分割され、美しいボロノイ多角形がリアルタイムに形を変える様子を体験できます。

自然界と都市の境界線

キャンバスをクリックして母点を追加してみよう！空間が自動分割されます

各領域の中にあるどの点も、他の母点より「その領域の中心にある母点」に最も近い性質を持ちます。キリンの模様から最寄り店舗の商圏まで、自然と都市の最適分割を体験できます。

ドロネー三角形の網目を表示

🏪 最寄り商圏の策定

どの家からどの店舗が一番近いかを自動計算。コンビニ出店戦略や学区割りに活用。

🦒 生物の形態形成

キリンの皮膚模様やトンボの羽の翅脈（しみゃく）など、細胞の同時成長で自然に生まれるパターン。

🎮 3DCGメッシュ生成

ドロネー三角形分割の双対性を活かし、尖った歪みのない美しいポリゴンメッシュを生成。

直感チェック！ミニクイズ

ボロノイ領域の境界線（エッジ）は、幾何学的に何に対応しているか？

Layer 2 — 定義・受験・証明

定義

平面上の有限個の母点集合 $P = \{p_1, p_2, \dots, p_n\}$ に対し、各母点 $p_i$ に対応する**ボロノイ領域（Voronoi Cell）** $V(p_i)$ は以下のように定義される凸多角形である：

公式・数理モデル

V(p_i) = \{ x \in \mathbb{R}^2 \mid d(x, p_i) \le d(x, p_j) \quad (\forall j \ne i) \} \text{（} d(x, y) = \|x - y\| \text{ はユークリッド距離）}

証明・導出

**垂直二等分線による領域形成** 2点 $p_i, p_j$ について、 $p_i$ の方が近い点の集合（半平面）は：

H(p_i, p_j) = \{ x \in \mathbb{R}^2 \mid \|x - p_i\| \le \|x - p_j\| \}

この境界は線分 $p_i p_j$ の垂直二等分線である。ボロノイ領域 $V(p_i)$ は、自分以外のすべての母点 $p_j$ に対する半平面の共通部分（インターセクション）として表される：

V(p_i) = \bigcap_{j \ne i} H(p_i, p_j)

凸集合の共通部分は常に凸集合であるため、**すべてのボロノイ領域は必ず凸多角形（または無限遠に伸びる開領域）**となる。

**ドロネー三角形分割との双対性** ボロノイ領域が境界（辺）を共有する母点同士を線分で結ぶと、平面は三角形に分割される。これが**ドロネー三角形分割（Delaunay Triangulation）**である。ドロネー三角形の外接円の内部には、他のどの母点も含まれないという『空円特性（Empty Circumcircle Property）』を持つため、最も細長い潰れた三角形ができにくい『良質なメッシュ』として工学的に多用される。

押さえておきたいポイント

ボロノイ領域の辺は、隣り合う2母点の垂直二等分線上に位置する
3つのボロノイ領域が交わる点（ボロノイ頂点）は、対応する3母点の外接円の中心（外心）である
フォーチュンの走査線法（Fortune's Sweep-line Algorithm）を用いれば、 $O(n \log n)$ の高速で全領域を計算できる

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

SciPyによるボロノイ図とドロネー分割の計算

空間データ分析や点群処理で使われるPythonコードです。

1import numpy as np
2from scipy.spatial import Voronoi, voronoi_plot_2d, Delaunay
3import matplotlib.pyplot as plt
4
5# 母点（ランダムな2次元座標）
6points = np.random.rand(15, 2)
7
8# 1. ボロノイ図の計算
9vor = Voronoi(points)
10
11# 2. ドロネー三角形分割の計算
12tri = Delaunay(points)
13
14# プロット表示
15fig, ax = plt.subplots(figsize=(6, 6))
16voronoi_plot_2d(vor, ax=ax, show_vertices=False, line_colors='blue')
17ax.triplot(points[:, 0], points[:, 1], tri.simplices, color='red', alpha=0.3)
18plt.title("Voronoi (Blue) & Delaunay (Red)")
19plt.show()