計算幾何教程ComputationalGeometry前言這個教程會從矢量開始講起，學習有關直線、三角形、多邊形、圓之知識。教程在下一部分會擴展所學的概念，展開三維計算幾何的講解。最后講解一些計算幾何算法和雜題。計算幾何的惡心之處有精度誤差。將在下一頁詳述。需要討論各種邊界情況。后面所介紹的算法，有些對于邊界情況的處理很完美，不需要再做討論；有些則不然，需要自行處理邊界情況。代碼長。精度誤差

二維矢量矢量既有大小又有方向的量。又稱為向量。大家初中都畢業了我就不多說了。矢量的表示

點積

夾角

矢量的垂直

矢量的縮放

矢量的投影

矢量的對稱

二維叉積

有向面積

有向面積的符號

點積和二維叉積的方向性利用點積可以判斷矢量的前后。利用二維叉積可以判斷矢量的左右。二維矢量的旋轉

二維矢量的極角

二維計算幾何約定

直線

點到直線的距離

分點

三角形的面積

兩直線交點

兩線段交點求出直線的交點，然后其判斷是否在兩條線段上即可。若判斷兩線段是否相交，則要注意平行不一定不相交，兩條線段可能有重合部分或重合點。三角形的重心

多邊形多邊形是平面上由有限線段（大于2）組成，且首尾連接起來劃出的封閉圖形。教程后面的多邊形一般指簡單多邊形，即邊不相交的多邊形。多邊形的記錄一般以順次記錄其頂點的方式完成，即順次記錄組成多邊形的線段。方向一般為逆時針。判斷點在多邊形內外以要判斷的點為起點任作一射線，計算該射線與多邊形的交點數目。若有偶數個交點則在形外，否則在形內。若與線段在端點處相交或重合，則要進行復雜的判斷。此時可另取一射線。求多邊形的面積基本的思路是進行三角剖分。求多邊形的面積如果用普通面積的累加來計算的話，三角剖分就變得十分復雜。但是使用有向面積的話，這個過程就變得簡單自然通用。算法

算法演示算法演示算法演示算法演示算法演示算法演示算法演示算法演示算法演示三角剖分三角剖分即將多邊形分為若干三角形部分，其中既有“正部分”亦有“負部分”。利用這種方法可以解決很多問題。例題：求多邊形的重心名前通り，給定一個簡單多邊形，求其重心之所在。預備知識：求質點組的重心

解答利用三角剖分，計算各個三角形的面積和重心，將此三角形化為一個質量為其面積，坐標為其重心的質點。若此三角形屬于“負部分”，則其擁有“負質量”。最后計算質點組的重心即可。凸集

凸集舉例空集直線、射線、線段凸多邊形圓及內部、二次曲線及內部若干種原料，每種原料含A成分和B成分的比例不同；混合這些原料能得到的產品的A,B兩種成分的比例凸包對于點集S，包含S

中所有點的最小的凸集稱為S

的凸包。若S

是有限集，則其凸包是凸多邊形。直觀來看，把S

中所有點釘在一個木板上，用一個橡皮筋框起所有點來，一撒手，橡皮筋就表示出了S

的凸包。凸包水平序Graham掃描算法Graham掃描算法有水平序和極角序兩種。極角序算法能一次確定整個凸包，但是計算極角需要用到三角函數，速度較慢，精度較差，特殊情況較多。水平序算法需要掃描兩次，但排序簡單，討論簡單，不易出錯。算法流程

算法演示首先將所有點排序。算法演示將1和2壓入棧。算法演示2被彈出棧，3進棧。算法演示沒有點被彈出棧，4進棧。算法演示4被彈出棧，5進棧。算法演示5被彈出棧，6進棧。算法演示6被彈出棧，7進棧。算法演示如此直到下凸殼被找到。算法演示倒序進行掃描找到上凸殼。Graham掃描的時間復雜度這太傻缺了。算法的瓶頸在排序，所以時間復雜度是O(NlogN)。若坐標均為整數，可以用基數排序將復雜度優化到O(N)。旋轉卡殼算法如何計算N

個點中，距離最大的兩個點的距離？要求O(NlogN)的算法。容易證明距離最大的兩個點一定是凸包上的兩個點，很明顯是先求凸包然后做文章啦。對踵點若凸包上的兩個頂點能落在一對平行切線上，則稱它們為對踵點。容易證明，答案一定是一對對踵點之間的距離。對踵點的枚舉從一對對踵點逆時針枚舉下一對對踵點的話，只需要觀察下圖中α

