WebCAD中的剖面区域搜索算法

基于Web的CAD系统是协同设计研究的一个分支。论文讨论了矢量化标记语言用于在Web上表示矢量图形的优点，比较了常见的几种剖面区域搜索算法，提出了一种不依赖操作系统的剖面区域搜索的新算法。该算法提供四种可行的搜索方向，能搜索出包含一个给定种子点的唯一外部最小剖面区域和不包含该种子点的所有内部非剖面区域，其计算复杂度与图形尺寸无关。文中最后给出了此算法的应用实例及计算性能。关键词  网页CAD；矢量图形；剖面区域；搜索Abstract  Web  based  CAD  is  a  branch  of  the  researches  on  collaborative  design.  This  paper  discusses  the  advantages  of  the  vector  markup  language  (VML)  used  to  present  vector  graphics  on  Web,  compares  several  types  of  finding  algorithms  for  hatch  region  and  proposes  a  new  algorithm  which  is  independent  of  operating  systems  for  searching  hatch  region.  The  algorithm  provides  four  feasible  searching  directions  for  searching  an  outer  minimum  hatch  region  which  includes  a  given  seed  point  and  finding  out  all  the  internal  non-hatch  regions  which  exclude  the  seed  point.  The  computing  complexity  of  this  algorithm  is  irrespective  with  the  size  of  graphics.  An  application  example  of  this  algorithm  and  its  computational  performance  are  given  at  last.Key  words  web  CAD;  vector  graphics;  hatch  region;  search