polygon

最近在工作中用到了这个算法，抽空做一个笔记。 判断一个点是否在多边形内部的问题在很多地方都会碰到，最常用的方法就是射线法。 射线法 以点P为端点，向左方作射线L，由于多边形是有界的，所以射线L的左端一定在多边形外，考虑沿着L从无穷远处开始自左向右移动，遇到和多边形的第一个交点的时候，进入到了多边形的内部，遇到第二个交点的时候，离开了多边形，…… 所以很容易看出当L和多边形的交点数目C是奇数的时候，P在多边形内，是偶数的话P在多边形外。 特殊情况 射线穿过多边形的顶点。 这个时候，这个顶点会被计算两次，这显然是不正确的。 解决方法是在射线上的顶点只在计算一次。为了达到这个目的，这里定义只有当一条边的一个端点在射线的下方，另一个端点在射线上或者射线的上方，我们才认为这条边与射线相交。这样一来，b边由于两个端点都在射线上或者在射线上方，因此被认为与射线不相交，而a边则与射线相交，那么这个顶点最终被计算了一次。 多边形的一条边在射线上。 这时候我们参照上面第一种情况的方法，可以得出d边和e边都被认为与射线不相交，而c边与射线相交。这样c边和d边中间的顶点只被统计了一次，此时也可以得出点在多边形内的正确结论。 其他情况。 这是另外两种特殊的情况，可以看到我们参照上面的计算方法，依然可以得出正确的结论。 给定的点在多边形的边上。 在这种情况下，射线法的结果是不确定的，可能得到的结果是点在多边形内也可能是点在多边形外。可以根据实际的应用要求在实现算法中先判断点是否在多边形的边上。 算法实现 C代码例子： // Globals which should be set before calling this function: // // int polySides = how many corners the polygon has // float polyX[] = horizontal coordinates of corners // float polyY[] = vertical coordinates of corners // float x, y = point to be tested // // (Globals are used in this example for purposes of speed....