角和β

角的大小，選擇其中較小的一個轉過去就行了。算法最左側點和最右側點一定是對踵點。從此點對開始枚舉即可。注意不只有“點–點”的情況，還有“點–邊”和“邊–邊”的情況。這些情況下要枚舉所有的點對。雖然看上去很簡單，但是寫起來還是要頗費一番周折的。旋轉卡殼練習題POJ2178求點集中最遠點POJ3608求兩凸包間的最近點POJ2079求以點集中的點為頂點組成的三角形的最大面積，要求O(N2)算法。半平面

半平面的表示

半平面的交半平面是凸集，所以半平面的交也是凸集。有限個半平面的交可能是空集、點、直線、射線、線段、凸多邊形、有“開口”的形狀甚至一個半平面。樸素的每次O(N)算法為了保證結果是凸多邊形或其退化，首先建立一個非～常～大的邊框。你懂的。每次順次枚舉多邊形的邊，與半平面求交，并將交的部分加入新多邊形。在得到半平面邊界與凸多邊形所交形成的邊時，立即將其加入新多邊形。算法演示值得注意的邊界情況1值得注意的邊界情況2值得注意的邊界情況3合計O(NlogN)的算法這是朱澤園在其國家集訓隊論文《半平面交的新算法及其實用價值》中提出的算法。由于建立了非～常～大的邊框，半平面交的結果一定是一個凸多邊形。而凸多邊形分為下凸殼和上凸殼。如果分開處理這兩部分，就會獲得非常好的性質。下凸殼與上凸殼

分別排序按照極角，篩選出可能屬于下凸殼和上凸殼的半平面分別按極角大小從小到大排序。上凸殼排序時，極角位于第三象限的半平面要加上

2π.掃清障礙對于極角相同的半平面，選擇最靠左的一個，并將剩下的舍棄。這樣即保證所有的半平面的極角皆不相同。處理下凸殼

算法演示首先將前兩個半平面進棧。算法演示x0<x1，將新的半平面壓入棧。算法演示x0

≥

x1，將棧頂彈出。算法演示x0<x1，將新的半平面壓入棧。依此類推。處理上凸殼

上下凸殼的合并只要凸殼中有不止一個半平面，就有可能出現沒有用的半平面。如圖，下圖中的

p1半平面沒有用。濾除沒有用的半平面先濾除左側的半平面。指針p1

指向下凸殼的最左側，p2

指向上凸殼的最左側。若下凸殼中還有至少兩個半平面，檢查p2

與p1

的邊界的交，以及下凸殼中p1

右側的半平面與p1

的邊界的交。若這兩個交的并集為空或只有一個端點，則舍棄半平面p1，將指針p1

右移。處理完p1

后類似處理p2。若p2

右移了，就重復處理p1，依此類推，直到二者都不右移了為止。類似濾除右側沒有用的半平面。實際上……“這兩個交的并集為空或只有一個端點”仍然只是討論交點的坐標大小。但是，這兩個交點的x

坐標可能相同，但y

坐標不相同。所以不能像前面一樣只討論x

坐標。算法演示p1

上二者的交為空集。右移p1。算法演示p2

上二者的交為空集。右移p2，重新檢查p1。算法演示p1和

p2均滿足要求，結束對左側的檢查。總結算法的瓶頸仍然在于排序，所以時間復雜度為O(NlogN)。若使用桶排序，甚至能得到O(N)的半平面交算法，但是并不會有明顯的性能提升。總體來說討論比較辛苦，寫起來不算很難。精度存在比較大的問題，而且半平面交的題目一般都容許O(N2)算法，所以并不是很常用。半平面交練習題POJ1279求多邊形的核。核中的點滿足其到多邊形邊界上任一點之間的線段只與多邊形在那一點相交。POJ3525求凸多邊形最大內切圓半徑。POJ2451裸的半平面交。朱澤園專門為他的算法出的題，要求O(NlogN)算法。POJ3384求在凸多邊形內部放兩個半徑為r

的圓所能覆蓋的最大面積。兩圓可以重疊，但不能與多邊形相交。需要用到旋轉卡殼。圓到定點O

距離等于定值r

的點的集合。有時根據上下文也包含內部的點。O即為圓心，r

