点对多边形位置检测的稳定串行最优与并行的算法

Stable serial optimal and parallel algorithm of point-in-polygon test

点相对于多边形位置检测是计算机图形学中的一个底层而基本的问题,目前的算法较多,但这些算法要么复杂,要么不稳定,都或多或少存在一些问题。为改进算法,首先从分析直线的正负性入手,进一步全面描述了点与有向线段的各种相互位置关系及相应的处理步骤。借助于正负性,不仅简化了点与有向线段的位置判断,降低了算法复杂性,更彻底消除了各种不稳定的因素。算法处理如此的精细也保证了算法的可并行性,实现了串、并行算法。实验证明,串行算法是一个稳定的最优算法。

Point-in-polygon test is a bottom and basic problem of computer graphics.The current algorithm is more,but these algorithms are complex or unstable and all more or less exists some problems.For improving the algorithm,the text started with analyzing the plus or minus characteristic of a straight line,further described roundly various mutual positions relation between the point and the directed line segment and the corresponding disposing process.By means of the plus or minus characteristic,not only simplified the position judgment between the point and the directed line segment,reduced the algorithm complexity,more eliminated drastically various unstable factors.It realized the serial and parallel algorithm.Finally experimental results prove that the serial algorithm is a stable optimal algorithm.