C语言射线法判断点是否在多边形内

本文介绍如何使用C语言实现射线法，用于判断一个点是否位于给定多边形内部，并提供详细的代码示例和测试用例。

算法原理

射线法是一种常用的判断点与多边形关系的算法。其基本思想是从待判断点出发，向任意方向（通常为水平方向）发射一条射线，然后统计该射线与多边形边界的交点个数。

• 如果交点个数为奇数，则点在多边形内部；
• 如果交点个数为偶数，则点在多边形外部。

C代码实现

#include <stdio.h>

struct Point {
    double x;
    double y;
};

struct Segment {
    struct Point p1;
    struct Point p2;
};

// 判断两条线段是否相交
int isIntersect(struct Segment s1, struct Segment s2) {
    double x1 = s1.p1.x, y1 = s1.p1.y;
    double x2 = s1.p2.x, y2 = s1.p2.y;
    double x3 = s2.p1.x, y3 = s2.p1.y;
    double x4 = s2.p2.x, y4 = s2.p2.y;

    double d = (y2 - y1) * (x4 - x3) - (x2 - x1) * (y4 - y3);
    if (d == 0) {
        return 0;
    }

    double u = ((x3 - x1) * (y4 - y3) - (y3 - y1) * (x4 - x3)) / d;
    double v = ((x3 - x1) * (y2 - y1) - (y3 - y1) * (x2 - x1)) / d;

    if (u < 0 || u > 1 || v < 0 || v > 1) {
        return 0;
    }

    return 1;
}

// 判断点是否在多边形内
int isInside(struct Point p, struct Segment segments[], int n) {
    // 构造一条从该点向右的射线
    struct Segment ray = { p, {p.x + 1e10, p.y} };

    int count = 0;
    for (int i = 0; i < n; i++) {
        // 如果射线与多边形的某条边相交，则计数器加1
        if (isIntersect(ray, segments[i])) {
            count++;
        }
    }

    // 如果计数器为奇数，则点在多边形内，否则在多边形外
    return count % 2 == 1;
}

int main() {
    struct Segment segments[] = {
        { {0, 0}, {2, 0} },
        { {2, 0}, {1, 1} },
        { {1, 1}, {2, 2} },
        { {2, 2}, {0, 2} },
        { {0, 2}, {0, 0} }
    };
    int n = sizeof(segments) / sizeof(segments[0]);

    struct Point p = { 1, 1 };
    if (isInside(p, segments, n)) {
        printf('Point (%.1f, %.1f) is inside the polygon.\n', p.x, p.y);
    } else {
        printf('Point (%.1f, %.1f) is outside the polygon.\n', p.x, p.y);
    }

    return 0;
}

测试结果

运行上述代码，输出结果为：

Point (1.0, 1.0) is inside the polygon.

总结

本文介绍了如何使用C语言实现射线法判断点是否在多边形内，并提供了详细的代码示例和测试用例。该算法简单易懂，实现方便，可以广泛应用于游戏开发、图形学等领域。