泰森多边形的建立步骤

更新时间： 2025-05-07 19:03:09

步骤如下：

离散点自动构建三角网，即构建Delaunay三角网，对离散点和形成的三角形编号，记录每个三角形构成的三个离散点；记录与每个离散点相邻的所有三角形的编号；对与每个离散点相邻的三角形按顺时针或逆时针方向排序，以便连接生成泰森多边形，设离散点为o，将以o为顶点的一个三角形设为A，将三角形A除o以外的另一顶点设为a，另一个顶点为f，下一个三角形必然以of为边，构成三角形F，三角形F的另一顶点为e，下一三角形以oe为边，重复进行，至与oa边重合为止；计算并记录每个三角形的外接圆圆心；根据每个离散点的相邻三角形，连接相邻三角形的外接圆圆心，可得到泰森多边形，三角网边缘的泰森多边形，可作垂直平分线与图廓相交，与图廓构成泰森多边形。