OracleWebGIS中一种依据网格索引判断点面关系的格局

小说版权由我李晓晖和搜狐共有,若转发请于鲜明处标明出处:http://www.cnblogs.com/naaoveGIS/

1.背景

看清点面关系的算法有众多,在自个儿事先的博文中有一篇专门对其进展了描述:判断点是或不是落在面中的Oracle存储进度描述。其中涉及了三种常见判断点面关系的算法:

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

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

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

只是上述直接判断点面关系的算法,其时间复杂度是相对很高的。如若2个面有N个点,那么判断2个点与该面的关系所要求成本的年月为: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.优点

Oracle,a.该算法避免了判断点属于哪个多边形时,要将全体多边形都遍历四遍,升高了频率。

b.当点所在网格只含有于三个多方形时,此时连点面具体涉及判断都能防止,进一步进步了成效。

c.多边形新闻索引文件中能够分包该多边形的性质音信,在点面关系判断成功后,还是可以领取到该多边形的习性音信,幸免了对地理服务器的倚重。

 

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

                                                                          
假诺你认为本文确实协理了您,可以微信扫一扫,进行小额的打赏和鼓励,谢谢^_^

                                                Oracle 6

 

相关文章