Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (2): 41-42.DOI: 10.3778/j.issn.1002-8331.2011.02.013

• 研究、探讨 • Previous Articles     Next Articles

Decomposing non-convex polyhedron based on successful loop

YU Yong1,ZHANG Ya2,GUO Xijuan2,FENG Xue2   

  1. 1.Department of Physical Education,Yanshan University,Qinhuangdao,Hebei 066004,China
    2.Department of Information Science and Engineering,Yanshan University,Qinhuangdao,Hebei 066004,China
  • Received:2009-04-27 Revised:2009-07-22 Online:2011-01-11 Published:2011-01-11
  • Contact: YU Yong

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

于 勇1,张 亚2,郭希娟2,封 雪2   

  1. 1.燕山大学 体育系,河北 秦皇岛 066004
    2.燕山大学 信息科学与工程学院,河北 秦皇岛 066004
  • 通讯作者: 于 勇

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

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

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

CLC Number: