ドロネー三角形分割とは？
どろねーさんかっけいぶんかつ
ドロネー三角形分割とは、点群から「どの三角形の外接円にも他の点が含まれない」という条件を満たす三角形の集合を作る手法です。
ドロネー三角形分割（Delaunay triangulation）とは、平面上に散らばった点の集合（点群）を三角形で埋め尽くす手法の一種で、「どの三角形の外接円の内部にも他の点が含まれない」というドロネー条件を満たすように三角形を構成する方法です。1934年にソビエトの数学者ボリス・ドロネーによって考案されました。
ドロネー三角形分割が重視される理由は、生成される三角形の「質」の良さにあります。ドロネー条件を満たす分割では、細長い潰れた三角形が生まれにくく、各三角形の内角の最小値が最大化されるという優れた特性を持ちます。
ドロネー三角形分割の主な応用分野は以下のとおりです。
- コンピューターグラフィックス：3Dメッシュ生成、地形データの三角形分割
- 有限要素法：構造解析・流体解析のメッシュ作成
- GIS・地図情報：地形のTIN（不規則三角形網）モデル作成
- ボロノイ図の双対：ドロネー三角形分割とボロノイ図は双対関係にある
計算アルゴリズムとしては、逐次挿入法・分割統治法・フリップアルゴリズムなどがあり、n点に対してO(n log n)の時間計算量で構成できます。コンピューター科学において最も基本的な計算幾何アルゴリズムの一つとして広く採用されています。
使い方・例文
地形測量で得た標高データの点群をドロネー三角形分割で結ぶと、質の良い三角形からなる立体地形モデル（TIN）が作成でき、GISソフトウェアの地形表示や斜面解析に利用されます。
この用語をシェア
最終更新: