Abstract: 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 polyhedral 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.

Key words: non-convex polyhedron, convex decomposition, successful loop

摘要： 提出了一种对任意凹多面体不添加顶点的凸剖分方法，该算法首先把凹多面体抽象为无向图，无向图的顶点为多面体的顶点，边为多面体的棱和对角棱，权值为棱或对角棱的长度，然后根据普利姆算法构造最小生成树的思想来构造一个成功回路，利用该回路对多面体进行剖分。重复执行此过程，直到剖分后的所有多面体都是非凹的。该算法能够对多面体进行不添加顶点的剖分，同时可以对任意凹多面体多面体进行剖分，包括含有空洞的凹多面体。

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