基于成功回路的凹多面体的剖分算法  

Decomposing non-convex polyhedron based on successful loop

作　　者：于勇[1] 张亚[2] 郭希娟[2] 封雪[2] 

机构地区：[1]燕山大学体育系,河北秦皇岛066004 [2]燕山大学信息科学与工程学院,河北秦皇岛066004

出　　处：《计算机工程与应用》2011年第2期41-42,51,共3页Computer Engineering and Applications

摘　　要：提出了一种对任意凹多面体不添加顶点的凸剖分方法,该算法首先把凹多面体抽象为无向图,无向图的顶点为多面体的顶点,边为多面体的棱和对角棱,权值为棱或对角棱的长度,然后根据普利姆算法构造最小生成树的思想来构造一个成功回路,利用该回路对多面体进行剖分。重复执行此过程,直到剖分后的所有多面体都是非凹的。该算法能够对多面体进行不添加顶点的剖分,同时可以对任意凹多面体多面体进行剖分,包括含有空洞的凹多面体。A new algorithm about decomposing an arbitrary non-convex polyhedron is proposed to convex polyhedrons without adding new vertexes.Firstly,the non-convex polyhedron is abstracted to undirected graph,the vertex of polyhedron for the vertices of graph,the edge and the diagonal edge of polyhedron for the edge of graph,the length of the edge or diagonal edge for the right value of graph.A successful loop is selected according to the minimum cost spanning tree that made by Prim algorithm.Then the non-convex is decomposed by using the successful loop.Repeat the processes until the polyhe-dral are convex.The algorithm can decompose the polyhedron without adding new vertexes.At the same time,it can decompose arbitrary non-convex polyhedrons that consist of holes.

关 键 词：凹多面体 凸剖分 成功回路 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]