网站的规划建设如何布局,wordpress 163,镇江市住房和城乡建设局网站,广告图片怎么制作文章版权由作者李晓晖和博客园共有#xff0c;若转载请于明显处标明出处#xff1a;http://www.cnblogs.com/naaoveGIS/。 1.背景 判断点面关系的算法有很多#xff0c;在我之前的博文中有一篇专门对其进行了描述#xff1a;判断点是否落在面中的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/ 如果您觉得本文确实帮助了您可以微信扫一扫进行小额的打赏和鼓励谢谢 ^_^ 转载于:https://www.cnblogs.com/naaoveGIS/p/5148185.html
