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

文章版权由小编李晓晖和今日头条共有,若转发请于明显处标明出处:http://www.cnblogs.com/naaoveGIS/

1.背景

判定点面关系的算法有无数,在自己事先的博文中有一篇更加对其展开了描述:判断点是还是不是落在面中的Oracle存储进度描述。其中涉及了两种普遍判断点面关系的算法:

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

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

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

可是上述直接判断点面关系的算法,其时间复杂度是对峙很高的。假使一个面有N个点,那么判断1个点与该面的关系所急需费用的时辰为:N*N。

此地,我要跟我们谈论的是一种以数学公式为内核,通过树立高效的空间索引来火速增进点面关系判断的算法。

2.算法模型

2.1命题

   图片 1                    

如图,有AB四个多边形,要求看清P点是落在哪些多边形?

2.2思路

确立覆盖了A、B多边形的格网,每个格网中带有了其属于怎么多边形的切切实实音讯。判断点与面的关系时,首先取得那些点落在哪些格网,然后拿走该格网隶属于哪多少个多变形。比如以上的P点,大家收获到P点所在的格网隶属于多个多边形A和B。最终调用点面关系算法,判断点P和面A、B之间的涉及。

 

2.3建模流程图

 图片 2

           

 

3.索引生成具体方法

扭转的目录分为多边形音信索引和网格索引八个,上面分别讲述。

3.1生成多边形新闻索引

多边形音信索引中隐含了三部分音讯:属性信息、几何新闻、音讯大小。具体完成流程如下:

 图片 3

 

3.2生成网格索引

网格索引中隐含那样两类信息:网格编号、网格隶属于的多方面形具体音讯(多边形编号、多边形标识)。具体贯彻流程如下:

 图片 4

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

那里一贯交给完毕流程图:

 图片 5

 

 

5.优点

a.该算法幸免了判断点属于哪个多边形时,要将持有多边形都遍历三遍,升高了频率。

b.当点所在网格只含有于一个多边形时,此时连点面具体涉及判断都能幸免,进一步进步了效用。

c.多边形音信索引文件中得以包蕴该多边形的质量音讯,在点面关系判断成功后,仍能领到到该多边形的习性新闻,幸免了对地理服务器的依赖。

 

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

                                                                          
假若您觉得本文确实支持了你,可以微信扫一扫,举行小额的打赏和鞭策,谢谢
^_^

                                                图片 6

 

相关文章