我正在编写一个程序,需要实现中轴线提取,其中Delaunay三角剖分是其中的一步。外部中轴线是不需要的,因此相应的外部三角形将被删除。幸运的是我发现了一个页面,里面有很多图表,也有一种根据“折线周长”确定内部和外部Delaunay三角形的方法的提示,但只是一个提示,没有详细的解释。有人知道该算法吗?
编辑:我忘记提到最初的点是从封闭多边形的边界采样的,我的意图是确定每个Delaunay三角形是否在多边形内部。
我正在编写一个程序,需要实现中轴线提取,其中Delaunay三角剖分是其中的一步。外部中轴线是不需要的,因此相应的外部三角形将被删除。幸运的是我发现了一个页面,里面有很多图表,也有一种根据“折线周长”确定内部和外部Delaunay三角形的方法的提示,但只是一个提示,没有详细的解释。有人知道该算法吗?
编辑:我忘记提到最初的点是从封闭多边形的边界采样的,我的意图是确定每个Delaunay三角形是否在多边形内部。
此解决方案假设您有一个数据结构,使用“虚拟无限Delaunay顶点”代表Delaunay三角剖分,就像CGAL所做的那样(在这里查看详细信息)。
思路是找到边界Delaunay边:连接两个连续采样点的边;然后通过Delaunay三角剖分“泛洪”,以对Delaunay面进行分类。人们知道无限顶点是外部的,因此只要不越过边界边,就可以将其邻居(和邻居的邻居等)分类为外部。如果到达边界边,则可以简单地将相邻的三角形标记为内部,并继续类似地进行。
输入: 一组紧密采样封闭形状的边界点,甚至可以包含空洞
输出: 形状内部的Voronoi图(形状中心轴的近似值)