判断平面上点和不规则多边形位置关系算法

本文列举5中计算点和不规则多边形位置关系的算法。

计算机算法实现方案,最好的是弧长法。

射线法 (铅垂线法、水平线法)

射线法是使用最广泛的算法,这是由于相比较其他算法而言,它不但可以正确使用在凹多边形上,而且不需要考虑精度误差问题。

该算法思想是从点出发向右水平做一条射线,计算该射线与多边形的边的相交点个数,当点不在多边形边上时,如果是奇数,那么点就一定在多边形内部,否则,在外部。

其中铅垂线法和水平线法是射线法的两个具体算法,更容易实现,在坐标计算中更方便。

面积法

面积法的思想是如果点在多边形内部或者边上,那么点与多边形所有边组成的三角形面积和等于多边形面积。多边形的面积公式可以用叉积计算。不过计算面积是会有一定误差的,需要设置精度的误差范围。

点线判断法

对于多边形,如果一个点它的所有边的左边,那么这个点一定在多边形内部。利用叉积正好可以判断点与给定边的关系,即点是在边的左边右边还是边上。

转角法

以被测点O为坐标原点,计算其与所有相邻两个多边形顶点点P[i]之间的角度和,所有角度相加后得到360度,即为点在多边形之内,若得到180度,则在多边形边上,0度则在多边形外。

弧长法

弧长法是改进后的转角法,解决了传统转角法的精度问题。算法思想是,以被测点O为坐标原点,将平面划分为4个象限,对每个多边形顶点P[i],计算其所在的象限,然后顺序访问多边形的各个顶点P[i],分析P[i]和P[i+1],有下列三种情况:

  • P[i+1]在P[i]的下一象限。此时弧长和加π/2;

  • P[i+1]在P[i]的上一象限。此时弧长和减π/2;

  • P[i+1]在Pi的相对象限。利用叉积f=y[i+1]x[i]-x[i+1]y[i]计算Op[i]与Op[i+1]的关系,若f=0,Op[i]与Op[i+1]共线,点在多边形边上;若f<0,Op[i+1]在Op[i]逆时针方向,弧长和减π;若f>0,Op[i+1]在Op[i]顺时针方向,弧长和加π。

由于顶点在原点和坐标轴上时需要特殊处理,为了准确性,应该在每次计算顶点时都用叉积判断P是否在当前边上,另外将π用整数代替可以避免浮点数的精度误差。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax