文章版权由作者李晓晖和博客园共有，若转载请于明显处标明出处：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/

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