文章版權由作者李曉暉和博客園共有，若轉載請于明顯處標明出處：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

總結

以上是生活随笔為你收集整理的WebGIS中一种根据网格索引判断点面关系的方法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。