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 x = ((x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)) / d;
    double y = ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)) / d;

    // 判断交点是否在线段范围内
    if (x < l1.start.x || x > l1.end.x || x < l2.start.x || x > l2.end.x) {
        return 0; 
    }

    // 排除交点为端点的情况
    if (x == l1.start.x && y == l1.start.y) {
        return 0; 
    }

    // 确保交点在射线的下方，多边形边的上方
    if (y > l1.start.y && y > l1.end.y) {
        return 0; 
    }

    if (y < l2.start.y && y < l2.end.y) {
        return 0; 
    }

    return 1;
}

// 判断点是否在多边形内
int isInsidePolygon(Point p, Point polygon[], int n) {
    Line ray = {p, {p.x + 1e9, p.y}}; // 构造水平向右的射线
    int count = 0;
    for (int i = 0; i < n; i++) {
        Line side = {polygon[i], polygon[(i + 1) % n]};
        if (isIntersect(ray, side)) {
            count++;
        }
    }
    return count % 2 == 1; // 奇数个交点在多边形内
}

int main() {
    Point p = {1, 1};
    Point polygon[] = {{0, 0}, {0, 2}, {2, 2}, {2, 0}};
    int n = sizeof(polygon) / sizeof(polygon[0]);
    printf('%d\n', isInsidePolygon(p, polygon, n)); // 输出1，表示点在多边形内
    return 0;
}

示例

上述代码定义了一个点 p(1, 1) 和一个多边形 polygon，并调用 isInsidePolygon 函数判断点 p 是否在多边形内部。最终输出结果为1，表示点 p 在多边形内部。

总结

本文介绍了使用C语言实现射线法判断点在多边形内的算法，并提供了详细的代码实现和示例。该算法简单易懂，实现方便，是判断点与多边形关系的常用方法。