ドロネー図(ドロネーず、)あるいはドロネー三角形分割(ドロネーさんかっけいぶんかつ、, )は、距離空間内に離散的に分布した点の集合に対し得られる、それらをある方法に従い辺で結んだ図形である。
計算幾何学あるいは離散幾何学における代表的な考察対象の1つである。名称は考案者であるロシアの数学者、()に由来する。ドロネー図の双対はボロノイ図であり、ドロネー図はボロノイ領域の隣接関係を表している。
双対 与えられたボロノイ図から対応するドロネー図を作図するには、与えられたボロノイ図の各領域(ボロノイ領域)に一つずつの特定の点(母点)を選んで固定し、どの二つのボロノイ領域についても、それが隣接ボロノイ領域ならば母点同士を結び、隣接していない場合は二つの母点を結ばないという操作を行う。元のボロノイ図の母点をドロネー点、得られたドロネー図のドロネー点を結んでいる線分をドロネー辺あるいはドロネー境界という。二次元のドロネー図ならば、ドロネー点とドロネー辺は多角形(ドロネー多角形)をつくるが、特殊な場合を除きこの多角形は三角形となり(退化して三角形とならない場合には母点を取り替えることで解消できる)、平面はドロネー図によってドロネー三角形の集まりに分割される。これをドロネー三角形分割という。次元を上げても同様のこと(ドロネー単体分割)を考察することができる。
関連項目
ボロノイ図 単体分割 計算格子 アルファシェイプ 参考文献 英文
.
和文
谷口健男:「FEMのための要素自動分割:デローニー三角分割法の利用」、森北出版、IBBN 4-627-91400-8 (1992年9月26日)。※ 出版当時の2次元領域のドローニー三角分割法とそのFortranソースコード掲載。 谷口健男、森脇清明:「3次元FEMのための自動要素分割法」、森北出版、 (2006年12月20日)。※ 出版当時の3次元領域のドローニー分割法とそのFortranソースコード掲載。