c实现点在多边形内的判断

判断一个点是否在一个多边形内可以使用射线法或者点在多边形边界上的特殊情况进行判断。下面是一个基于射线法的实现，其中点P是否在多边形内部的判断依据是P水平向右发出的一条射线与多边形边的交点的个数。

#include <stdio.h>
#include <stdbool.h>

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

typedef struct {
    int n;          // 多边形的顶点数
    Point *points;  // 多边形的顶点坐标列表
} Polygon;

// 判断点是否在多边形内
bool isPointInPolygon(const Point *p, const Polygon *poly) {
    int i, j, count = 0;

    // 射线起点
    Point q = { -1e9, p->y };

    for (i = 0, j = poly->n - 1; i < poly->n; j = i++) {
        // 如果点在多边形边界上，则认为点在多边形内
        if ((p->x == poly->points[i].x && p->y == poly->points[i].y) ||
            (p->x == poly->points[j].x && p->y == poly->points[j].y)) {
            return true;
        }

        // 如果射线与多边形边有交点，则计数器加1
        if ((poly->points[i].y > p->y) != (poly->points[j].y > p->y) &&
            (p->x - poly->points[i].x) * (poly->points[j].y - poly->points[i].y) >
            (poly->points[j].x - poly->points[i].x) * (p->y - poly->points[i].y)) {
            count++;
        }
    }

    // 如果交点个数为奇数，则点在多边形内
    return count % 2 == 1;
}

其中，`Polygon` 结构体表示一个多边形，包含顶点数和顶点坐标列表。`Point` 结构体表示一个二维坐标点。`isPointInPolygon` 函数判断一个点是否在多边形内，返回值为 `true` 表示在内部，返回值为 `false` 表示在外部。