基于斜率的多边形内外点快速判别算法

A Fast Test Algorithm to Point in Polygon Based on Slope

多边形的内外点判别是图形学的一个基础算法,为了更大限度地降低其算法复杂度和运算量,提出一种基于斜率的点与多边形位置关系的快速判别法。该方法只需计算该点到多边形各顶点的斜率,然后与多边形各顶点的邻边的斜率进行比较,即可对多边形的内外点快速做出判别。该算法无需复杂的点乘、叉乘、求交、三角函数等运算,在判别过程中仅需平均2n次减法运算和n/2次的除法运算,以及一些比较运算,即可对简单n多边形的内外点做出判别。经测试,该算法快速有效。

To detect if a point in the polygon or not is a basic algorithm in computer graphics, in order to simplify the algorithm complexity, a new method is proposed here which can produce the result fast simply by computing the slope of the line connected from the point to each point of the polygon, and then compare each of the slop to the edges. Within this algorithm, there is no so- phisticated computation, such as dot, cross, intersect, triangle algorithms etc and, merely has 2n times of subtract operate, n/2 times of division, and some simple compare operate in average, hence the result of the point if in an n edges polygon can be pro- duced. Finally, tests suggest that this algorithm is fast and efficient.