Simple Polygon Distance Algorithm Based on Monotone Chains
基于单调链的简单多边形距离算法

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.