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