GIS算法资料
算法概念
柵格化
? ? 柵格化這個術語可以用于任何將[[矢量圖形]]轉(zhuǎn)換成[[位圖|柵格圖像]]的過程。這個術語用來表示在計算機上顯示三維形狀的流行[[渲染]]算法。柵格化目前是生成實時[[三維計算機圖形]]最流行的算法。實時應用需要立即響應用戶輸入，并且通常需要至少每秒 24 幀的速率。
? ? 最基礎的柵格化算法將多邊形表示的三維場景渲染到二維表面。多邊形由三角形的集合表示，三角形由三維空間中的三個頂點表示。在最簡單的實現(xiàn)形式中，柵格化工具將頂點數(shù)據(jù)映射到觀察者顯示器上對應的二維坐標點，然后對變換出的二維三角形進行合適的填充。
變換
通常使用矩陣運算進行變換，另外也可以用四元數(shù)運算。在三維頂點中添加一個齊次變量成為四維定點然后左乘一個 4 x 4 的變換矩陣，通過這種方法就可以對三維頂點進行變換。主要的變換有平移、縮放、旋轉(zhuǎn)以及投射。
裁剪
一旦三角形頂點轉(zhuǎn)換到正確的二維位置之后，這些位置可能位于觀察窗口之外，也可能位于屏幕之內(nèi)。裁剪就是對三角形進行處理以適合顯示區(qū)域的過程。
最常用的技術是Sutherland-Hodgeman裁剪算法。在這種方法中，每次測試每個圖像平面的四條邊，對于每個邊測試每個待渲染的點。如果該點位于邊界之外，就剔除該點。對于與圖像平的面邊相交的三角形邊，即邊的一個頂點位于圖像內(nèi)部一個位于外部，那么就在交叉點插入一個點并且移除外部的點。
掃描變換
傳統(tǒng)的柵格化過程的最后一步就是填充圖像平面中的二維三角形，這個過程就是掃描變換。
第一個需要考慮的問題就是是否需要繪制給定的像素。一個需要渲染的像素必須位于三角形內(nèi)部、必須未被裁掉，并且必須未被其它像素遮擋。有許多算法可以用于在三角形內(nèi)進行填充，其中最流行的方法是掃描線算法。
由于很難確定柵格化引擎是否會從前到后繪制所有像素，因此必須要有一些方法來確保離觀察者較近的像素不會被較遠的像素所覆蓋。最為常用的一種方法是深度緩存，深度緩存是一個與圖像平面對應的保存每個像素深度的二維數(shù)組。每個像素進行繪制的時候都要更新深度緩存中的深度值，每個新像素在繪制之前都要檢查深度緩存中的深度值，距離觀察者較近的像素就會繪制，而距離較遠的都被舍棄。
為了確定像素顏色，需要進行紋理或者濃淡效果計算。紋理圖是用于定義三角形顯示外觀的位圖。每個三角形頂點除了位置坐標之外都與紋理以及二維紋理坐標 (u,v) 發(fā)生關聯(lián)。每次渲染三角形中的像素的時候，都必須在紋理中找到對應的紋素，這是根據(jù)在屏幕上像素與頂點的距離在與紋理坐標相關聯(lián)的三角形頂點之間插值完成的。在透視投影中，插值是在根據(jù)頂點深度分開的紋理坐標上進行的，這樣做就可以避免透視縮減（perspective foreshortening）問題。
在確定像素最終顏色之前，必須根據(jù)場景中的所有光源計算像素上的光照。在場景中通常有三種類型的光源。定向光是在場景中按照一個固定方向傳輸并且強度保持不變的光。在現(xiàn)實生活中，由于太陽距離遙遠所以在地球上的觀察者看來是平行光線并且其衰減微乎其微，所以太陽光可以看作是定向光。點光源是從空間中明確位置向所有方向發(fā)射光線的光源。在遠距離的物體上的入射光線會有衰減。最后一種是聚光燈，如同現(xiàn)實生活中的聚光燈一樣，它有一個明確的空間位置、方向以及光錐的角度。另外，經(jīng)常在光照計算完成之后添加一個環(huán)境光值以補償光柵化無法正確計算的全局照明效果。
有許多可以用于光柵化的濃淡算法。所有的濃淡處理算法都必須考慮與光源的距離以及遮蔽物體法向量與光照入射角。最快的算法讓三角形中的所有像素使用同樣的亮度，但是這種方法無法生成平滑效果的表面。另外也可以單獨計算頂點的亮度，然后繪制內(nèi)部像素的時候?qū)旤c亮度進行插值。速度最慢也最為真實的實現(xiàn)方法是單獨計算每點的亮度。常用的濃淡模型有 Gouraud shading 和 Phong shading。
加速技術
為了在任何柵格化引擎中獲得最大的性能，只能往渲染工具中發(fā)送最少數(shù)量的多邊形。人們已經(jīng)開發(fā)出了一些加速技術以剔除無法看到的物體。
后向剔除
最簡單的剔除多邊形的方法就是剔除所有背離觀察者的多邊形，這就是后向剔除。由于大多數(shù)三維物體都是封閉的，所以除非觀察者位于物體內(nèi)部，背離觀察者的多邊形都會被面向觀察者的多邊形所遮擋。多邊形的方向由它的旋繞方向（winding）或者送到渲染工具的頂點順序所確定。一旦多邊形變換到屏幕空間之后，就可以檢查它是否位于相反的方向，一旦如此就丟棄這個多邊形。當然，后向剔除不適合于簡并的不封閉立體。
空間數(shù)據(jù)結(jié)構(gòu)
許多先進的技術使用數(shù)據(jù)結(jié)構(gòu)提出觀察物體之外的物體或者被其它物體遮擋的物體，最為常用的數(shù)據(jù)結(jié)構(gòu)有二元空間分割、八叉樹以及 Cell and Portal Culling。
4進一步改進
編輯
盡管基本的柵格化過程已經(jīng)出現(xiàn)了數(shù)十年，許多當今的應用仍然在優(yōu)化、增加柵格化渲染引擎的應用范圍。
紋理映射
紋理是在特定的分辨率生成的，但是由于紋理覆蓋的表面與觀察者之間可能是任意的距離，所以紋理也可能最后圖像上有任意的尺寸。因此，屏幕上的一個像素通常并不直接對應于一個紋素，而是需要使用一些紋理濾波技術來生成任意距離的清晰圖像。有許多在圖像質(zhì)量與計算的復雜性進行不同這種考慮的方法可以完成這項工作。
環(huán)境映射
環(huán)境映射是紋理坐標與觀察點相關的紋理映射形式。例如，其中一個常用的應用程序就是用來模擬鏡面反射，我們可以將整個房間內(nèi)部環(huán)境映射到房間內(nèi)的一個金屬杯上，當觀察者沿著杯子移動的時候，杯子頂點的紋理坐標也隨之變化，這樣就得到反射效果。
凸凹紋理映射
凸凹紋理映射是改變像素深度而不是顏色的另外一種紋理映射形式。尤其是與最新的陰影工具一起使用的時候，凸凹紋理映射使得表面顯現(xiàn)出與光照有關的凸凹不平，從而大幅度地提高真實感。
細節(jié)層次
在許多當今的應用中，任何場景中的多邊形數(shù)目都是非常大的，但是場景中的觀察者只能區(qū)分近距物體的細節(jié)。細節(jié)層次算法根據(jù)物體與觀察者的距離改變幾何圖形的復雜性。正對著觀察者的物體需要進行非常復雜的渲染，而距離遠的物體可以動態(tài)地簡化，甚至可以完全適用二維 sprite 替代。
陰影
傳統(tǒng)柵格化過程的光照計算沒有考慮物體遮擋的因素。陰影圖與陰影體是當今兩種生成陰影的普通技術。
5硬件加速
編輯
從1990年代開始，用于消費型桌面電腦的硬件加速開始變得普通。圖形程序員早期依賴于手工編寫匯編程序以改善程序的運行速度，現(xiàn)在大多數(shù)的程序已經(jīng)使用現(xiàn)有的圖形 API 驅(qū)動專用的圖形處理器。
最新的圖形處理器帶有可編程的 pixel shader，這可以大幅度地提升程序員的能力。未來的發(fā)展趨勢就是完全可編程的圖形流水線。
八方向柵格化算法代碼
/*八方向柵格化算法*/
public List<PixelPosition_T> RasterationMap(Map_T map, Raster_T ras)//柵格化整個選中的地圖數(shù)據(jù)
? ? ? ? {
? ? ? ? ? ? List<PixelPosition_T> mappixel = new List<PixelPosition_T>();
? ? ? ? ? ? foreach (Geometry_T geo in map.Geofeatures)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (geo.GetType() == typeof(Path_T))
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? Path_T pa = (Path_T)geo;
? ? ? ? ? ? ? ? ? ? foreach (Line_T line in pa.Path)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? List<PixelPosition_T> linepixel = RasterationLine(line, ras);
? ? ? ? ? ? ? ? ? ? ? ? mappixel.AddRange(linepixel);
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? return mappixel;
? ? ? ? }
? ? 返回值是 PixelPosition_T 類型的List，輸入?yún)?shù)是Map_T類型的map和Raster_T類型的ras；
? ? new一個PixelPosition_T 類型的List - mappixel；
? ? 對于map中的Geofeatures中的每個Geometry_T類型變量geo循環(huán)
? ? ? ? 如果geo的類型等于Path_T
? ? ? ? ? ? 把geo轉(zhuǎn)換為Path_T類型賦給pa
? ? ? ? ? ? 對pa中的Path中的每個Line_T類型的line循環(huán)
? ? ? ? ? ? ? ? 用line和ras調(diào)用RasterationLine，返回結(jié)果給PixelPosition_T類型的List-linepixel
? ? ? ? ? ? ? ? 在mappixel的范圍增加linepixel
? ? 返回mappixel
GIS開發(fā)常用算法原理分析
作為計算機科學的一個分支，計算幾何主要研究解決幾何問題的算法。在現(xiàn)代工程和數(shù)學領域，計算幾何在圖形學、機器人技術、超大規(guī)模集成電路設計和統(tǒng)計等諸多領域有著十分重要的應用。在本文中，我們將對計算幾何常用的基本算法做一個全面的介紹，希望對您了解并應用計算幾何的知識解決問題起到幫助。
矢量的概念
如果一條線段的端點是有次序之分的，我們把這種線段成為有向線段(directed segment)。如果有向線段p1p2的起點p1在坐標原點，我們可以把它稱為矢量(vector)p2。
矢量加減法
設二維矢量P = ( x1,y1 )，Q = ( x2 ,y2 )，則矢量加法定義為： P + Q = ( x1 + x2 , y1 + y2 )，同樣的，矢量減法定義為： P - Q =( x1 - x2 , y1 - y2 )。顯然有性質(zhì) P + Q = Q + P , P - Q = - ( Q - P )。
矢量叉積
計算矢量叉積是與直線和線段相關算法的核心部分。設矢量P =（x1,y1），Q = (x2,y2)，則矢量叉積定義為由(0,0)、p1、p2和p1+p2所組成的平行四邊形的帶符號的面積，即：P× Q = x1*y2 - x2*y1，其結(jié)果是一個標量。顯然有性質(zhì) P× Q = - ( Q× P )和 P× ( - Q ) = - ( P× Q )。一般在不加說明的情況下，本文下述算法中所有的點都看作矢量，兩點的加減法就是矢量相加減，而點的乘法則看作矢量叉積。
叉積的一個非常重要性質(zhì)是可以通過它的符號判斷兩矢量相互之間的順逆時針關系：
若 P× Q > 0 ,則P在Q的順時針方向。若 P × Q < 0 ,則P在Q的逆時針方向。若 P × Q = 0 ,則P與Q共線，但可能同向也可能反向。
折線段的拐向判斷
折線段的拐向判斷方法可以直接由矢量叉積的性質(zhì)推出。對于有公共端點的線段p0p1和p1p2，通過計算(p2 - p0)× (p1 - p0)的符號便可以確定折線段的拐向：
若(p2 - p0)× (p1 - p0) > 0,則p0p1在p1點拐向右側(cè)后得到p1p2。
若(p2 - p0)× (p1 - p0) < 0,則p0p1在p1點拐向左側(cè)后得到p1p2。
若(p2 - p0)× (p1 - p0) = 0,則p0、p1、p2三點共線。
判斷點是否在線段上
設點為Q，線段為P1P2，判斷點Q在該線段上的依據(jù)是：( Q- P1 )× ( P2 - P1 ) = 0且 Q在以 P1，P2為對角頂點的矩形內(nèi)。前者保證Q點在直線P1P2上，后者是保證Q點不在線段P1P2的延長線或反向延長線上，對于這一步驟的判斷可以用以下過程實現(xiàn)：
ON-SEGMENT(pi,pj,pk)
if min(xi,xj)<=xk<=max(xi,xj) andmin(yi,yj)<=yk<=max(yi,yj)
then return true;
else return false;
特別要注意的是，由于需要考慮水平線段和垂直線段兩種特殊情況，min(xi,xj)<=xk<=max(xi,xj)和min(yi,yj)<=yk<=max(yi,yj)兩個條件必須同時滿足才能返回真值。
判斷兩線段是否相交
我們分兩步確定兩條線段是否相交：
(1)快速排斥試驗
設以線段 P1P2為對角線的矩形為R，設以線段 Q1Q2 為對角線的矩形為T，如果R和T不相交，顯然兩線段不會相交。
(2)跨立試驗如果兩線段相交，則兩線段必然相互跨立對方。若P1P2跨立Q1Q2，則矢量 ( P1 - Q1 )和( P2 - Q1 )位于矢量( Q2 - Q1 )的兩側(cè)，即( P1 - Q1 )× ( Q2 - Q1 ) * ( P2 - Q1 )× ( Q2 - Q1 ) < 0。上式可改寫成( P1 -Q1 )× ( Q2 - Q1 ) * ( Q2 - Q1 )× ( P2 - Q1 ) > 0。當 ( P1 - Q1)× ( Q2 - Q1 ) = 0時，說明 ( P1 - Q1 )和 ( Q2 - Q1 )共線，但是因為已經(jīng)通過快速排斥試驗，所以 P1一定在線段 Q1Q2上；同理，( Q2 - Q1 )×(P2 - Q1 ) = 0說明 P2一定在線段 Q1Q2上。所以判斷P1P2跨立Q1Q2的依據(jù)是：( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 )× ( P2 - Q1 ) >= 0。同理判斷Q1Q2跨立P1P2的依據(jù)是：( Q1 -P1 )× ( P2 - P1 ) * ( P2 - P1 )× ( Q2 - P1 ) >= 0。具體情況如下圖所示：
在相同的原理下，對此算法的具體的實現(xiàn)細節(jié)可能會與此有所不同，除了這種過程外，大家也可以參考《算法導論》上的實現(xiàn)。
判斷線段和直線是否相交
有了上面的基礎，這個算法就很容易了。如果線段P1P2和直線Q1Q2相交，則P1P2跨立Q1Q2，即：( P1 - Q1 ) ×( Q2 - Q1 ) * ( Q2 - Q1 )× ( P2 - Q1 ) >= 0。
判斷矩形是否包含點
只要判斷該點的橫坐標和縱坐標是否夾在矩形的左右邊和上下邊之間。
判斷線段、折線、多邊形是否在矩形中
因為矩形是個凸集，所以只要判斷所有端點是否都在矩形中就可以了。
判斷矩形是否在矩形中
只要比較左右邊界和上下邊界就可以了。
判斷圓是否在矩形中
很容易證明，圓在矩形中的充要條件是：圓心在矩形中且圓的半徑小于等于圓心到矩形四邊的距離的最小值。
判斷點是否在多邊形中
判斷點P是否在多邊形中是計算幾何中一個非常基本但是十分重要的算法。以點P為端點，向左方作射線L，由于多邊形是有界的，所以射線L的左端一定在多邊形外，考慮沿著L從無窮遠處開始自左向右移動，遇到和多邊形的第一個交點的時候，進入到了多邊形的內(nèi)部，遇到第二個交點的時候，離開了多邊形，……所以很容易看出當L和多邊形的交點數(shù)目C是奇數(shù)的時候，P在多邊形內(nèi)，是偶數(shù)的話P在多邊形外。
但是有些特殊情況要加以考慮。如圖下圖(a)(b)(c)(d)所示。在圖(a)中，L和多邊形的頂點相交，這時候交點只能計算一個；在圖(b)中，L和多邊形頂點的交點不應被計算；在圖(c)和(d)中，L和多邊形的一條邊重合，這條邊應該被忽略不計。如果L和多邊形的一條邊重合，這條邊應該被忽略不計。
為了統(tǒng)一起見，我們在計算射線L和多邊形的交點的時候，1。對于多邊形的水平邊不作考慮；2。對于多邊形的頂點和L相交的情況，如果該頂點是其所屬的邊上縱坐標較大的頂點，則計數(shù)，否則忽略；3。對于P在多邊形邊上的情形，直接可判斷P屬于多邊行。由此得出算法的偽代碼如下： count ← 0;以P為端點，作從右向左的射線L; for多邊形的每條邊s do if P在邊s上 then return true; if s不是水平的 then if s的一個端點在L上 if 該端點是s兩端點中縱坐標較大的端點then count← count+1 else if s和L相交 then count← count+1; if count mod 2 = 1 then return true; else return false;
其中做射線L的方法是：設P\'的縱坐標和P相同，橫坐標為正無窮大（很大的一個正數(shù)），則P和P\'就確定了射線L。
判斷點是否在多邊形中的這個算法的時間復雜度為O(n)。
另外還有一種算法是用帶符號的三角形面積之和與多邊形面積進行比較，這種算法由于使用浮點數(shù)運算所以會帶來一定誤差，不推薦大家使用。
判斷線段是否在多邊形內(nèi)
線段在多邊形內(nèi)的一個必要條件是線段的兩個端點都在多邊形內(nèi)，但由于多邊形可能為凹，所以這不能成為判斷的充分條件。如果線段和多邊形的某條邊內(nèi)交（兩線段內(nèi)交是指兩線段相交且交點不在兩線段的端點），因為多邊形的邊的左右兩側(cè)分屬多邊形內(nèi)外不同部分，所以線段一定會有一部分在多邊形外(見圖a)。于是我們得到線段在多邊形內(nèi)的第二個必要條件：線段和多邊形的所有邊都不內(nèi)交。
線段和多邊形交于線段的兩端點并不會影響線段是否在多邊形內(nèi)；但是如果多邊形的某個頂點和線段相交，還必須判斷兩相鄰交點之間的線段是否包含于多邊形內(nèi)部（反例見圖b)。
因此我們可以先求出所有和線段相交的多邊形的頂點，然后按照X-Y坐標排序(X坐標小的排在前面，對于X坐標相同的點，Y坐標小的排在前面，這種排序準則也是為了保證水平和垂直情況的判斷正確)，這樣相鄰的兩個點就是在線段上相鄰的兩交點，如果任意相鄰兩點的中點也在多邊形內(nèi)，則該線段一定在多邊形內(nèi)。
證明如下：
命題1：如果線段和多邊形的兩相鄰交點P1，P2的中點P\'也在多邊形內(nèi)，則P1, P2之間的所有點都在多邊形內(nèi)。
證明：假設P1,P2之間含有不在多邊形內(nèi)的點，不妨設該點為Q，在P1, P\'之間，因為多邊形是閉合曲線，所以其內(nèi)外部之間有界，而P1屬于多邊行內(nèi)部，Q屬于多邊性外部，P\'屬于多邊性內(nèi)部，P1-Q-P\'完全連續(xù)，所以P1Q和QP\'一定跨越多邊形的邊界，因此在P1,P\'之間至少還有兩個該線段和多邊形的交點，這和P1P2是相鄰兩交點矛盾，故命題成立。證畢。
由命題1直接可得出推論：推論2：設多邊形和線段PQ的交點依次為P1,P2,……Pn，其中Pi和Pi+1是相鄰兩交點，線段PQ在多邊形內(nèi)的充要條件是：P，Q在多邊形內(nèi)且對于i =1, 2,……, n-1，Pi ,Pi+1的中點也在多邊形內(nèi)。在實際編程中，沒有必要計算所有的交點，首先應判斷線段和多邊形的邊是否內(nèi)交，倘若線段和多邊形的某條邊內(nèi)交則線段一定在多邊形外；如果線段和多邊形的每一條邊都不內(nèi)交，則線段和多邊形的交點一定是線段的端點或者多邊形的頂點，只要判斷點是否在線段上就可以了。至此我們得出算法如下： if 線端PQ的端點不都在多邊形內(nèi) then return false;點集pointSet初始化為空; for多邊形的每條邊s do if線段的某個端點在s上 then將該端點加入pointSet; else if s的某個端點在線段PQ上 then 將該端點加入pointSet; else if s和線段PQ相交 // 這時候已經(jīng)可以肯定是內(nèi)交了 then return false;將pointSet中的點按照X-Y坐標排序; for pointSet中每兩個相鄰點 pointSet[i] , pointSet[ i+1] do if pointSet[i] , pointSet[ i+1]的中點不在多邊形中then return false; return true;這個過程中的排序因為交點數(shù)目肯定遠小于多邊形的頂點數(shù)目n，所以最多是常數(shù)級的復雜度，幾乎可以忽略不計。因此算法的時間復雜度也是O(n)。
判斷折線是否在多邊形內(nèi)
只要判斷折線的每條線段是否都在多邊形內(nèi)即可。設折線有m條線段，多邊形有n個頂點，則該算法的時間復雜度為O(m*n)。
判斷多邊形是否在多邊形內(nèi)
只要判斷多邊形的每條邊是否都在多邊形內(nèi)即可。判斷一個有m個頂點的多邊形是否在一個有n個頂點的多邊形內(nèi)復雜度為O(m*n)。
判斷矩形是否在多邊形內(nèi)
將矩形轉(zhuǎn)化為多邊形，然后再判斷是否在多邊形內(nèi)。
判斷圓是否在多邊形內(nèi)
只要計算圓心到多邊形的每條邊的最短距離，如果該距離大于等于圓半徑則該圓在多邊形內(nèi)。計算圓心到多邊形每條邊最短距離的算法在后文闡述。
判斷點是否在圓內(nèi)
計算圓心到該點的距離，如果小于等于半徑則該點在圓內(nèi)。
判斷線段、折線、矩形、多邊形是否在圓內(nèi)
因為圓是凸集，所以只要判斷是否每個頂點都在圓內(nèi)即可。
判斷圓是否在圓內(nèi)
設兩圓為O1,O2，半徑分別為r1, r2，要判斷O2是否在O1內(nèi)。先比較r1，r2的大小，如果r1<r2則O2不可能在O1內(nèi)；否則如果兩圓心的距離大于r1 - r2 ，則O2不在O1內(nèi)；否則O2在O1內(nèi)。
計算點到線段的最近點
如果該線段平行于X軸（Y軸），則過點point作該線段所在直線的垂線，垂足很容易求得，然后計算出垂足，如果垂足在線段上則返回垂足，否則返回離垂足近的端點；如果該線段不平行于X軸也不平行于Y軸，則斜率存在且不為0。設線段的兩端點為pt1和pt2，斜率為：k = ( pt2.y - pt1. y ) / (pt2.x - pt1.x );該直線方程為：y = k*( x - pt1.x) + pt1.y。其垂線的斜率為 - 1 / k，垂線方程為：y = (-1/k) * (x - point.x) + point.y。
聯(lián)立兩直線方程解得：x = ( k^2 * pt1.x + k * (point.y - pt1.y ) + point.x ) / ( k^2 + 1)，y = k * ( x- pt1.x) + pt1.y;然后再判斷垂足是否在線段上，如果在線段上則返回垂足；如果不在則計算兩端點到垂足的距離，選擇距離垂足較近的端點返回。
計算點到折線、矩形、多邊形的最近點
只要分別計算點到每條線段的最近點，記錄最近距離，取其中最近距離最小的點即可。
計算點到圓的最近距離及交點坐標
如果該點在圓心，因為圓心到圓周任一點的距離相等，返回UNDEFINED。
連接點P和圓心O，如果PO平行于X軸，則根據(jù)P在O的左邊還是右邊計算出最近點的橫坐標為centerPoint.x - radius 或centerPoint.x +radius。如果PO平行于Y軸，則根據(jù)P在O的上邊還是下邊計算出最近點的縱坐標為 centerPoint.y -+radius或 centerPoint.y -radius。如果PO不平行于X軸和Y軸，則PO的斜率存在且不為0，這時直線PO斜率為k = （ P.y - O.y）/ ( P.x - O.x )。直線PO的方程為：y = k * ( x - P.x) + P.y。設圓方程為:(x - O.x ) ^2+ ( y - O.y ) ^2 = r ^2，聯(lián)立兩方程組可以解出直線PO和圓的交點，取其中離P點較近的交點即可。
計算兩條共線的線段的交點
對于兩條共線的線段，它們之間的位置關系有下圖所示的幾種情況。圖(a)中兩條線段沒有交點；圖 (b)和 (d)中兩條線段有無窮焦點；圖 (c)中兩條線段有一個交點。設line1是兩條線段中較長的一條，line2是較短的一條，如果line1包含了line2的兩個端點，則是圖(d)的情況，兩線段有無窮交點；如果line1只包含line2的一個端點，那么如果line1的某個端點等于被line1包含的line2的那個端點，則是圖(c)的情況，這時兩線段只有一個交點，否則就是圖(b)的情況，兩線段也是有無窮的交點；如果line1不包含line2的任何端點，則是圖(a)的情況，這時兩線段沒有交點。
計算線段或直線與線段的交點
設一條線段為L0 = P1P2，另一條線段或直線為L1= Q1Q2 ，要計算的就是L0和L1的交點。 1．首先判斷L0和L1是否相交（方法已在前文討論過），如果不相交則沒有交點，否則說明L0和L1一定有交點，下面就將L0和L1都看作直線來考慮。
2．如果P1和P2橫坐標相同，即L0平行于Y軸
a)若L1也平行于Y軸，
i.若P1的縱坐標和Q1的縱坐標相同，說明L0和L1共線，假如L1是直線的話他們有無窮的交點，假如L1是線段的話可用"計算兩條共線線段的交點"的算法求他們的交點（該方法在前文已討論過）； ii. 否則說明L0和L1平行，他們沒有交點；
b)若L1不平行于Y軸，則交點橫坐標為P1的橫坐標，代入到L1的直線方程中可以計算出交點縱坐標；
3．如果P1和P2橫坐標不同，但是Q1和Q2橫坐標相同，即L1平行于Y軸，則交點橫坐標為Q1的橫坐標，代入到L0的直線方程中可以計算出交點縱坐標；
4．如果P1和P2縱坐標相同，即L0平行于X軸
a)若L1也平行于X軸，
i.若P1的橫坐標和Q1的橫坐標相同，說明L0和L1共線，假如L1是直線的話他們有無窮的交點，假如L1是線段的話可用"計算兩條共線線段的交點"的算法求他們的交點（該方法在前文已討論過）； ii. 否則說明L0和L1平行，他們沒有交點；
b)若L1不平行于X軸，則交點縱坐標為P1的縱坐標，代入到L1的直線方程中可以計算出交點橫坐標；
5．如果P1和P2縱坐標不同，但是Q1和Q2縱坐標相同，即L1平行于X軸，則交點縱坐標為Q1的縱坐標，代入到L0的直線方程中可以計算出交點橫坐標；
6．剩下的情況就是L1和L0的斜率均存在且不為0的情況
a)計算出L0的斜率K0，L1的斜率K1；
b)如果K1 = K2
i.如果Q1在L0上，則說明L0和L1共線，假如L1是直線的話有無窮交點，假如L1是線段的話可用"計算兩條共線線段的交點"的算法求他們的交點（該方法在前文已討論過）； ii.如果Q1不在L0上，則說明L0和L1平行，他們沒有交點。 c)聯(lián)立兩直線的方程組可以解出交點來這個算法并不復雜，但是要分情況討論清楚，尤其是當兩條線段共線的情況需要單獨考慮，所以在前文將求兩條共線線段的算法單獨寫出來。另外，一開始就先利用矢量叉乘判斷線段與線段（或直線）是否相交，如果結(jié)果是相交，那么在后面就可以將線段全部看作直線來考慮。需要注意的是，我們可以將直線或線段方程改寫為 ax+by+c=0的形式，這樣一來上述過程的部分步驟可以合并，縮短了代碼長度，但是由于先要求出參數(shù)，這種算法將花費更多的時間。
求線段或直線與折線、矩形、多邊形的交點
分別求與每條邊的交點即可。
求線段或直線與圓的交點
設圓心為O，圓半徑為r，直線（或線段）L上的兩點為P1,P2。
1.如果L是線段且P1，P2都包含在圓O內(nèi)，則沒有交點；否則進行下一步。
2.如果L平行于Y軸，
a)計算圓心到L的距離dis； b) 如果dis > r則L和圓沒有交點； c)利用勾股定理，可以求出兩交點坐標，但要注意考慮L和圓的相切情況。 3.如果L平行于X軸，做法與L平行于Y軸的情況類似；
4.如果L既不平行X軸也不平行Y軸，可以求出L的斜率K，然后列出L的點斜式方程，和圓方程聯(lián)立即可求解出L和圓的兩個交點；
5.如果L是線段，對于2，3，4中求出的交點還要分別判斷是否屬于該線段的范圍內(nèi)。
凸包的概念
點集Q的凸包(convexhull)是指一個最小凸多邊形，滿足Q中的點或者在多邊形邊上或者在其內(nèi)。下圖中由紅色線段表示的多邊形就是點集Q={p0,p1,...p12}的凸包。
凸包的求法
現(xiàn)在已經(jīng)證明了凸包算法的時間復雜度下界是O(n*logn),但是當凸包的頂點數(shù)h也被考慮進去的話，Krikpatrick和Seidel的剪枝搜索算法可以達到O(n*logh)，在漸進意義下達到最優(yōu)。最常用的凸包算法是Graham掃描法和Jarvis步進法。本文只簡單介紹一下Graham掃描法，其正確性的證明和Jarvis步進法的過程大家可以參考《算法導論》。
對于一個有三個或以上點的點集Q，Graham掃描法的過程如下：
令p0為Q中Y-X坐標排序下最小的點設<p1,p2,...pm>為對其余點按以p0為中心的極角逆時針排序所得的點集（如果有多個點有相同的極角，除了距p0最遠的點外全部移除壓p0進棧S壓p1進棧S壓p2進棧S for i← 3 to m do while由S的棧頂元素的下一個元素、S的棧頂元素以及pi構(gòu)成的折線段不拐向左側(cè)對S彈棧壓pi進棧S return S;
此過程執(zhí)行后，棧S由底至頂?shù)脑鼐褪荙的凸包頂點按逆時針排列的點序列。需要注意的是，我們對點按極角逆時針排序時，并不需要真正求出極角，只需要求出任意兩點的次序就可以了。而這個步驟可以用前述的矢量叉積性質(zhì)實現(xiàn)。
?GIS算法源碼集合
?其他GIS相關代碼下載索引 http://www.mygis.com.cn/codeindex10.htm
1．深度優(yōu)先實現(xiàn)的路徑分析源碼 http://www.mygis.com.cn/codes/21-481-481.htm ?
2．用遺傳算法編寫的tsp源碼 http://www.mygis.com.cn/codes/21-3961-3961.htm ?
3．最短路徑算法源碼(VB) ?http://www.mygis.com.cn/codes/21-579-579.htm ?
4．Delphi最短路徑 http://www.mygis.com.cn/codes/21-4778-4778.htm ?
5．建立公交網(wǎng)絡拓撲關系 http://www.mygis.com.cn/codes/21-3962-3962.htm ?
6．VC實現(xiàn)公交換乘代碼 http://www.mygis.com.cn/codes/21-4671-4671.htm ?
7．經(jīng)緯度BL換算到高斯平面直角坐標XY（高斯投影正算）的源碼及算法 http://www.mygis.com.cn/codes/21-1686-1686.htm ?
8．Dijkstra算法函數(shù)(c++) ?http://www.mygis.com.cn/codes/21-11595-11595.htm ?
9．C畫等值線代碼 http://www.mygis.com.cn/codes/21-1708-1708.htm ?
10．經(jīng)典三角插值源代碼 http://www.mygis.com.cn/codes/21-2424-2424.htm ??
11．delanay三角網(wǎng)算法的VB程序 http://www.mygis.com.cn/codes/21-5483-5483.htm ?
12．道格拉斯-普克壓縮算法 http://www.mygis.com.cn/codes/21-10424-10424.htm ?
13．高斯投影變換_cpp ?http://www.mygis.com.cn/codes/21-1721-1721.htm ?
14．WGS84墨卡托投影轉(zhuǎn)換C#源碼 http://www.mygis.com.cn/codes/21-5588-5588.htm ?
15．讀寫Ini文件 http://www.mygis.com.cn/codes/21-2689-2689.htm ?
16．一個VC做的gis系統(tǒng)源代碼 http://www.mygis.com.cn/codes/21-479-479.htm ?
17．鼠標截取程序源碼，可在MapBasic中調(diào)用 http://www.mygis.com.cn/codes/21-3593-3593.htm ?
18．c#讀mif文件/txt文件代碼 http://www.mygis.com.cn/codes/21-3810-3810.htm ?
19．串口連接GPS實例VB（適合初學者） http://www.mygis.com.cn/codes/21-3860-3860.htm ?
20．串口連接GPS實例VC ?http://www.mygis.com.cn/codes/21-10945-10945.htm ?
21．北京市地理信息公眾查詢系統(tǒng)mo+c# ?http://www.mygis.com.cn/codes/21-8821-8821.htm ?
22．PDA上GPS的一個例子 eVB ?http://www.mygis.com.cn/codes/21-5639-5639.htm ?
23．VB.NET+MapObject查詢系統(tǒng)源代碼 http://www.mygis.com.cn/codes/21-6299-6299.htm ?
24．ArcMap連接SQL Server的三種方法 http://www.mygis.com.cn/codes/21-4677-4677.htm ?
25．將點狀圖層中各點x,y坐標輸出到文本文件中 http://www.mygis.com.cn/codes/21-4679-4679.htm ?
26．AO中直接加載ArcSDE矢量數(shù)據(jù) http://www.mygis.com.cn/codes/21-4682-4682.htm ?
27．地理信息系統(tǒng)二次開發(fā)實例教程-C#和MapObjects實現(xiàn) http://www.mygis.com.cn/codes/21-4701-4701.htm ?
28．GeoDatabase xml轉(zhuǎn)換為文件xml的源碼 http://www.mygis.com.cn/codes/21-5460-5460.htm ?
29．MapX打包程序腳本原碼 http://www.mygis.com.cn/codes/21-4459-4459.htm ?
30．MO的索引圖和放大窗口代碼_VB ?http://www.mygis.com.cn/codes/21-7371-7371.htm ?
31．VC版的MO View ?http://www.mygis.com.cn/codes/21-6383-6383.htm ?
32．C#網(wǎng)絡編程 http://www.mygis.com.cn/codes/21-9024-9024.htm ?
33．C#播放聲音 http://www.mygis.com.cn/codes/21-9025-9025.htm ?
34．C#數(shù)據(jù)庫編程一 http://www.mygis.com.cn/codes/21-9022-9022.htm ?
35．C#數(shù)據(jù)庫編程二 http://www.mygis.com.cn/codes/21-9023-9023.htm ?
36．C#自定義事件 http://www.mygis.com.cn/codes/21-9032-9032.htm ?
37．給地圖加上比例尺 http://www.mygis.com.cn/codes/21-5461-5461.htm ?
38．開發(fā)OLE容器的一個代碼 http://www.mygis.com.cn/codes/21-2422-2422.htm ?
39．AO的一個例子 http://www.mygis.com.cn/codes/21-10943-10943.htm ?
40．VC實現(xiàn)GIS矢量圖形的繪制 http://www.mygis.com.cn/codes/21-10997-10997.htm ??
41．判斷點是否在多邊形中 http://www.mygis.com.cn/codes/21-11474-11474.htm ?
42．VC下面ADO & DAO編程 http://www.mygis.com.cn/codes/21-2519-2519.htm ?
43．讀寫中國地球空間數(shù)據(jù)交換格式源碼 http://www.mygis.com.cn/codes/21-11886-11886.htm ?
44．1_1萬地形圖54與80坐標系換算程序(源碼） http://www.mygis.com.cn/codes/21-11889-11889.htm ?
45．用VC寫的miniGIS ?http://www.mygis.com.cn/codes/21-12195-12195.htm ?
46．GIS源程序（VC++） http://www.mygis.com.cn/codes/21-12196-12196.htm ?
47．獲取系統(tǒng)進程訊息 http://www.mygis.com.cn/codes/21-12706-12706.htm ?
48．短消息代碼 http://www.mygis.com.cn/codes/21-13799-13799.htm ?
? ?? 《新程序員》：云原生和全面數(shù)字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀
總結(jié)
- 上一篇： iOS - UIButton 开发总结
- 下一篇： Linux压缩解压缩文章总结