GIS中的計算幾何
GIS是一個圖形系統(tǒng)，必然會涉及到幾何學(xué)的理論應(yīng)用，比如，圖形可視化，空間拓撲分析，GIS圖形編輯等都需要用到幾何
。向量幾何是用代數(shù)的方法來研究幾何問題，首先，請大家翻一翻高等數(shù)學(xué)里有關(guān)向量的章節(jié)，熟悉一下幾個重要的概念：
向量、向量的模、向量的坐標表示、向量的加減運算、向量的點積、向量的叉積，以及這些概念的幾何意義...下面我們將用
這些基本概念來解答GIS中一些幾何問題。
1 點和線的關(guān)系
點是否在線段上，這樣的判斷在圖形編輯，拓撲判斷(比如，GPS跟蹤點是否跑在線上)需要用到這樣的判斷。通常的
想法是：先求線段的直線方程，再判斷點是否符合這條直線方程，如果符合，還要判斷點是否在線段所在的矩形區(qū)域(MBR)內(nèi)
，以排除延長線上的可能性，如果不符合，則點不在線段上。這種思路是可行的，但效率不高，涉及到建立方程，解方程。
借助向量的叉積（也叫向量的向量積，結(jié)果還是向量，有方向的）可以很容易的判斷。設(shè)向量a=(Xa,Ya,Za) b=(Xb,Yb,Zb)
向量叉積a X b如下：
二維向量叉積的模 |a X b|=|a|*|b|*sinα=|Xa*Yb-Ya*Xb| （α是向量a,b之間的夾角），向量叉積模的幾何意義是以向量a,b
為鄰邊的平行四邊形的面積?？梢酝茰y：如果兩向量共線，向量叉積模(所代表的
平行四邊形的面積) 為零 則
|a X b|=|a|*|b|*sinα=|Xa*Yb-Ya*Xb|=0,否則不共線，叉積的模為非零，根據(jù)這樣條件可以很輕松的判斷點和線的關(guān)系，避
免了建立方程和解方程的麻煩。
向量叉積的模|AB X AC|=0即可判斷C點在AB所確定的直線上，再結(jié)合C點是否在AB所在的MBR范圍內(nèi)，就可以最終確
定C是否在AB線段上。關(guān)于點和線段的其他關(guān)系，都可以通過叉積的求得，比如 判斷點在線的哪一側(cè)，右手法則，可以通過a
X b= (Xa*Yb-Ya*Xb)*k中的（Xa*Yb-Ya*Xb）正負來判斷。留給大家思考，很簡單的，呵呵…
2 線和線的關(guān)系
判斷兩條線段是否相交，在很多拓撲判斷和圖形編輯 (比如，線的打斷來構(gòu)建拓撲，編輯線對象，疊置分析，面與
面關(guān)系的判斷等) 中都需要用到線線相交的判斷，如果兩條線段相交，一條線段的兩端點必然位于另一條線段的兩側(cè)（不考
慮退化情況，也就是一條線段的端點在另一條線段上，這個很容易判斷）
兩向量的叉積a X b= (Xa*Yb-Ya*Xb)*k ，分別判斷AB X AC的方向與AB X AD的方向是否異號，再判斷CD X CA 的方向與CD X
CB的方向是否異號，即可判斷兩線段是否相交。
退化情況，即一條線的端點落在另一條線上。運用”點是否在線段上”的方法來判定。詳細區(qū)分留給大家思考。呵呵…
利用向量的方向還可以判斷線段的轉(zhuǎn)向，這個在道路導(dǎo)航中有所應(yīng)用：
3 點和面的關(guān)系
在各種拓撲判斷中（比如，面對象的選取，包含關(guān)系的判斷等）需要判斷一個點是否位于某個面內(nèi)，經(jīng)典的方法就是“垂線法
”，在直角坐標系中，從這個點向X軸作射線，判斷射線與多邊形的交點個數(shù)（不考慮退化情況，退化情況下，判斷點或者射
線與多邊形端點或者邊的關(guān)系），如果為奇數(shù)，則點在面內(nèi)，為偶數(shù)，則點在面外。
4 線和面的關(guān)系
線面關(guān)系的判斷相對比較復(fù)雜，線在面內(nèi)，線和面相交，相離，相接等關(guān)系。線段在面內(nèi)，第一個必要條件是，線段的兩個
端點都要在內(nèi)。但由于多邊形可能為凹，所以這不能成為判斷的充分條件，于是有第二個必要條件線段與多邊形的邊，沒有
內(nèi)部交點。
線段和多邊形交于線段的兩端點并不會影響線段是否在多邊形內(nèi)；但是如果多邊形的某個頂點和線段相交，還必須
判斷兩相鄰交點之間的線段是否包含于多邊形內(nèi)部，如果在面內(nèi)，則線段在面內(nèi)，否則不在面內(nèi)。
所以，算法思路如下（本算法引用網(wǎng)絡(luò)上一篇文章）：
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;
注：X-Y坐標排序，X坐標小的排在前面，對于X坐標相同的點，Y坐標小的排在前面，這種排序準則也是為了保證水平和垂直
情況的判斷正確。
1. 點在面內(nèi)，線段相交情況的判斷見上面的思路。
2. 這個過程中的排序因為交點數(shù)目肯定遠小于多邊形的頂點數(shù)目n，所以最多是常數(shù)級的復(fù)雜度，幾乎可以忽略不計
。因此算法的時間復(fù)雜度也是O(n)。
3. 有了線段和面的關(guān)系，再判斷折線與面的關(guān)系，也就可以for循環(huán)，同理進行判斷了，但時間復(fù)雜度將是O(n^2)。
后面將介紹一種時間復(fù)雜度為O(nlogn)的”平面掃描算法”。
5 面和面的關(guān)系
面面的空間關(guān)系，可能要更復(fù)雜一些，在拓撲判斷，多邊形疊置分析，面對象的編輯中，有著廣泛的應(yīng)用。這個將在以后的
章節(jié)中介紹一種時間復(fù)雜度為O（nlogn）的算法“平面掃描算法”。
6 點到線段的距離
點到線段的距離，在各種測量，拓撲判斷(比如，線對象的選取中需要比較距離)中都需要用到。大家對點到直線的
距離，都很熟悉，那點到線段距離又該如何計算呢？
問題的關(guān)鍵是判斷a、r的角度，向量的點積能判斷一個角是鈍角還是銳角，先復(fù)習(xí)一下向量的點積，也叫向量的數(shù)
量積,結(jié)果是一個數(shù)，沒有方向。設(shè)向量a=(Xa,Ya,Za) b=(Xb,Yb,Zb)
a . b=|a|*|b|*cosα=Xa*Xb+Ya*Yb+Za*Zb 向量點積的幾何意義是，高中物理中，求作用力在一個方向上所作的功。如果a .
b>0，則α為銳角，a . b<0,則α鈍角。
熟悉了利用向量的點積來判斷角度，AC·AB 判斷夾角a，BA·BC判斷夾角r，即可確定三種情況中，具體是哪一種。至于第一種
情況，求點到垂足的距離，可以饒開建立方程求垂足，再求兩點距離的思路，因為建立方程運算是復(fù)雜的，多耗了CPU資源。
利用向量叉積的幾何意義來求，向量的叉積表示以兩向量為鄰邊的平行四邊形的面積，|AC X AB|為⊿ABC的面積的兩倍，求
平行四邊形的高,只要用面積除以底邊AB的長度。即，高CD的長度=|AC X AB|/distance(AB)。
這些復(fù)雜的幾何判斷，都將在空間索引的過濾下，在少量數(shù)據(jù)集(侯選集)上進行。計算幾何算法，通常是比較復(fù)雜，比較耗
CPU資源，而且還要考慮各種退化情況，在這里，并不試圖向大家窮舉各種情況，只想起一個拋磚引玉的作用， 或許還有人
會有這樣的疑慮：有沒考慮“投影”的問題？關(guān)于投影將在相應(yīng)的章節(jié)中給予解釋，但有一點是可以肯定的，空間分析、計算
幾何算法，都是在平面直角坐標系下運算的，不會在球面上。