寻找包含点k的以点集P中的三个点为顶点的最小三角形
问题描述
通过Lawson算法实现 Delaunay 三角剖分中有这么一个步骤:
就比如说,点集P内有五个点A、B、C、O、K,其中A、B、C、O已经组成四个三角形(ABC, ABO, BCO, CAO),怎么确定包含K的最小三角形AOC呢?
引用
以下内容翻译自Computational Geometry Algoorithms and Applications 3ed. Springer:2008:202-204,我英语水平让人捉急,勿怪,原文会放在最后。
我们使用和第六章用过的十分相似的一个方法寻找包含点 pr 的三角形:当我们构造Delaunay三角剖分的同时,也构造了一个点位置结构(point location structure) D ,它是一个有向无环图(DAG)。 D 的叶子结点相当于当前三角剖分 T 的三角形,并且保留这些叶子和三角剖分的交叉点。 D 的内部结点相当于三角化时早期创建的那些三角形,