即為半徑。圓只需要用這兩個東西表示就行了。圓與直線的交點

圓與直線的交點

圓與圓的交點

圓與圓的交點

圓與圓的交點

圓的面積并題目：SPOJCIRU給出N(N

≤1000)個圓，求其并集的面積。要求O(N2logN)的算法。后面給出的算法由AekdyCoin原創。分析如圖，最后形成的圖形是由很多弓形和多邊形組成的。弓形可以單獨計算，多邊形利用叉積亦可以分各邊計算，所以我們可以單獨考慮每個圓。每個圓的情形

不連通？由于各個連通塊中的弓形和多邊形的邊實際上都得到了很好的處理，所以圖形不連通沒有問題。有“洞”？發生了非常NB的事情。由于我們累加的是有向面積，而“洞”中多邊形是反向(順時針)旋轉的，所以“洞”會被自動抵消！時間復雜度對于每個圓，要求O(N)次交，從而出現了O(N)個交點。要找出未被覆蓋的弧的話，要對交點進行排序，所以每個圓要花費O(NlogN)的時間進行處理。總時間復雜度O(N2logN)。算法擴展SPOJCIRUT求恰好被覆蓋1次、2次、…、N

次的面積。算法的本質在于對“裸露”部分進行處理。這種方法也可以用于求很多圓與很多凸多邊形的面積并——但是情況復雜得多，要討論的情況也多得多。三維矢量第三維度

三維叉積

左手系與右手系x,y,z

軸的方向，傳統上應該滿足右手系。即伸出右手，將四指由x

軸指向沿小于平角轉到y

軸指向，拇指所指即為z

軸指向。類似也可以定義左手系。三個不共面的矢量必然滿足左手系與右手系中的一種。文字游戲注意“a,b,c

成右手系”和“b,a,c

成右手系”是截然相反的兩個命題。但是“a,b,c

成右手系”和“b,c,a

成右手系”是同一個命題。畫圖看一下這是為什么。三維叉積的性質

在三維空間我們失去的極角。在三維空間中描述矢量的方向不能只用一個角度，實際上需要使用兩個角度。左右。在三維空間中，兩個矢量間沒有左與右的概念。取而代之的是三個矢量間左手系與右手系的概念。混合積

有向體積如圖。a,b,c

的混合積的模，即為a,b,c

所成的平行六面體的體積。考慮符號的話，混合積又稱為有向體積。a,b,c

所成三棱錐的體積為平行六面體的1/6.一切的本質：行列式

三維計算幾何三維直線三維直線的表示法與二維類似。計算點到直線的距離的方法與二維相同。計算分點的方式也與二維相同。異面直線但是在三維空間中，直線除平行與相交之外有著第三種位置關系：異面。異面直線的距離即為兩條直線上距離最小的兩點之距離。你們都知道這就是兩條直線的公垂線段的長度。異面直線的距離

異面直線的距離

兩直線的交點先求它們的距離。若不為0，顯然木有交點。否則，若它們的方向矢量平行，它們重合。否則，它們是相交的。推薦利用后面所講的投影技術將其轉化為二維問題。平面平面是到兩點距離相等的點的軌跡。具體是個啥乃們應該清楚……點法式與平面垂直，即與平面上一切矢量垂直的非零矢量叫做平面的法矢量。可以證明平面的所有法矢量平行。記錄平面的一個法矢量v，再記錄平面上一點P，就可以完整表示整個平面了。點到平面的距離

直線與平面的交點

直線與平面的交點

平面與平面的交線

二面角就是兩個平面的法矢量的夾角啦。平面上點的二維投影

平面上點的二維投影

平面上點的二維投影

多面體多面體是指三維空間中由平面和直邊組成的幾何形體。……以上是科學定義。我不覺得這么一句廢話有什么用。我們假定多面體的每個面都是三角形的。凸多面體若一個多面體是凸集，則它是凸多面體。如同凸多邊形是半平面的交一樣，凸多面體也可以看做半空間的交。求半空間的交非常復雜，在此不多做介紹。不過有關于半空間的基本知識仍要加以講解。半空間的表示如同半平面可以用兩個互異的有序點來表示一樣，半空間可以用三個不共線的有序點來表示。半空間的表示

簡單判別法若要判斷點P

在內側還是外側，則從點P

向平面看去。若半空間的三個有序點成逆時針，則點P

在外側；否則點P

