当前位置:网站首页>How to judge whether a point is within a polygon (including complex polygons or a large number of polygons)
How to judge whether a point is within a polygon (including complex polygons or a large number of polygons)
2022-04-23 07:42:00 【0zien0】
We use the ray judgment method to judge whether the point is in the polygon , This point emits a ray in any direction , If the total number of intersections with each edge of the polygon is odd, it is inside the polygon , For the even , Outside the polygon .
If there are thousands on the plane 、 tens of thousands 、 Hundreds of thousands of polygons , Need to judge whether the point falls in one of the polygons ? If you need to judge whether each edge of countless polygons intersects , Extremely inefficient . We use RTree To simplify this complex process .
1. We first convert each polygon into its circumscribed rectangle .
2. Then divide the circumscribed rectangles of all polygons on the map into regions .
3. Establish a good area according to RTree.
Finally, according to RTree Search out the rectangular area intersecting the ray , Then judge whether the point falls in the polygon of the rectangular area . resume RTree after , Just a few decimals to judge , You can quickly calculate which polygon the good point falls in , Even if the number of polygons is huge .
If a single polygon itself is extremely complex , By thousands 、 tens of thousands 、 Hundreds of thousands of edges ? It doesn't mean that a single polygon also needs to judge whether the rays intersect the edges countless times ? The answer is clearly no , We still use RTree To solve this problem .
The principle is basically consistent with the above method , But the above is to convert a polygon into a rectangle and then divide the area , Here is to convert an edge into a rectangle to divide the area . I won't elaborate on the process , The picture above is finished ……
Reference article :https://www.cnblogs.com/LBSer/p/4471742.html
版权声明
本文为[0zien0]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204230623293902.html
边栏推荐
猜你喜欢
随机推荐
7. sub query
游戏辅助脚本开发之旅
LATEX公式注意事项
海康威视面经总结
数据分析入门 | kaggle泰坦尼克任务(三)—>探索数据分析
菜菜的并发编程笔记 |(五)线程安全问题以及Lock解决方案
P2257 YY的GCD(莫比乌斯反演)
Reflection on the systematic design of Android audio and video caching mechanism
3.排序语句
11.表和库的管理
[牛客练习赛68]牛牛的粉丝(矩阵快速幂之循环矩阵优化)
h5本地存储数据sessionStorage、localStorage
(扩展)BSGS与高次同余方程
On BFC (block formatting context)
王者荣耀-unity学习之旅
Date对象(js内置对象)
manjaro安装与配置(vscode,微信,美化,输入法)
页面实时显示当前时间
FSM有限状态机
Lead the industry trend with intelligent production! American camera intelligent video production platform unveiled at 2021 world Ultra HD Video Industry Development Conference