问题描述

给出m个点，和一个多边形，求出在多边形内部的点的个数，在多边形顶点上点的个数，在多边形边上的顶点个数。

基本原理

点向某一方向发射射线，如果与多边形的交点个数为奇数，则点在多边形内；如果为偶数，则在多边形外。（点在多边形上的情况单独计算，不算做多边形内）

问题分解：

子问题1：假设一点C，过C作平行线，找出所有与多边形相交的点（排除点C为多边形顶点的特殊情况）。

1）取出多边形一条边<Pi,Pj>，判断C的y坐标在不在yi和yj之内（y和大的一端的值相等也算作在两点之内），在的话，C(x,y)与该边相交。设交点为C'，则C'的坐标为(x',y);

2）因为C'在这条边上，而这条边的斜率是确定的。通过斜率相同，我们可以求出点C'的横坐标x'，做法如下:

a.边<Pi,C'>斜率为(y-yi)/(x'-xi)

b.边<Pi,Pj>斜率为()/()

c.求得x' = 

3）把所有边遍历一遍，就可以求出所有点了。

子问题2：点C向某一方向发射射线，过C作该平行射线线，找出所有与多边形相交的点。

1）在子问题1的基础上，探讨。首先固定一个方向，假设点C向右发射射线（右边界上的点就会算作多边形外部，左边界上的点算作多边形的内部）。

2）若已经判断出C的y坐标在两点之间

3）则若x'（为C'横坐标），大于x（x为点C横坐标），那么C的射线与该边相交，相交点数加一。

（这也说明了点C在线段的左边，才能与线段相交）

子问题3：判断特殊情况，点C在多边形顶点上或点C在多边形边上

1）在子问题1,2的基础上：

若求得的y在两点之间

第一种情况，Pi和Pj是水平直线，点C在多边形上。

除去上一种情况，且x'和x相等就说明点C和点C'是同一点，可以断定点C在这条边上。这个时候如果算法假定向右发射射线，点在右边界上就会算作在多边形外部，因为上面说了只有x'>x时，才计数，在右边界上，只有一条边有点x'=x。而点在左边界上就会算作多边形内部。（画个图就清楚了）

若求得的y不在两点之间，等于其中某一个顶点的y坐标，则继续判断点C的x坐标是否和该顶点的x坐标相同，若相同则该点为多边形顶点。（也可以放在之前先行判断）

2）取出下一点，继续判断。

算法总结：

1）判断Pi,Pj是否是水平直线，若是，则在多边形上

2）判断点C坐标是否在顶点上，即和Pi或者Pj相同，若相同则在多边形上

3）判断点C的y坐标是否在两端点之间，若点C射线过顶点时，计上端点，即y值大的一端，算作在两端点之间

4）判断点C是否在C'的左侧，即x<x'时，计数加一

5）计数总数为奇数在多边形内部，否则在外部。

代码解析

【原问题代码】

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#define maxSize 100

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

typedef struct
{
	Point vex[maxSize];//顶点信息,按照逆序或者顺序存放，0和n号为第一个顶点，n-1号为最后一个顶点
	int n;//顶点个数
}Polygon;

//射线法判断点p是否在多边形内部，若在则返回1否则返回0
int Judge(Polygon g, Point p)
{
	//定义计数器
	int count = 0;

	//顺序取出多边形的顶点
	int i, j;
	for (i = 0; i < g.n; ++i)
	{
		j = i + 1;
		//若取出的边是水平的，且点p在这条边上，则点不在多边形内部
		if (g.vex[i].y == g.vex[j].y)
		{
			if (p.y == g.vex[i].y)
				return 0;
		}
		else
		{
			//若点p在取出的顶点上，同样不算作在多边形内部
			if ((g.vex[i].x == p.x && g.vex[i].y == p.y) || (g.vex[j].x == p.x && g.vex[j].y == p.y))
			{
				return 0;
			}

			//若点p在两端点的y值之间，规定方向向上的边包括开始点，不包括其终止点，方向向下的边不包括开始点，包括其终止点
			if ((p.y >=
g.vex[i].y && p.y < g.vex[j].y) || (p.y >= g.vex[j].y && p.y < g.vex[i].y))
			{
				double x1;//x1为点p水平线与边<i,j>的交点横坐标

				x1 = (g.vex[j].x - g.vex[i].x)*(p.y - g.vex[i].y) / (g.vex[j].y - g.vex[i].y) + g.vex[i].x;

				//若p在边的左侧，则计数
				if (p.x < x1)
				{
					count++;
				}
				
				//若点p在取出的边上，即点在右边界或左边界上，也可以不要这个判断，则限定左边界在内部，右边界在外部
				if (p.x == x1)
				{
					return 0;
				}
			}
		}
	}

	//若点p向右发射的射线与多边形边的交点个数为偶数则点p在多边形的外部，否则在内部
	if (count % 2 == 0)
		return 0;

	return 1;
}




int main()
{
	Polygon g = { {{-3,-3},{3,-3},{3,3},{-3,3},{-3,-3}},{4} };
	Point p = { -1,1};

	int flag = Judge(g, p);

	if (flag)
		printf("点在多边形内部");
	else
		printf("点在多边形外部");


	return 0;
}

测试结果：

 

关注我获取更多编程方面的知识，和我共同进步吧~