如何判断点是否在多边形内部 (C语言版)

概述

这是图形学中的一个经典问题（point-in-polygon），一种比较简易的判断方法是射线法，就是以判断点作为端点，朝着任意方向绘制一条射线。如果射线与多边形交点为奇数个，就说明此点在多边形内部。如果交点为偶数个，就说明此点在多边形外部。严格证明的话可以在网上根据关键词自行搜索，这里只是解释下这种方法，还有代码实现。

细节思考

交点奇数个在内部，偶数个在外部，虽然表述起来比较简单，但是这里还有细节条件需要约束，比如下面这三种情况。

A，B，C 三条射线都只跟多变形有一个交点，但是显然只有点 C 的端点在内部。这里的问题就在于，当射线跟多边形的顶点有交点时需要怎么计算？
虽然射线的方向可以任意，但我们平时为了计算方便，可以采用水平射线正方向，然后条件就是: 交点的 Y 坐标，需要大于线段的一其中个端点，小于等于另一个端点。 换成形象一点的理解方式就是，在射线"下面"的线段才会被计算，所以按照这种规则就是，A 算两个交点，B 算一个交点，C 没有交点，所以只有 C 在内部。

除此之外还有一种重合的情况，就是射线跟多边形的一条边重合了，其实按照上面的规则看，这种情况也属于没有交点。

代码实现

最后就是代码实现了，这里贴个 C语言 版的。

#include <stdio.h>

typedef struct
{
    float x;
    float y;
} Point;

// 多边形点坐标， 多边形点个数， 需要判断的点
int isInner(Point *poly, int num, Point p)
{
    int flag = 0, i;
    for (i = 0; i < num; i++)
    {
        // 多边形的边的两个点 p1, p2
        Point p1 = poly[i];
        Point p2 = poly[(i + 1) % num];
        // 点的 Y 坐标一个大于等于，一个小于
        if (p.y >= p1.y && p.y < p2.y || p.y >= p2.y && p.y < p1.y)
        {
            // 交点计算，两点式
            float x = (p.y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y) + p1.x;
            // 交点 X 坐标肯定在前
            if (x > p.x)
            {
                flag++;
            }
        }
    }
    return flag % 2;
}

#define SIZEOF(T) (sizeof(T)/sizeof(T[0]))

int main()
{
    Point a = {2, 3};
    Point b = {3, 2};
    Point c = {2, 1};
    Point d = {-1, 0};
    Point qz[] = {
        {0, 0}, {3, 3}, {5, 2}, {4, 2}, {4, -1}, {3, 1}, {2, -1}, {1, 0}
    };
    printf("a, %d\n", isInner(qz, SIZEOF(qz), a));
    printf("b, %d\n", isInner(qz, SIZEOF(qz), b));
    printf("c, %d\n", isInner(qz, SIZEOF(qz), c));
    printf("d, %d\n", isInner(qz, SIZEOF(qz), d));
    return 0;
}

运行结果

a, 0
b, 1
c, 1
d, 0

补充

代码中交点计算主要用到了两点式：

如果对速度有要求的话，在计算交点之前可以多加点判断，比如 A B 两条线，显然 A 是没有交点的，因为 A 的两个端点的 X 轴坐标都要比判断点的 X 轴坐标小，几次大小比较可能要比计算交点快，这个看情况优化吧。