笔者在工作过程中遇到一个场景,需要批量判断点是否位于某个多边形,搜索了几个算法,发现过于复杂,本身理解就有困难,编成代码就更难了。
主流算法:
(1)面积和判别法:判断目标点与多边形的每条边组成的三角形面积和是否等于该多边形,相等则在多边形内部。
(2)夹角和判别法:判断目标点与所有边的夹角和是否为360度,为360度则在多边形内部。
(3)引射线法:从目标点出发引一条射线,看这条射线和多边形所有边的交点数目。如果有奇数个交点,则说明在内部,如果有偶数个交点,则说明在外部。
具体做法:将测试点的Y坐标与多边形的每一个点进行比较,会得到一个测试点所在的行与多边形边的交点的列表。在下图的这个例子中有8条边与测试点所在的行相交,而有6条边没有相交。如果测试点的两边点的个数都是奇数个则该测试点在多边形内,否则在多边形外。在这个例子中测试点的左边有5个交点,右边有三个交点,它们都是奇数,所以点在多边形内。
一个偶然的机会想起了之前圈网格内站点的方法,感觉可以试试,便按照这个思路搞了一下,结果成功了。
操作步骤:
1、mapinfo中打开多边形图层;
2、mapinfo中打开点图层;
3、查询->SQL查询,参考下图进行设置
Layer4G 是点图层
Buildings 是面图层
该查询的意思是获取“点位于多边形中的元素”,点击确定,查询完毕后返回一张表格;
4、表->导出,选择刚才的查询结果 query,保存类型选择 csv,
5、字符集按照下图设置
至此,便得到了点和多边形汇聚后的表,如果该点位于多边形内,则会出现一条记录,否则,不出现。
其实,我脑海里还有一个算法,只是无法用代码实现,如果你可以用代码实现,欢迎告诉我。
另外的算法:
1、将点设置为红色;
2、将多边形设置为黑色;
3、查询点的颜色,黑色则说明位于多边形内,红色则说明位于多边形外。