C语言中实现点在多边形内算法

本文是一个C语言程序，用射线法判断一个点是否在多边形内。这是一个C语言的小算法的实现程序，本来不想放在这里。但是，当我自己想实现这样一个算法的时候，我想在网上找一个现成的，但是经过调查，没有一个符合需求的。对自己大学写的代码没有信心，决定再写一个放在这里，以飨读者。还要增加博客的点击量。

首先，如下定义点结构:

以下是引号片段:
/*顶点结构*/
Typedef Struct
{
Double X，Y；
} vertex _ t；

该算法中的多边形是指由一系列点组成的封闭的简单多边形。它的头点和尾点可以是也可以不是同一点(头点和尾点不一定是同一点)。这种多边形可以是任何形状，包括绝对直线上的多条边。因此，定义多边形结构如下:

下面是引用的片段:
/*顶点列表结构–Polygon */
Typedef结构
{
int num _ cities；/*列表中的顶点数*/
vertex _ t * vertex；/*顶点数组指针*/
} Vertex list _ t；

为了加快判别速度，先计算多边形的外接矩形(rect_t)，判断点是否落在外接矩形内。只有满足落在外接矩形内的条件的点才会进入下一次计算。所以介绍了rect_t，外包矩形的结构，点集外包矩形中的vertices_get_extent的方法，代码如下:

下面是加引号的片段:
/*包围矩形type */
typedef struct
{
doublemin _ x，min _ y，max _ x，max _ y；
} rect _ t；
/*获取顶点的范围*/
void vertices _ get _ extent(const vertex _ t * VL，int np，/* in vertices */
rect _ t * RC/* out extent */)
{
int I；
if(NP > 0){
RC-> min _ x = RC-> max _ x = VL[0]。x；rc->min_y = rc->max_y = vl[0]。y；
} else {
RC-> min _ x = RC-> min _ y = RC-> max _ x = RC-> max _ y = 0；/* =0 ?对于(i=1，没有顶点*/
}
；i
{
if(vl[i]。x < rc->min_x) rc->min_x = vl[i]。x；
if(vl[i]。y < rc->min_y) rc->min_y = vl[i]。y；
if(vl[i]。x > rc->max_x) rc->max_x = vl[i]。x；
if(vl[i]。y > rc->max_y) rc->max_y = vl[i]。y；
}
}

当一个点满足落在多边形包络矩形内的条件时，需要进一步确定该点(V)是否在多边形内(VL: NP)。本程序采用射线法。从待测点(V)的水平面画出一条射线B(v，W)，计算B与vl的交点个数，记为C，根据内奇外偶的原则(C为奇数，表示V在vl内，否则V不在vl内)，判断该点是否在多边形内。