基于图论的平面图形划分算法  

ALGORITHM FOR SPLITTING PLANNER FACES BASED ON GRAPH THEORY

作　　者：杜宏明[1] 姚红卫[1] 

机构地区：[1]西南交通大学机械工程学院,四川成都610031

出　　处：《陕西科技大学学报（自然科学版）》2009年第1期125-129,共5页Journal of Shaanxi University of Science & Technology

摘　　要：提出了一种基于图论的平面图形划分的新方法.首先,平面图形被表示为一有向图,然后用图论中计算基本回路的方法将其划分为只在公共边搭接、互不包含的若干小平面.运用实例表明,与其他算法相比,该方法具有实现容易、划分准确、运算效率高等优点,可用于二维、三维几何形体的集合运算.A new algorithm for splitting planner faces based on graph theory is presented in this paper. First, a planner face can be described as a directed graph, then it is split into some small faces just joining at the common borderlines according to the method of calculating fundamental loops in graph theory. Application example shows that compare with other algorithm, it is relatively simple to implement and Inherent with accuracy and efficiency.

关 键 词：图论 有向图 基本回路 平面图形划分 几何造型 集合运算 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术] O157.5[自动化与计算机技术—计算机科学与技术]