WebGIS中平等种植根据网格索引判断点面关系之法门

章版权由作者李晓晖与博客园共有,若转载请给大庭广众处于标明出处:http://www.cnblogs.com/naaoveGIS/。

1.背景

认清点面关系的算法来众多,在自事先的博文被出平等篇专门针对其开展了叙:判断点是否获得于面中的Oracle存储过程描述。其中涉嫌了三栽常见判断点面关系的算法:

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

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

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

而是上述直接判断点面关系之算法,其日复杂度是相对很高之。假设一个面有N个点,那么判断1单点与该面的关联所欲花费的光阴啊:N*N。

此,我要同大家谈谈的凡一律种为数学公式为本,通过树立高效之空间索引来快速提高点面关系判断的算法。

2.算法模型

2.1命题

   Oracle 1                    

万一图,有AB两独多边形,需要看清P点是获取于谁多边形?

2.2思路

成立覆盖了A、B多边形的格网,每个格网中含了彼属于怎么多边形之切切实实信息。判断点及照之涉经常,首先取得这个点落在谁格网,然后拿走该格网隶属于哪几独多变形。比如以上的P点,我们获取到P点所在的格网隶属于片独多边形A和B。最后调用点面关系算法,判断点P和面A、B之间的关系。

 

2.3盖模流程图

 Oracle 2

           

 

3.索引生成具体方法

变化的目分为多边形信息索引和网格索引两个,下面分别讲述。

3.1深成多边形信息索引

多边形信息索引中隐含了三片信息:属性信息、几哪里信息、信息大小。具体贯彻流程如下:

 Oracle 3

 

3.2生成网格索引

网格索引中含有这样简单类消息:网格编号、网格隶属于的绝大部分形具体信息(多边形编号、多边形标识)。具体实现流程如下:

 Oracle 4

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

此间一直吃有实现流程图:

 Oracle 5

 

 

5.优点

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

b.当点所在网格只包含于一个多方形时,此时并点面具体涉及判断还能够免,进一步提高了效率。

c.多边形信息索引文件被得分包该多边形的特性信息,在点面关系判断成功后,还能取到拖欠多边形的性信息,避免了针对地理服务器的依赖性。

 

                                                                      
 —–欢迎转载,但保留版权,请为大庭广众处于标明出处:http://www.cnblogs.com/naaoveGIS/

                                                                          
如果您当本文确实帮了卿,可以微信扫一扫,进行小额的打赏和鞭策,谢谢
^_^

                                                Oracle 6

 

相关文章