WebGIS中一种根据网格索引判断点面关系的方法

简介: 文章版权由作者李晓晖和博客园共有,若转载请于明显处标明出处:http://www.cnblogs.com/naaoveGIS/。 1.背景 判断点面关系的算法有很多,在我之前的博文中有一篇专门对其进行了描述:判断点是否落在面中的Oracle存储过程描述。

文章版权由作者李晓晖和博客园共有,若转载请于明显处标明出处:http://www.cnblogs.com/naaoveGIS/

1.背景

判断点面关系的算法有很多,在我之前的博文中有一篇专门对其进行了描述:判断点是否落在面中的Oracle存储过程描述。其中提到了三种常见判断点面关系的算法:

a差乘判别法(只针对凸多边形)

b.面积判别法(只针对凸多边形)

c.角度和判别法等(任意多边形均可)

但是以上直接判断点面关系的算法,其时间复杂度是相对很高的。假设一个面有N个点,那么判断1个点与该面的关系所需要花费的时间为:N*N。

这里,我要跟大家讨论的是一种以数学公式为内核,通过建立高效的空间索引来快速提高点面关系判断的算法。

2.算法模型

2.1命题

                       

如图,有AB两个多边形,需要判断P点是落在哪个多边形?

2.2思路

建立覆盖了A、B多边形的格网,每个格网中包含了其属于哪些多边形的具体信息。判断点与面的关系时,首先获得这个点落在哪个格网,然后获取该格网隶属于哪几个多变形。比如以上的P点,我们获取到P点所在的格网隶属于两个多边形A和B。最后调用点面关系算法,判断点P和面A、B之间的关系。

 

2.3建模流程图

 

           

 

3.索引生成具体方法

生成的索引分为多边形信息索引和网格索引两个,下面分别描述。

3.1生成多边形信息索引

多边形信息索引中包含了三部分信息:属性信息、几何信息、信息大小。具体实现流程如下:

 

 

3.2生成网格索引

网格索引中包含这样两类信息:网格编号、网格隶属于的多边形具体信息(多边形编号、多边形标识)。具体实现流程如下:

 

4.利用索引判断点面关系具体方法

这里直接给出实现流程图:

 

 

 

5.优点

a.该算法避免了判断点属于哪个多边形时,要将所有多边形都遍历一遍,提高了效率。

b.当点所在网格只包含于一个多边形时,此时连点面具体关系判断都能避免,进一步提高了效率。

c.多边形信息索引文件中可以包含该多边形的属性信息,在点面关系判断成功后,还能提取到该多边形的属性信息,避免了对地理服务器的依赖。

 

                                                                        -----欢迎转载,但保留版权,请于明显处标明出处:http://www.cnblogs.com/naaoveGIS/

                                                                           如果您觉得本文确实帮助了您,可以微信扫一扫,进行小额的打赏和鼓励,谢谢 ^_^

                                                

 

目录
相关文章
|
XML 消息中间件 JSON
VOS3000 AXB标志下的号码保护AXB功能!
准备工作: 可直接下拉最后查看实例。 开通阿里服务: 条件:您已经完成注册阿里云账号,并完成企业实名认证,具体操作请参见阿里云账号注册流程、企业实名认证。
1075 0
|
缓存 NoSQL 数据库
如何保证缓存(redis)与数据库(MySQL)的一致性
【说明】  对于热点数据(经常被查询,但不经常被修改的数据),我们可以将其放入redis缓存中,以增加查询效率,但需要保证从redis中读取的数据与数据库中存储的数据最终是一致的。本文基于“孤独烟”与“58沈剑”两位的文章,针对一致性的问题进行了汇总总结,两位的原文链接见文末。
25631 3
|
XML 前端开发 Java
怎样将MultipartFile和File互转
该文介绍了如何在Java开发中优雅地转换MultipartFile和File。MultipartFile是Spring框架用于接收上传文件的类,而File是操作系统文件的代表。文章提供了三种将MultipartFile转换为File的方法:使用`transferTo`方法、FileOutputStream和Java NIO。另外,还介绍了在测试场景下将File转换为MultipartFile,通过MockMultipartFile实现。
1240 1
|
弹性计算 运维 Kubernetes
阿里云轻量应用服务器与轻量容器服务简介与区别及收费标准参考
轻量应用服务器是深受个人和普通企业用户亲耐的一款轻量级云服务器产品,提供精品应用一键部署,支持一站式的域名、网站、安全、运维、应用管理等服务,极大优化搭建简单应用的体验,降低了入门级用户使用云计算产品的门槛。轻量容器服务是专为学生、个人开发者等用户打造的轻量级容器服务,帮助您在云上快速了解容器和Kubernetes(简称K8s)相关的基础概念和轻松进行入门实践。本文为大家介绍一下阿里云轻量应用服务器与轻量容器服务的区别以及收费标准,以供参考。
阿里云轻量应用服务器与轻量容器服务简介与区别及收费标准参考
|
11月前
|
存储 域名解析 监控
云上攻防:任意上传、域名接管与AK/SK泄漏
随着企业上云的趋势加剧,云安全成为新的焦点。本文探讨了云计算环境中的三大安全问题:任意上传、域名接管与AK/SK泄漏,分析了这些威胁的工作原理及防护措施,强调了数据保护和访问控制的重要性。通过阿里云等平台的实际案例,提供了具体的安全防范建议。
1353 2
云上攻防:任意上传、域名接管与AK/SK泄漏
|
10月前
|
搜索推荐 安全 UED
我店平台系统开发模式
在开发我店平台模式时,需明确平台定位与目标用户,设计符合需求的功能与界面。考虑商业模式,选择盈利方式,设计创新功能如社交分享、个性化推荐等,提升用户体验。注重界面简洁、操作便捷,确保技术稳定与安全。持续迭代优化,根据用户反馈调整完善,保持竞争力。
|
缓存 运维 Linux
保姆级python项目离线部署服务器教程只需这一篇就够了(建议收藏)
这篇文章提供了详尽的Python项目在离线Linux(CentOS)服务器上的部署教程。作者首先介绍了环境背景,强调了无网络环境和使用有网络的CentOS虚拟机准备安装包的重要性。教程分为两部分:外网环境搭建和内网离线安装。在外网环境中,包括下载Python 3.9.0安装包、传输至服务器、安装依赖包,并使用pip3下载项目所需依赖。内网安装则涉及依赖包的复制和Python环境的同样步骤。最后,作者分享了运行项目的命令,并总结了离线安装的整个流程,提醒读者注意可能出现的问题。
保姆级python项目离线部署服务器教程只需这一篇就够了(建议收藏)
|
SQL 前端开发 Java
java为什么要分为service层,dao层,controller层和Entity层等?
java为什么要分为service层,dao层,controller层和Entity层等?
828 0
|
负载均衡 网络协议 算法
云计算中的负载均衡技术,确保资源的平衡分配
云计算中的负载均衡技术,确保资源的平衡分配
1240 0
|
设计模式 Java uml
Java中23种面试常考的设计模式之适配器模式(Adapter)---结构型模式
Java中23种面试常考的设计模式之适配器模式(Adapter)---结构型模式
235 1