21在多边形 0 0 2 0 2 0 1 11 1 2 2 2 2 0 2 0 2 0 0 内吗？C语言射线法求解

以下是C语言的射线法实现：

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

#define N 5 // 多边形的边数 #define INF 10000 // 无限大

typedef struct { double x, y; } Point;

// 计算两点之间的距离 double distance(Point p1, Point p2) { return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)); }

// 判断两条线段是否相交 bool intersect(Point p1, Point p2, Point p3, Point p4) { double d1 = (p3.x - p1.x) * (p2.y - p1.y) - (p3.y - p1.y) * (p2.x - p1.x); double d2 = (p4.x - p1.x) * (p2.y - p1.y) - (p4.y - p1.y) * (p2.x - p1.x); double d3 = (p1.x - p3.x) * (p4.y - p3.y) - (p1.y - p3.y) * (p4.x - p3.x); double d4 = (p2.x - p3.x) * (p4.y - p3.y) - (p2.y - p3.y) * (p4.x - p3.x); return (d1 * d2 < 0) && (d3 * d4 < 0); }

// 判断点是否在多边形内 bool inside(Point p, Point polygon[]) { int cnt = 0; Point p1 = {p.x, INF}; // 构造射线 for (int i = 0; i < N; i++) { Point p2 = polygon[i], p3 = polygon[(i+1)%N]; if (intersect(p, p1, p2, p3)) { cnt++; } } return cnt % 2 == 1; }

int main() { Point polygon[N] = {{0, 0}, {2, 0}, {1, 1}, {2, 2}, {0, 2}}; Point p = {1, 1}; if (inside(p, polygon)) { printf("Point (%.2lf, %.2lf) is inside the polygon.\n", p.x, p.y); } else { printf("Point (%.2lf, %.2lf) is outside the polygon.\n", p.x, p.y); } return 0; }

输出结果为：

Point (1.00, 1.00) is inside the polygon