就在內側。凸多面體的表示表示一個凸多面體需要記錄其所有的面。對于所有的面，要正確記錄這個面上點的順序。根據假設，每個面都是三角形的，即包含三個點，所以每個面都表示了一個半空間。凸多面體應為這些半空間內側的交。可視若P

在半空間A

的外側，則稱半空間A，或A

所代表的平面對P

是可視的。我們在觀察一個凸多面體的時候，看到的面即為視點的可視面。凸多面體各個面的點的順序應該保證，從多面體內部的任意一點看去，所有的面都不可視。若將左右手系用行列式的符號替代，則可視的概念能推廣到高維。若多面體有非三角面這樣的面記錄的時候要保證，其上所有點從多面體的內部看去成順時針排列。此時這個面仍然能有效地表示一個半空間。三維凸包從凸包的定義出發推斷，一坨三維空間中的點的凸包是一個凸多面體。事已至此我們只好想辦法求它了。但是不難發現由于失去了左右這一概念，Graham掃描法徹底報廢了。那怎么辦？為了方便起見，我們假定沒有四點共面的情況。暴力方法O(N3)枚舉所有的點的三元組，將其看做半空間。若所有其它的點都在這個半空間的內側，則這個面是凸包的一個面。時間復雜度O(N4)。非常好寫！

增量法增量法作為求凸包的有力算法，可以解決任意維度的凸包問題。最壞情況下其時間復雜度為O(N2)。算法流程取出點集中的四個點，這四個點組成的四個面都是初始凸包的面。調整各個面上點的順序使得從內部看去各個面均不可視。之后添加其它各點。如果從這個點看去，所有的面均不可視，則此點在凸包內部。什么都不做，跳過該點。否則……算法流程

算法演示建立初始凸包，并試圖添加第一個點。算法演示添加第一個點完畢。算法演示試圖添加第二個點。算法演示添加第二個點完畢。如此添加所有點即可。隨機增量

三維凸包練習題POJ3528裸的三維凸包，且不含四點共面。三維凸包的出題概率很低，就不提供更多的練習題了。球在三維空間中，到定點距離等于定值的點的軌跡即為球。球可以用球心O

和半徑r

來表示。二維球面上的幾何學稱為球面幾何，是非歐幾何的一種。自然我們不會研究如此高深的問題。球與直線的交點

球與平面或球的交圓既然已經到了如此程度，想必大家已經可以自己來求了吧。先求交圓的圓心，再求交圓的半徑。由于這個圓是在三維空間中的，需要標明其在哪個平面上。經緯度

經緯度到三維坐標的轉換

三維旋轉確認旋轉之后坐標軸的位置，利用與昨天所講類似的旋轉矩陣求解即可。計算幾何雜題PolarisofPandora

「潘多拉的北極星」HDU4428/ZOJ3663潘多拉星球的半徑為r.在其北極的正上方有一顆北極星，距離星球可以認為是無窮遠(即星光可以認為是平行光)。現在要從經緯度為(lat0,lng0)的點沿大圓飛行到經緯度為(lat1,lng1)的點，且飛行高度為h.求能看到北極星的路程長度與總路程長度之比。解題思路飛行是在一個半徑為r+h

的球上進行的，看不到北極星的部分如圖所示。解題思路這貨可以處理成在某個“影子平面”下面，北極星是不可見的。前提是只在大圓上飛行。怎樣求大圓上兩點的距離

怎樣求大圓與平面的交點然后需要處理路徑從何時進入不可見區域。這需求大圓與平面的交點。由于整個大圓在一個平面上，我們可以求大圓平面與原平面的交線，然后求交線與大圓所在球的交點。收尾……如果起訖點都看不到北極星，那就哪兒都看不到北極星。否則，如果路徑所在大圓與影子平面沒有交點，那就全程都能看見北極星。否則，起訖點與兩個交點都在一個大圓上，根據它們之間的夾角討論即可。難度：較低BohemianRhapsody

「波西米亞狂想曲」POJ2824給出一個單位圓和若干（1000個）矢量，每個矢量都對應一筆錢。游戲一開始隨機抽取單位圓中的一點，然后按順序對每個矢量進行如下操作：首先將這個點按矢量平移，若這次平移之后該點仍在單位圓內，則獲得這個矢量對應的那筆錢，否則游戲結束。每次平移之后不將點移回，然后試驗下一個矢量。求能夠獲得的金額的期望。可行區域基本想法：對于每一步，維護可行區域。一開始的可行區域是整個圓。平移

