基于链码和特征形的多边形内外点判断算法

Point in-out Polygon Test Based on Coding Chain and Eigenpolygon

通过对多边形各个顶点与待测点相对位置进行判别,给出了多边形的垂直(水平)链码序列生成方法.该方法根据多边形的链码将原多边形中对判别无关的冗余边或冗余点删除,形成多边形的特征形;待测点在特征形与原多边形内外位置关系上具有一致性,从而大大简化了运算.同时给出了一种点在多边形内外点判断算法,把点在原多边形内外的判断转化为点与其特征形的位置判断,特征形的提取过程是一个线性扫描及条件判断过程,可以避免大量的叉积运算,从而有效地提高了多边形内外点判断算法的效率.程序验证表明:文中算法易于实现,具有运行速度快、稳定性高等优点.

Taking the test point as the origin and using vertical and horizontal coding chain consisting of 1 and 0 to represent each consecutive vertex of the planar polygon lying above the x-axis and on the right side of y-axis, or below the x-axis and on the left side of y-axis respectively, each sequence of three consecutive Is or Os appearing in the vertical or horizontal coding chain is replaced by the first or last digit and the other two are deleted in both chains, at the same time the corresponding vertices are deleted in polygon. Through recursive procedures, a simplified equivalent eigenpolygon is obtained and the in-out polygon test can be readily accomplished by checking the relationships of adjacent 1 and 0 digits in the two chains.