当前位置：网站首页>如何判断点是否在多边形内(包含复杂多边形或者多边形数量很多的情况)

如何判断点是否在多边形内(包含复杂多边形或者多边形数量很多的情况)

2022-04-23 06:24:00 【0zien0】

  我们采用射线判断法判断点是否在多边形内，这个点任意一个方向发出一条射线，如果和多边每条边的交点总数为奇数则在多边形内部，为偶数，则在多边形外部。
在这里插入图片描述

  那如果在平面上有几千、几万、几十万个多边形，需要判断点是否落在其中一个多边形内呢？如果需要对无数的多边形每条边都判断是否相交，效率极其低下。我们采用RTree来简化这个复杂的过程。
1.我们首先把每个多边形都换算出他们的外接矩形。
在这里插入图片描述
2.然后把地图上所有多边形的外接矩形进行区域划分。
在这里插入图片描述
3.根据划分好的区域建立RTree。
在这里插入图片描述
最后就是根据RTree搜索出与射线相交的矩形区域，再判断点是否落在矩形区域的多边形内即可。 简历RTree后，只需小数几次判断，就可以快速计算出好点落在哪个多边形内，即使多边形的数量庞大。
在这里插入图片描述

  那如果单个多边形本身就极其复杂，由几千、几万、几十万条边构成呢？不就意味着单个多边形也需要判断无数次射线与边是否相交？ 答案显然是否定的，我们依然是用RTree来解决这一问题。
原理其实和上面的方法基本一致，只是上面是把一个多边形换算成一个矩形再分区域，这里是把一条边换算成一个矩形来分区域。就不细说过程了，上图完事……
在这里插入图片描述

参考文章：https://www.cnblogs.com/LBSer/p/4471742.html

版权声明
本文为[0zien0]所创，转载请带上原文链接，感谢
https://blog.csdn.net/a42626423/article/details/103615599

边栏推荐

猜你喜欢

随机推荐