本文主要是介绍判断点在多边形内算法（射线法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
转自 ：http://www.cnblogs.com/mazhenyu/p/3800638.html 谢谢分享！
点和多边形关系的算法实现
好了，现在我们已经了解了矢量叉积的意义，以及判断直线段是否有交点的算法，现在回过头看看文章开始部分的讨论的问题：如何判断一个点是否在多边形内部？ 根据射线法的描述，其核心是求解从P点发出的射线与多边形的边是否有交点。注意，这里说的是射线，而我们前面讨论的都是线段，好像不适用吧？没错，确实是 不适用，但是我要介绍一种用计算机解决问题时常用的建模思想，应用了这种思想之后，我们前面讨论的方法就适用了。什么思想呢？就是根据问题域的规模和性质 抽象和简化模型的思想，这可不是故弄玄虚，说说具体的思路吧。
计算机是不能表示无穷大和无穷小，计算机处理的每一个数都有确定的值，而且必须有确定的值。我们面临的问题域是整个实数空间的坐标系，在每个维度上都是 从负无穷到正无穷，比如射线，就是从坐标系中一个明确的点到无穷远处的连线。这就有点为难计算机了，为此我们需要简化问题的规模。假设问题中多边形的每个 点的坐标都不会超过(-10000.0, +10000.0)区间（比如我们常见的图形输出设备都有大小的限制），我们就可以将问题域简化为(-10000.0, +10000.0)区间内的一小块区域，对于这块区域来说，>= 10000.0就意味着无穷远。你肯定已经明白了，数学模型经过简化后，算法中提到的射线就可以理解为从模型边界到内部点P之间的线段，前面讨论的关于线 段的算法就可以使用了。
射线法的基本原理是判断由P点发出的射线与多边形的交点个数，交点个数是奇数表示P点在多边形内（在多边形的边上也视为在多边形内部的特殊情 况），正常情况下经过点P的射线应该如图6（a）所示那样，但是也可能碰到多种非正常情况，比如刚好经过多边形一个定点的情况，如图6 （b），这会被误认为和两条边都有交点，还可能与某一条边共线如图6 （c）和（d），共线就有无穷多的交点，导致判断规则失效。还要考虑凹多边形的情况，如图6（e）。
图6 射线法可能遇到的各种交点情况
针对这些特殊情况，在对多边形的每条边进行判断时，要考虑以下这些特殊情况，假设当前处理的边是P1P2，则有以下原则：
1）如果点P在边P1P2上，则直接判定点P在多边形内；
2）如果从P发出的射线正好穿过P1或者P2，那么这个交点会被算作2次（因为在处理以P1或P2为端点的其它边时可能已经计算过这个点了），对这种情况的处理原则是：如果P的y坐标与P1、P2中较小的y坐标相同，则忽略这个交点；
3）如果从P发出的射线与P1P2平行，则忽略这条边；
对于第三个原则，需要判断两条直线是否平行，通常的方法是计算两条直线的斜率，但是本算法因为只涉及到直线段（射线也被模型简化为长线段了），就简化了 很多，判断直线是否水平，只要比较一下线段起始点的y坐标是否相等就行了，而判断直线是否垂直，也只要比较一下线段起始点的x坐标是否相等就行了。
应用以上原则后，扫描线法判断点是否在多边形内的算法流程就完整了，图7就是算法的流程图：
在图形学领域实施的真正工程代码，通常还会增加一个多边形的外包矩形快速判断，对点根本就不在多边形周围的情况做快速排除， 提高算法效率。这又涉及到求多边形外包矩形的算法，这个算法也很简单，就是遍历多边形的所有节点，找出各个坐标方向上的最大最小值。以下就是求多边形外包 矩形的算法：
除了扫描线法，还可以通过多边形边的法矢量方向、多边形面积以及角度和等方法判断点与多边形的关系。但是这些算法要么只支持 凸多边形，要么需要复杂的三角函数运算（多边形边数小于44时，可采用近似公式计算夹角和，避免三角函数运算），使用的范围有限，只有扫描线法被广泛应 用。
至此，本文的内容已经完结，以上通过对点与矩形、点与圆、点与直线以及点与多边形位置关系判断算法的讲解，向大家展示了几种常见的计算几何算法实现，用简短而易懂的代码剖析了这些算法的实质。下一篇将介绍计算机图形学中最基本的直线生成算法。
这篇关于判断点在多边形内算法（射线法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
