イヤークリッピング(耳切り法)
多角形から「耳」、つまり内部に他の頂点を含まない凸の角を繰り返し切り落として三角形分割する、単純なアルゴリズム。
耳とは、連続する3頂点のうち中央が凸で、その3点がつくる三角形の中に多角形の他の頂点が入っていないものを指す。耳を見つけて三角形として切り取り、残りが三角形1つになるまで繰り返す。
計算量はO(n²)だが実装が容易で、凹多角形や(橋を架けることで)穴のある多角形など、任意の単純多角形に使える。名前は1975年にゲイリー・マイスターズが命名した。フォントやUI図形、ナビゲーション用多角形といった2D輪郭を、GPUが描画できる三角形に変換する際の標準的な選択肢である。