点和多边形关系的算法实现
好了，现在我们已经了解了矢量叉积的意义，以及判断直线段是否有交点的算法，现在回过头看看文章开始部分的讨论的问题：如何判断一个点是否在多边形内部？ 根据射线法的描述，其核心是求解从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就是算法的流程图：
最终扫描线法判断点是否在多边形内的算法实现如下：
228 bool IsPointInPolygon(const Polygon& py, const Point& pt)
229 {
230 assert(py.IsValid()); /*只考虑正常的多边形，边数>=3*/
231
232 int count = 0;
233 LineSeg ll = LineSeg(pt, Point(-INFINITE, pt.y)); /*射线L*/
234 for(int i = 0; i < py.GetPolyCount(); i++)
235 {
236 /*当前点和下一个点组成线段P1P2*/
237 LineSeg pp = LineSeg(py.pts[i], py.pts[(i + 1) % py.GetPolyCount()]);
238 if(IsPointOnLineSegment(pp, pt))
239 {
240 return true;
241 }
242
243 if(!pp.IsHorizontal())
244 {
245 if((IsSameFloatValue(pp.ps.y, pt.y)) && (pp.ps.y > pp.pe.y))
246 {
247 count++;
248 }
249 else if((IsSameFloatValue(pp.pe.y, pt.y)) && (pp.pe.y > pp.ps.y))
250 {
251 count++;
252 }
253 else
254 {
255 if(IsLineSegmentIntersect(pp, ll))
256 {
257 count++;
258 }
259 }
260 }
261 }
262
263 return ((count % 2) == 1);
264 }
在图形学领域实施的真正工程代码，通常还会增加一个多边形的外包矩形快速判断，对点根本就不在多边形周围的情况做快速排除， 提高算法效率。这又涉及到求多边形外包矩形的算法，这个算法也很简单，就是遍历多边形的所有节点，找出各个坐标方向上的最大最小值。以下就是求多边形外包 矩形的算法：
266 void GetPolygonEnvelopRect(const Polygon& py, Rect& rc)
267 {
268 assert(py.IsValid()); /*只考虑正常的多边形，边数>=3*/
269
270 double minx = py.pts[0].x;
271 double maxx = py.pts[0].x;
272 double miny = py.pts[0].y;
273 double maxy = py.pts[0].y;
274 for(int i = 1; i < py.GetPolyCount(); i++)
275 {
276 if(py.pts[i].x < minx)
277 minx = py.pts[i].x;
278 if(py.pts[i].x > maxx)
279 maxx = py.pts[i].x;
280 if(py.pts[i].y < miny)
281 miny = py.pts[i].y;
282 if(py.pts[i].y > maxy)
283 maxy = py.pts[i].y;
284 }
285
286 rc = Rect(minx, miny, maxx, maxy);
287 }
除了扫描线法，还可以通过多边形边的法矢量方向、多边形面积以及角度和等方法判断点与多边形的关系。但是这些算法要么只支持 凸多边形，要么需要复杂的三角函数运算（多边形边数小于44时，可采用近似公式计算夹角和，避免三角函数运算），使用的范围有限，只有扫描线法被广泛应 用。
至此，本文的内容已经完结，以上通过对点与矩形、点与圆、点与直线以及点与多边形位置关系判断算法的讲解，向大家展示了几种常见的计算几何算法实现，用简短而易懂的代码剖析了这些算法的实质。下一篇将介绍计算机图形学中最基本的直线生成算法。
参考资料：
【1】计算几何：算法设计与分析 周培德 清华大学出版社 2005年
【2】计算几何：算法与应用 德贝尔赫（邓俊辉译） 清华大学出版社 2005年
【3】算法导论 Thomas H.Cormen等（潘金贵等译） 机械工业出版社 2006年
【4】计算机图形学 孙家广、杨常贵 清华大学出版社 1995年