计算几何是计算机科学的一个重要分支,主要研究几何形体的数学描述和计算机描述,在现代工程和数学领域,以及计算机辅助设计、地理信息系统、图形学、机器人技术、超大规模集成电路设计和统计等诸多领域都有重要的用途。在 ACM 竞赛中,出题相对独立,曾出现过与图论、动态规划相结合的题,大多数计算几何问题用程序实现都比较复杂。常用算法包括经典的凸包求解、离散化及扫描线算法、旋转卡壳、半平面交等。本文介绍计算几何常用算法——包含关系。

01、实例应用：飞行员

问题描述:

在第二次世界大战中，一个飞行员由于飞机没油被强迫降落，飞机降落的地点固定在坐标系中的（0，0）点。但是，敌人在地面上修筑了一些多边形的包围区。如果飞行员降落在包围区外，他就是安全的。当飞行员降落在包围区内，他必须知道一种密码口令，才能通过包围区。飞行员不可能降落在多边形的边上。这种密码是，给出两个不同的质数p、q，密码就是不能用px+qy形式表示的正整数的个数，其中x、y为大于或等于0的整数。比如，p=3，q=5，则有4个正整数1、2、4、7不能用其表示，因此密码口令为4。
输入:

输入有多组测试数据，每组数据的第一行是一个数n（3≤n≤16），表示包围区的顶点的个数。当n=0时表示输入结束。接下来有n行，每行有两个实数，用来表示顶点的坐标，顶点是按照顺时针或逆时针给出的。再接下来的一行是p q。

输出:

首先输出测试数据的编号，第二行输出飞行员是否在包围区内，如果在包围区内，第三行输出密码口令。

输入样例:

4
-1.0 -1.0
2.0 -1.0
2.0 2.0
-1.0 2.0
3 5
5
-2.5 -2.5
10.5 -2.5
10.5 -1.5
-1.5 -1.5
-2.5 20.5
2 7
0

输出样例:

Pilot 1
The pilot is in danger!
The secret number is 4.
Pilot 2
The pilot is safe.

解题思路:

采用水平/垂直交叉点数判别法确定点是否在多边形内时，如果P在多边形内部，那么这条射线与多边形的交点必为奇数;如果P在多边形外部，则交点个数必为偶数（0也在内）。假如考虑边（P1, P2），如果射线正好穿过P1或者P2,那么这个交点会被算作2次，这样就有如下一些特殊处理:

(1) （P1在射线上）P0和P2在L的异侧算作交一次。

(2) （P1和P2都在射线上）P0和P3在射线的异侧算作交一次。

参考程序:

#include< stdio.h>
# include< stdlib.h>
# include< string.h>
#include<math.h>
# define MaxNode 51
# define INE 999999999
struct TPoint
//点
double x;
double y;
struct TSegment
//线
i
TPoint pl;
TPoint p2;
struct TPolygon
//多边形
TPoint point[MaxNodel;
int n;
double multi(TPoint p1,TPoint p2,TPoint p0)
//求矢量 P。P、P。P的叉积return (Pi.X- Po.x) * ( P .y- Po.y)- ( P.X-P.x) * ( P.y- Po.y);//若结果等于 0,则这三点共线
//若结果大于 0,则 P。P2 在 P。P 的逆时针方向
//若结果小于 0,则 P。P,在 P。Pi 的顺时针方向
double max(double x,double y)
if(x>y) return x;
else return y;
double min(double x,double y)
if(x<y) return x;
else return y;
//判断线段是否相交bool Intersect(TSegment L1,TSegment I2)
//若线段 L1 与 L2 相交而且不在端点上，则返回 true
//判断线段是否相交
//1.快速排斥试验,判断以两条线段为对角线的两个矩形是否相交//2.跨立试验
TPoint s1=L1.p1;
TPoint e1=L1.p2;
TPoint s2=L2.p1;
TPoint e2=L2.p2;
if(
(max(s1.x,e1.x)>min(s2.x,e2.x)) &&
(max(s2.x,e2.x)>min(s1.x,e1.x)) &&(max(s1.y,el.y) >min(s2 .y,e2 .y) ) &&(max(s2 .Y,e2 .y) >min(sl.y,e1.y) ) &&(multi(s2,e1,s1) *multi(el,e2,s1) > 0) &&(multi(s1,e2,s2) *multi(e2,e1,s2) > 0)
return true;
return false;
bool Online(TSegment L,TPoint p)
//判断点 P 是否在直线上
//若 p在 L上(不在端点)，则返回 true
//1.p 在L所在的直线上
//2.p 在以 L为对角线的矩形中
double dx,dy,dx1,dyl;
dx=L.p2.x-L.p1.x;
dy=L.p2 .y-L.1.y;
dx1=p.x-L.p1.x;
dy1=p.y-L.p1.y;
//若不返回，则说明 p 在直线上if(dx * dy1-dy*dx1!=0) return false;if(dx1* (dxl-dx)<0 dyl* (dyl-dy)<0) return true;
//进一步确定 p在射线 上
return false;
//判断 p1、p2 是否在工的同侧，若在同侧bool same(TSegment L,TPoint p1,TPoint p2)//则返回 true
if(multi(pl,L.p2,L.pl) * multi(L.p2,p2,L.pl)< 0) return true;return false;
bool Inside(TPoint q,TPolygon polygon)
//判断 q 点是否在多边形内
int c,i;
 头
相交一次的情况有
1.线段 P。P 和工相交且交点不为端点
2.(Pi 在射线上) P。和 P在 L的异侧算作交一次
3.( P 和 P都在射线上) P。和 P:在射线的异侧算作交一次
TSegment I1,L2;
C=0;
L1.p1=q;
I1.p2=q;
L1.p2.X=INF;
for(i=0;i<polygon.n;i++)
L2.p1=polygon.point[il;
L2.p2=polygon.point[(i+1)polygon.n];
//提前判断点是否在多边形的边上，因为本题有，所以不需要//if(Online(L2,q))
// return true;
if(Intersect(L1,I2))
//L1 和 L2 相交且不在端点上
C++;
continue;
if(!Online(L1,polygon.point[(i+1)%polygon.n]))continue;if(!Online(Ll,polygon.point[(i+2)polygon.n]))//p[i+1]在直线上,p[i]和 p[i+2]在L的异侧&&!same(Ll,polygon.point[il,polygon.point[(i+2)%polygon.n]))
C++;
continue;
if(Online(Ll,polygon.point[(i+2)%polygon.n])//p[i+1]和 p[i+2]都在直线上,p[i]和 p[i+3]在工的异侧&&!same(Ll,polygon.point[il,polygon.point[(i+3)polygon.n]))
C++;
if(c号2==0)return false;
else return true;
int main()
int i, test,k;int primp，primq;TPoint p;p.x= 0;p.y = 0;test =攸袄崩备胺保惠卞1;
//构造待测点
TPolygon polygon;while(scanf("d",&polygon.n)!=EOF)
if(polygon.n==0)
break;
for(i=0;i<polygon.n;i++)
scanf("%lf%lf",&polygon.point[il.x,&polygon.point[il.y);scanf("d%d",&primp,&primq);printf("Pilot d\n",test);
test++ ;
if(Inside(p,polygon))
//当(0,0) 点在多边形内
printf("The pilot is in danger! n") ;
k=(primp-1) * (primq-1) /2;
//不能用 xp+yg 表示的整数个数，找规律可得
printf("The secret number is d. n",k) ;
else printf("The pilot is safe. n") ;
printf("\n") ;
return 0;