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

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

本文将介绍如何使用C语言实现射线法，判断一个点是否在给定的多边形内。

算法原理

射线法是一种常用的判断点是否在多边形内的算法。其基本思想是：从该点出发，向任意方向画一条射线，统计该射线与多边形边界的交点个数。如果交点个数为奇数，则该点在多边形内；否则，该点在多边形外。

C语言代码实现

#include <stdio.h>

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

typedef struct {
    Point start;
    Point end;
} Line;

int isIntersect(Line l1, Line l2) {
    double x1 = l1.start.x, y1 = l1.start.y;
    double x2 = l1.end.x, y2 = l1.end.y;
    double x3 = l2.start.x, y3 = l2.start.y;
    double x4 = l2.end.x, y4 = l2.end.y;

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

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

    if (t >= 0 && t <= 1 && u >= 0 && u <= 1) {
        return 1;
    } else {
        return 0;
    }
}

int isInside(Point p, Line* edges, int n) {
    int count = 0;

    Line ray = {p, {9999, p.y}};
    for (int i = 0; i < n; i++) {
        if (isIntersect(ray, edges[i])) {
            count++;
        }
    }

    if (count % 2 == 1) {
        return 1;
    } else {
        return 0;
    }
}

int main() {
    Point p = {1, 1};
    Line edges[] = {{{0, 0}, {2, 0}}, {{2, 0}, {1, 1}}, {{1, 1}, {2, 2}}, {{2, 2}, {0, 2}}, {{0, 2}, {0, 0}}};
    int n = sizeof(edges) / sizeof(edges[0]);

    if (isInside(p, edges, n)) {
        printf('Point is inside the polygon.\n');
    } else {
        printf('Point is outside the polygon.\n');
    }

    return 0;
}

示例

以下代码判断点 (2, 1) 是否在由以下顶点组成的多边形内：

{{0, 0}, {2, 0}}, {{2, 0}, {1, 1}}, {{1, 1}, {2, 2}}, {{2, 2}, {0, 2}}, {{0, 2}, {0, 0}}

运行代码，输出结果为：

Point is inside the polygon.

总结

本文介绍了使用C语言实现射线法判断点是否在多边形内的方法，并提供了完整的代码示例。该方法简单易懂，且易于扩展，适合用于各种几何算法的开发。