GIS點在多邊形內(nèi)算法

《GIS點在多邊形內(nèi)算法》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、1.判斷點在多邊形內(nèi)外的簡單算法--改進弧長法今天學圖形學的時候發(fā)現(xiàn)了一個求多邊形內(nèi)外的超簡單算法，當時覺得非常驚喜，后來晚上上完選修的時候在走廊遇到bug，bug也是很驚喜地感慨道：居然有甘簡單既辦法都捻唔到！遂將其寫下，供大家分享，希望不會太火星。???這個算法是源自《計算機圖形學基礎教程》（孫家廣，清華大學出版社），在該書的48-49頁，名字可稱為“改進的弧長法”。該算法只需O(1)的附加空間，時間復雜度為O(n)，但系數(shù)很小；最大的優(yōu)點是具有很高的精度，只需做乘法和減法，若針對整數(shù)坐標則完全沒

2、有精度問題。而且實現(xiàn)起來也非常簡單，比轉角法和射線法都要好寫且不易出錯。???首先從該收中摘抄一段弧長法的介紹：“弧長法要求多邊形是有向多邊形，一般規(guī)定沿多邊形的正向，邊的左側為多邊形的內(nèi)側域。以被測點為圓心作單位圓，將全部有向邊向單位圓作徑向投影，并計算其中單位圓上弧長的代數(shù)和。若代數(shù)和為0，則點在多邊形外部；若代數(shù)和為2π則點在多邊形內(nèi)部；若代數(shù)和為π，則點在多邊形上?！???按書上的這個介紹，其實弧長法就是轉角法。但它的改進方法比較厲害：將坐標原點平移到被測點P，這個新坐標系將平面劃分為4個象限

3、，對每個多邊形頂點P，只考慮其所在的象限，然后按鄰接順序訪問多邊形的各個頂點P，分析P和P[i+1]，有下列三種情況：（1）P[i+1]在P的下一象限。此時弧長和加π/2；（2）P[i+1]在P的上一象限。此時弧長和減π/2；（3）P[i+1]在Pi的相對象限。首先計算f=y[i+1]*x-x[i+1]*y（叉積），若f=0，則點在多邊形上；若f<0，弧長和減π；若f>0，弧長和加π。???最后對算出的代數(shù)和和上述的情況一樣判斷即可。???實現(xiàn)的時候還有兩點要注意，第一個是若P的某個坐標為0時，一律當

4、正號處理；第二點是若被測點和多邊形的頂點重合時要特殊處理。???以上就是書上講解的內(nèi)容，其實還存在一個問題。那就是當多邊形的某條邊在坐標軸上而且兩個頂點分別在原點的兩側時會出錯。如邊(3,0)-(-3,0)，按以上的處理，象限分別是第一和第二，這樣會使代數(shù)和加π/2，有可能導致最后結果是被測點在多邊形外。而實際上被測點是在多邊形上（該邊穿過該點）。???對于這點，我的處理辦法是：每次算P和P[i+1]時，就計算叉積和點積，判斷該點是否在該邊上，是則判斷結束，否則繼續(xù)上述過程。這樣犧牲了時間，但保證了正

5、確性。???具體實現(xiàn)的時候，由于只需知道當前點和上一點的象限位置，所以附加空間只需O(1)。實現(xiàn)的時候可以把上述的“π/2”改成1，“π”改成2，這樣便可以完全使用整數(shù)進行計算。不必考慮頂點的順序，逆時針和順時針都可以處理，只是最后的代數(shù)和符號不同而已。整個算法編寫起來非常容易。???針對以上算法，我寫了一個代碼，拿ZOJ1081PointsWithin進行測試，順利Accepted。這證明該算法的正確性還是可以保障的。以下附上我的代碼：//ZOJ1081,改進弧長法判點在形內(nèi)形外#include

6、tdio.h>#includeconstintMAX=101;structpoint{intx,y;}p[MAX];intmain(){??intn,m,i,sum,t1,t2,f,prob=0;??pointt;??while(scanf("%d",&n),n)??{???????????if(prob++)printf("");???????????printf("Problem%d:",prob);???????????scanf("%d",&m);???????????

7、for(i=0;i=0?(p[0].y>=0?0:3):(p

8、[0].y>=0?1:2);???????//計算象限?????????????????????for(sum=0,i=1;i<=n;i++)?????????????????????{??????????????????????????if(!p.x&&!p.y)break;//被測點為多邊形頂點??????????????????????????f=p.y*p[i-1].x-p.x*p[i-1].y;???//計算叉積????????????????