【摘要】 简单多边形的距离问题是计算机图形学中的一个研究难点,为了能快速地获得距离信息,提出一种基于单调链的简单多边形距离算法。算法先对多边形边界进行关于坐标轴的单调链分割,然后根据可见性原则确定候选链对,再结合层次树理论和分支限界策略计算链对距离以求解多边形的最近距离。试验结果表明,该算法性能优于其他同类算法。更多还原

【Abstract】 The distance problem between simple polygons is a nut in computer graphics.A simple polygon distance algorithm based on monotone chains is proposed in this paper for calculating the distance efficiently.It comprises three procedures.Firstly,the simple polygons are decomposed into a collection of monotone chains concerning coordinate axis.Then,the candidate chain-pairs are determined by the visibility rule.Eventually,it computes the distances for all candidate chainpairs using both hierarchy-tree theory and branch-limit strategy in order to solute the minimum distance problem for simple polygons.Experimental results indicate that this approach performs better than other counterparts.更多还原