判断点是否在多边形内——转角法

简介射线法转角法原理算法

简介

今天在拜读南京师范大学张宏老师与温永宁老师的书籍《地理信息系统算法基础》时，收获了新的拓扑算法，所以在此记录一下。 在地理学中，探究两个几何对象，点与多边形的拓扑关系时，经常使用两种方法，分别是射线法与转角法，其中射线法更加常用。

射线法

在使用射线法进行点与多边形的拓扑关系判断时，有一个限定条件，即多边形必须是一个简单多边形，这个多边形必须是一个简单的闭合曲线所构成的，在多边形所在的平面中只有两个相互分离的部分，即多边形的外部与多边形的内部；且多边形没有自相交与自重叠； 如果出现了复杂的自重叠多边形，在某些多边形二次重叠的部分，射线法并不能很好的判断点是否在多边形内部，此时，就提出了另一种判断方法，转角法。

转角法

转角法，简单来说就是判断，多边形是否对点产生了环绕，累计在计算过程中的环绕数，如果环绕数为0，则在多边形外部，否则在多边形内部；

原理

设定多边形的边是具有方向的向量，总体是按逆时针方向，如图；

为了便于理解，同时也为了优化算法，将射线法的算法进行改写，依然从点引出一条向右的射线，但此时与射线法的区别在于，不再是对与多边形相交数的叠加，而是有加有减的计算； 当射线与方向向上的边相交时，环绕数加一；当射线与方向向下的边相交时，环绕数减一，如图所示，即可更好的判断点是否位于多边形内部。 如图，点A向右引出的射线经过了2-3，及8-9两个方向向上的边，没有经过方向向下的边，所以环绕数为2，可以判断点A在多边形内部； 以点B为端点的射线经过了2-3一个方向向上的边，6-7一个方向向下的边，所以环绕数为0，即可判断点B在多边形外部； 点C的射线只经过了2-3一个方向向上的边，所以环绕数为1，所以点C也在多边形内部；

算法

在转角法的算法中，我用自己定义的结构节点代表了多边形的顶点，并以链表的形式存储，在遍历边进行判断时，顶点号依次递增，并加入了判断边的方向的条件；算法仅供参考，若有错误，欢迎指正。

#include <stdio.h> #include <math.h> typedef struct node { int n; int x; int y; struct node *next; }; int main() { struct node t[10] = {0,0,0,NULL}; struct node *a = &t[0],*b; struct node p; int wn = 0; for (int i = 1;i < 10;i++) { a->next = &t[i]; a = a->next; } a->next = &t[0]; b = &t[1]; do{ if((p.x-a->x)*(b->y-a->y)==(b->x-a->x)*(p.y-a->y)&&min(a->x,b->x)<=p.x&&p.x<=max(a->x,b->x)&&min(a->y,b->y)<=p.y&&p.y<=max(a->y,b->y)) { if(b->y > a->y) { wn++; } else if (a->y > b->y) { wn--; } } a = a->next; b = b->next; }while (a->n == 0); if(wn == 0) { return 0; } else { return 1; } }