Home > TaiBIF > 多邊形檢索探討-使用Point in polygon演算法

多邊形檢索探討-使用Point in polygon演算法

October 20th, 2010

很多的朋有再問「究竟TaiBIF上的多邊形檢索是怎麼作」?在這一篇文章中,就來說明其中的關鍵作法。

傳統上多邊形檢索在一般的GIS軟體中,並不是一個特別的功能,幾乎所有的GIS軟體都會提供這樣的功能,大家用久了自然也就覺得好像不是一個特別的技術。但在Google Map中並沒有提供所謂多邊形檢索,因此要達成這樣的目的,必須多花一些功夫,重新探討與瞭解GIS軟體中多邊形檢索的原理。

早期的TaiBIF的空間檢索功能,先利用一個JavaScript的功能,當使用者任意框選Google Map上任一個地區,會將這個矩形的框框的左下與右上(座標的最大值與最小值)傳到資料庫中進行檢索,再回傳符合這個區塊的資料。

矩形檢索
這樣的做法,大概只需具備JavaScript及SQL語法的查詢,應該不難作出來。

但如果矩形並成下面這些,或甚至更複雜,剛剛的方法是否還有效果,也許還可用SQL語法進行檢索,但我想那一串SQL應該會非常的複雜。

不同的多邊形

因此,這時候就必須靠Point in polygon演算法。而透過這個演算法就可判斷究竟哪些點有被多邊形包圍,那些不在多邊形內。而這個演算法主要概念為計算任一點往任一方向與多邊形相交的次數,若為偶數則此點落於多邊形之外,相反的若為奇數則表示點在多邊形之內。用下面的圖說明,大家應該就會很快的瞭解這是什麼意思。

(a):交點共一點,所以在多邊形內

(b):交點共五點,所以在多邊形內

(c):交點共三點,所以在多邊形內

(d):交點共兩點,所以在多邊形外

用這樣的方法,就可以逐一計算出多邊形包含哪些點。下面的實際例子,我們就可計算出「太魯閣國家公園」內所有的採集紀錄,並且搭配原先的不同網格呈現。

Comments are closed.