平移

平移所以，每一步的可行區域，都是上一步的可行區域沿這一步的矢量平移之后，與原來圓的交。考慮把移動可行區域變為移動圓本身。則每一步的可行區域，都是上一步的可行區域與某一個新的圓的交。概率與期望獲得了每一步的可行區域之后，就可以求它的面積，然后計算在這一步之后還能拿錢的概率。從而即可算出期望。圓交的增量算法每次新增加一個圓的話，可以仿照半平面交，給出圓交的增量算法。簡單來說就是用新的圓和原來邊界上的圓求交，然后求得新的交。每次O(n)。而且本題所有的圓的半徑都是一樣的。討論起來比較方便。十分考驗基本功的題。Telescope

「望遠鏡」POJ3675求簡單多邊形與圓的交的面積。叉積與圓的有向面積交凸多邊形的面積，實際上是叉積的有向面積的和。所以只要能求出來每個叉積與圓的有向面積交即可。而叉積就是一個三角形。叉積的原點可以取圓心，這樣三角形的一個頂點就在圓心了。Case1三角形的兩條邊長全部短于半徑。Case2三角形的兩條邊長全部長于半徑，并且另一條邊與圓心的距離也長于半徑。Case3.1三角形的兩條邊長全部長于半徑，但是另一條邊與圓心的距離也短于半徑。垂足落在第三條邊上。Case3.2三角形的兩條邊長全部長于半徑，但是另一條邊與圓心的距離也短于半徑。垂足落在第三條邊外。Case4三角形的兩條邊長一條長于半徑，一條短于半徑。有向面積既然是有向面積，求交的面積的時候要考慮叉積的符號。Shadow「影子」POJ4010/HDU4130天上有若干個球和一個凸多面體。求在給定平行光下這些東西的投影的面積。球的數目N

以及凸多面體的頂點數M

之和不超過500。地上是什么東西凸多面體的投影是凸多邊形。所以將凸多面體的頂點都投到地上，然后求凸包就是凸多面體的投影。可是球的投影是橢圓……難道說就到此為止了么><換個投影面

噩夢的開始于是就變成了一個凸多邊形和一堆圓的面積并。按照原先所講的算法做即可。但是那個編碼復雜度……你們懂的。傳送門：難度：高LL’sCake

「LL的蛋糕」POJ3743一個半徑為10的圓蛋糕，切了N（N≤100）刀，而且保證沒有三刀交于一點。每一刀都是給定圓上兩點確定的。求里面最大一塊的面積是多少。很像半平面交不是么？但是外圍是個圓，也就是說會有一些弓形。“光環”首先離散化所有的角度，然后以這些角度為頂點建立初始多邊形。然后，給所有的邊一個“光環”——“光環”所謂“光環”，其實就是線段的附加屬性，表示這條線段對應的弓形的面積。不難發現，這些線段都不會被切斷。樸素半平面交然后就轉化成了帶“光環”的半平面交。切的時候，新產生的線段都是不帶光環的，或者可以說光環的大小是0。邊界情況不過這種半平面交新增了一種邊界情況。如果某一刀與多邊形的一條邊重合，要切出一個只有光環的面積是0的多邊形，對應原來的弓形。加速指南由于一個圓切N刀最多會產生的塊數是O(N2)級別的，每塊邊數是O(N)級別的，從而每次切的復雜度是O(N3)級別的，總復雜度是O(N4)級別的。一個簡單但是效果出色的剪枝：由于只求最大的一塊，而最大的一塊的面積肯定不會小于最大的一個弓形，所以比最大的弓形面積小的多邊形可以舍棄。Highway

「自駕暢游美國大平原」HDU5134你剛剛領了年終獎。現在你有錢了，你打算去美帝自駕游20天。不過，你一不小心從高速公路上開下去了。當你發現的時候，你已經離高速公路D

英里了。你在高速上可以開v1mph，而在外面只能開v0mph（由于精度問題，保證v1>1.2v0）。高速公路是無限延伸的直線。求你現在在T

時間內駕車能覆蓋的區域的面積。上高速我們研究一下如何上高速才是最快的。假定你要上高速去高速上的某無限遠點。hdθ上高速

hdθ上高速

hdθ最短路從而AB兩點之間的最短路由下圖所示——如果B’在