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

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

1.背景

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

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

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

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

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

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

2.算法模型

2.1命题

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

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

2.2思路

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

2.3建模流程图

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

3.索引生成具体方法

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

3.1生成多边形信息索引

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

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

3.2生成网格索引

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

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

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

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

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

5.优点

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

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

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

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

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

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

上一篇:小说爬虫强制绕过ssl验证


下一篇:每七本 你的生命有什么可能