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