????????因?yàn)橐姷降膸讉€(gè)泰森多邊形函數(shù)庫都有一些bug和問題，所以我自己寫了一個(gè)生成泰森多邊形的函數(shù)庫。我自己寫的這個(gè)函數(shù)庫正確度百分之百、靈活度更高、執(zhí)行速度很快。而比如老外寫的那個(gè)Voronoi就有相當(dāng)嚴(yán)重的bug (https://gist.github.com/tnlogy/9081637也同https://bitbucket.org/Jmaa/luafortune/src)，有超高的幾率出現(xiàn)bug，而我寫的這個(gè)庫，是目前唯一一個(gè)能得到百分百正確的泰森多邊形圖案的庫，不僅正確率有完全的優(yōu)勢(shì)，而且擁有更高的靈活度，執(zhí)行速度也非常快。我的庫和其他庫的對(duì)比測(cè)試在文章末尾！

? ? ? ??先看看實(shí)際生成的泰森多邊形都是怎么樣的（順便附帶了作為生成泰森多邊形基礎(chǔ)的三角網(wǎng)圖案）。先看效果，然后再講算法，這些算法都是我自己想的，我也會(huì)很細(xì)致具體的講清楚

如圖1.01，這是用一張隨機(jī)的三角網(wǎng)生成的泰森多邊形，并且還人為設(shè)定了邊界范圍。可見在原有的三角網(wǎng)范圍上，橫向和縱向的邊界范圍全部擴(kuò)大了。

那么當(dāng)然也可以就用原本的三角網(wǎng)的范圍來設(shè)定泰森多邊形的邊界，如圖1.02

對(duì)于邊界的設(shè)定，只要確保邊界框是能包含住所有的離散點(diǎn)就都可以生成相應(yīng)的voronoi cell（泰森多邊形細(xì)胞）。然后圖1.03，還是一張隨機(jī)的三角網(wǎng)，但是設(shè)定的泰森多邊形邊界在幾個(gè)方向都擴(kuò)大了

因?yàn)樵摵瘮?shù)庫生成voronoi cell是基于任意三角網(wǎng)的，所以圓形的三角網(wǎng)當(dāng)然也可以，如圖1.04

當(dāng)然還是一樣的，泰森多邊形的邊界范圍可以自定義，所以也可以弄大的邊界，如圖1.05

還有大家熟悉的矩形的三角網(wǎng)生成的泰森多邊形，如圖1.06

邊界擴(kuò)大一點(diǎn)看看，如圖1.07

? ? ? ??當(dāng)然我不太喜歡基于矩形三角網(wǎng)生成的泰森多邊形，你瞧瞧，上面兩張圖，邊界上的泰森多邊形也太"規(guī)則"了吧？我都泰森多邊形了，我要更隨機(jī)的，那好看啊，這矩形三角網(wǎng)生成的泰森多邊形邊界基本都這么工工整整的、這么規(guī)則完全不好看。

? ? ? ??說了一堆，那么什么是泰森多邊形呢？之前講過三角網(wǎng)的生成算法，其實(shí)在生成的三角網(wǎng)基礎(chǔ)上就可以繼續(xù)生成泰森多邊形。三角網(wǎng)有幾個(gè)頂點(diǎn)就對(duì)應(yīng)幾個(gè)泰森多邊形，也就是，以某一個(gè)頂點(diǎn)為中心的一簇delaunay三角形就可以來生成一個(gè)泰森多邊形，簡(jiǎn)單來說，將這一簇三角形的外心按順序連接起來就可以得到這一簇三角形對(duì)應(yīng)的泰森多邊形了，如圖1.08（其實(shí)看剛剛上面的幾個(gè)圖應(yīng)該就很容易看出來了）。

圖1.08中，這些黑色頂點(diǎn)是隨機(jī)的離散點(diǎn)，然后根據(jù)這些隨機(jī)點(diǎn)生成了一張三角網(wǎng)，也就是這些黑線連成的三角網(wǎng)。有了三角網(wǎng)，就可以根據(jù)這三角網(wǎng)生成泰森多邊形了，有幾個(gè)隨機(jī)點(diǎn)就會(huì)生成幾個(gè)泰森多邊形細(xì)胞。比如P這個(gè)點(diǎn)，以P這個(gè)點(diǎn)為中心的三角形一共有6個(gè)，把這一簇三角形的外心按順序連起來就得到了以P這個(gè)點(diǎn)為中心的voronoi cell，即多邊形ABCDEF。三角形的外心當(dāng)然就是三角形三條邊的中垂線的交點(diǎn)了。顯然現(xiàn)在圖1.08中一共有10個(gè)黑色的離散點(diǎn)，所以相應(yīng)的voronoi cell也有10個(gè)，也就是紅線連出的那一個(gè)個(gè)泰森多邊形細(xì)胞。在知道了voronoi是什么以后，就可以考慮具體的算法了。

? ? ? ??那么現(xiàn)在就有幾個(gè)問題需要面對(duì)：

1、在生成了隨機(jī)的三角網(wǎng)以后，怎么找到以每個(gè)頂點(diǎn)為中心的一簇三角形

2、找到一簇三角形以后，怎么把三角形按照順序排好（無論順時(shí)針或逆時(shí)針排列都可以）

3、求出各個(gè)三角形的外心以后，如果外心超過設(shè)定的邊界范圍(如矩形框)怎么辦（因?yàn)橐粋€(gè)泰森多邊形是靠一簇三角形的每個(gè)外心連線連起來的，但如果外心在邊界外面，那連接后的圖形就會(huì)超過邊界范圍了、就會(huì)超出矩形框了）

4、對(duì)于頂點(diǎn)在邊界上的一簇三角形，它們沒有形成“閉合”的一圈三角形,? 那要怎么連成泰森多邊形

對(duì)于1：首先要用到之前講的函數(shù)，判斷一個(gè)點(diǎn)是否是一個(gè)點(diǎn)集中的點(diǎn)，如圖1.09

然后就可以根據(jù)某個(gè)三角形里是否有相應(yīng)的頂點(diǎn)來判斷這個(gè)三角形是否是屬于那個(gè)頂點(diǎn)的一簇三角形。也就是，for循環(huán)遍歷三角網(wǎng)的每一個(gè)頂點(diǎn)p[i]，再for循環(huán)遍歷每一個(gè)三角形?tris[i1]?檢查該三角形里有沒有p[i]點(diǎn)，即check(tris[i1],p[i])，如果三角形里有這個(gè)頂點(diǎn)，說明這個(gè)三角形是以這個(gè)頂點(diǎn)為中心的三角形之一，于是把這個(gè)三角形裝進(jìn)一個(gè)臨時(shí)的表里，當(dāng)遍歷完所有三角形時(shí)（即內(nèi)層循環(huán)for i1=1,#tris do結(jié)束時(shí)），這個(gè)臨時(shí)的表里就裝有現(xiàn)在以這個(gè)頂點(diǎn)為中心的所有三角形

對(duì)于2：現(xiàn)在找到一簇三角形以后，就要對(duì)這一簇三角形排序，使它們按照順時(shí)針或逆時(shí)針排序。觀察一下圖1.10

這樣一簇以O(shè)點(diǎn)為“中心”的三角形，本身順序是亂的，現(xiàn)在需要按順序排列，不管是順時(shí)針還是逆時(shí)針，只要朝一個(gè)方向排列就可以了。假設(shè)第一個(gè)三角形是OAE那么這個(gè)三角形里，除了O的兩個(gè)點(diǎn)一個(gè)是A一個(gè)是E，隨便任選一點(diǎn)作為起點(diǎn)，比如E，那么此時(shí)排序的第一個(gè)三角形就是OAE，然后該三角形的點(diǎn)除開O、E，就剩下A，那么就可以找這一簇三角形里還有哪個(gè)三角形頂點(diǎn)有一個(gè)是A的，因?yàn)槟莻€(gè)三角形就一定和△OAE相鄰。所以現(xiàn)在就能找到△OBA，只有這個(gè)三角形有頂點(diǎn)A，所以△OBA和△OAE相鄰，那么現(xiàn)在得到了排序的第二個(gè)三角形OBA，而△OBA里除開O和A就只剩下B了，這樣就又開始找這一簇三角形里誰還有B點(diǎn)，然后就可以找到△OCB也有B點(diǎn)，那么當(dāng)然△OCB就是排序的第三個(gè)三角形了，因?yàn)樗偷诙€(gè)三角形OBA相鄰，然后此時(shí)當(dāng)然又要按照OCB里除開O、B兩點(diǎn)，剩下的C來找第四個(gè)三角形，以此類推。

? ? ? ??其實(shí)在找的過程中，還需要同時(shí)保存邊的信息(等會(huì)會(huì)講這樣做的用處)，就是說，一開始第一個(gè)三角形是OAE，因?yàn)槭菑腅開始的，那么第一條變?yōu)镺E、第二條變?yōu)镺A，每找到一個(gè)三角形，就還要記得這樣把邊的信息存儲(chǔ)在另一個(gè)專門放邊的表里。所以現(xiàn)在第三條邊是OB、第四條邊是OC等等等等，以此類推。不過，現(xiàn)在圖1.10這一簇三角形是能繞一圈的，但是你生成的三角網(wǎng)，總有在邊界的三角形，比如像圖1.11這樣的以O(shè)為中心的一簇三角形（舉個(gè)例子,這些三角形都是隨便畫的...），如果該離散點(diǎn)在三角網(wǎng)的邊界上的話，當(dāng)然以這個(gè)點(diǎn)為中心的一簇三角形就不能繞著一圈了，這樣意味著不是每個(gè)三角形都像剛剛那樣，有兩個(gè)相鄰的三角形，在最邊上的三角形實(shí)際只有一個(gè)相鄰的三角形(如以O(shè)點(diǎn)為中心的三角形OEF，與它相鄰的三角形只有ODE一個(gè)。同樣△OAB也只有一個(gè)相鄰的△OBC)，那么這樣排序怎么辦呢？

現(xiàn)在如果像剛才一樣，隨便找個(gè)三角形就開始排序的話是不行的。比方說，隨便找△ODC為第一個(gè)三角形，OC為第一條邊，那么這樣找，就是OD為第二條邊，找到第二個(gè)三角形ODE,? 然后OE第三條邊，第三個(gè)三角形就是OEF，第四條邊就是OF，然后又找，哪個(gè)三角形還有F點(diǎn)的？啊，沒了。找不到下一個(gè)和OEF相鄰的三角形了，所以說，如果按照剛剛的找法，是沒辦法對(duì)邊界的一簇三角形成功排序的。顯然，現(xiàn)在如果要排序，就可考慮從最邊上的三角形開始排序，而不是隨便找一個(gè)三角形就開始排序，比如從三角形OAB開始排序、而且必須以O(shè)A為第一條邊, OB就是第二條邊，這樣就能找到第二個(gè)三角形OBC，以此類推下去，最后就能排序完所有三角形，因?yàn)閺倪吷祥_始找，就不會(huì)出現(xiàn)找的過程中提前找到在邊上的三角形了。

? ? ? ??所以現(xiàn)在要解決的問題就是如何知道三角形是不是最邊上的呢？要是說剛剛那種隨便一個(gè)三角形為起點(diǎn)的話就特別輕松舒服，但是現(xiàn)在的話就必須找哪個(gè)點(diǎn)是在最邊上的，因?yàn)橐屵@邊上的三角形排第一個(gè)的話，邊上的三角形肯定只有一個(gè)相鄰的，所以比如點(diǎn)A和點(diǎn)F都是只存在于一個(gè)三角形上，除了△OBA以外，這一簇三角形里沒有任何一個(gè)三角形有A點(diǎn)，那這樣當(dāng)然就說明△OBA是在邊上的三角形了。所以要找在最邊上的三角形只需要看每個(gè)三角形的頂點(diǎn)，如果有哪一個(gè)頂點(diǎn)只是這個(gè)三角形的頂點(diǎn)、其它三角形都沒有這個(gè)頂點(diǎn)的話，就能說明該三角形在邊上了。

? ? ? ??所以總結(jié)一下就是，對(duì)于任意一簇三角形，先檢查有沒有一個(gè)頂點(diǎn)只是這一個(gè)三角形的頂點(diǎn)，如果有，則說明這一簇三角形不是能繞一圈的三角形，所以就按最邊上的三角形開始排序，如果檢查出來所有頂點(diǎn)都同時(shí)是其它某三角形的頂點(diǎn)的話，說明這一簇三角形能繞一圈，此時(shí)就隨便按任何一個(gè)三角形開始排序就可以了。這樣就解決了排序問題，排出來的三角形當(dāng)然可能順時(shí)針或逆時(shí)針，不過這當(dāng)然沒有關(guān)系，只要是按順序的，不就可以繼續(xù)直接連線了嗎，因?yàn)橐粋€(gè)泰森多邊形是一簇三角形的外心依次連線得到的。

? ? ? ? 在排序以后，就得到了兩個(gè)臨時(shí)的表，一個(gè)三角形表tris，一個(gè)邊表edges。如下圖

比如以A為中心，那可以得到比如表tris里第一個(gè)三角形是ABD、第二個(gè)三角形是ABC，表edges的第一條邊是AD、第二條邊是AB、第三條邊是AC。比如以B為中心，那可以得到比如表tris里第一個(gè)三角形是ABD、第二個(gè)三角形是BDC、第三個(gè)三角形是BCA，表edges的第一條邊是BD、第二條邊是BC、第三條邊是BA。比如以C為中心，那可以得到比如表tris里第一個(gè)三角形是CBD、第二個(gè)三角形是CAB，表edges的第一條邊是CD、第二條邊是CB、第三條邊是CA。所以這樣你就應(yīng)該知道為什么剛剛說在三角形排序的同時(shí)還需要得到一個(gè)邊表，因?yàn)楹腿切瓮樞虻囊粭l條邊是有作用的，當(dāng)某一簇三角形的中心點(diǎn)在邊界時(shí)，tris表的三角形數(shù)量必然小于edges表里的邊的數(shù)目，而如果某簇三角形的中心點(diǎn)不在邊緣，那tris表里的三角形數(shù)和edges表的邊數(shù)就是一樣的。所以首先邊表的第一個(gè)用處是，當(dāng)#tris等于#edges時(shí)，說明該簇三角形不在邊緣(即能繞一圈)，而當(dāng)#tris≠#edges時(shí)說明該簇三角形有頭有尾(即不能繞一圈)。

????????邊表edges里儲(chǔ)存一條條邊，每條邊有兩個(gè)點(diǎn)，每條邊的第二個(gè)點(diǎn)都為該簇三角形的中心點(diǎn)，所以每條邊的方向可以看成是都是指向這個(gè)中心點(diǎn)的。如上圖，以A為中心的三角形，邊表的第一條是{D點(diǎn)，A點(diǎn)}、第二條是{B點(diǎn)、A點(diǎn)}、第三條是{C點(diǎn)、A點(diǎn)}。有了邊表以后，比如要求第一邊的中垂線啥的就很方便

對(duì)于3：現(xiàn)在就是計(jì)算一簇排好序的三角形的各個(gè)外心，然后連線，但是外心可能超出你設(shè)定的邊界范圍，如圖1.12

圖1.12只是一個(gè)局部，舉個(gè)例子而已。比如△OAB、△OBC、△OCD、△ODA構(gòu)成的這一簇以O(shè)為中心的三角形，因?yàn)樗麄兊耐庑倪B起來就是泰森多邊形，所以計(jì)算出△OAB的外心P1、△OBC的外心P2、△OCD的外心P3、△ODA的外心P4，然后因?yàn)槲覀兊娜切问桥藕眯虻?，所以直接外心按順序連接即可。但是顯然，現(xiàn)在連出的泰森多邊形太大了，超出了上面可見的人為設(shè)定的矩形邊框外，若我們只想要在矩形邊界內(nèi)的部分，那就需要求只和矩形相交的部分了。關(guān)于這個(gè)問題會(huì)在下文中更詳細(xì)的講解

對(duì)于4：因?yàn)閳D1.12里的這一簇三角形的“中心”O(jiān)點(diǎn)并不在三角網(wǎng)的邊界上，顯然這一簇三角形也確實(shí)是繞了一圈的，而像是以A點(diǎn)或以D點(diǎn)為“中心”的一簇三角形就是在邊緣的一簇三角形了，在連線的時(shí)候?qū)τ谠谶吘壍囊淮厝切危麄兊倪B線方式就有一些小區(qū)別。很簡(jiǎn)單的道理，本來說一簇三角形的每個(gè)外心連起來就是泰森多邊形了，但是如果這簇三角形在邊緣，那么它就不能繞一圈了，那最后一個(gè)三角形要怎么連接下一個(gè)外心呢，它后面根本沒有下一個(gè)三角形了。所以對(duì)于中心點(diǎn)在三角網(wǎng)邊界的一簇三角形在連線時(shí)，對(duì)于第一個(gè)三角形就要利用它的第一條邊的中垂線，對(duì)于最后一個(gè)三角形就要利用最后一條邊的中垂線了，如下圖。

? ? ? ? 那在簡(jiǎn)單描述了這幾個(gè)問題的處理方式以后，再來細(xì)講

? ? ? ? 首先肯定需要求比如射線和矩形框的交點(diǎn)，這很簡(jiǎn)單，如下圖射線AB與一條直線L求交點(diǎn)，交點(diǎn)是P

射線的端點(diǎn)是A，方向是A到B。然后求交點(diǎn)很簡(jiǎn)單，先把射線當(dāng)做直線來和另一條直線L求交點(diǎn)，假設(shè)交點(diǎn)是P，那如果P是射線和直線的交點(diǎn)的話，向量AB和向量AP的方向就應(yīng)該是相同的。而當(dāng)然P點(diǎn)本來就在直線AB上，那AB和AP當(dāng)然是共線的，所以要判斷向量AP和向量AB是否同向只需要進(jìn)行簡(jiǎn)單的符號(hào)判斷即可，如下圖

只要ΔX的符號(hào)和Δx的符號(hào)相同并且ΔY的符號(hào)和Δy的符號(hào)相同，那P一定就在射線AB上，而如果P不在射線AB上的話，那么必然有ΔX的符號(hào)和Δx的符號(hào)相反并且ΔY的符號(hào)和Δy的符號(hào)相反，當(dāng)然別忘了直線與射線的交點(diǎn)剛好是射線的端點(diǎn)的情況(那時(shí)Δx和Δy都等于0)

? ? ? ??然后要求射線和矩形的交點(diǎn)的話，只需要保證：1、交點(diǎn)在矩形上，2、交點(diǎn)在射線上

? ? ? ? 這樣就可以具體討論中心點(diǎn)在邊緣或不在邊緣的一簇三角形怎么連成泰森多邊形了?，F(xiàn)在咱們假設(shè)一個(gè)泰森多邊形的頂點(diǎn)要把它收集起來、放在名叫vor_cell的表里

? ? ? ? 一、當(dāng)該簇三角形是邊緣三角形時(shí)：

? ? ? ? ? ? ? ??對(duì)于第一個(gè)三角形：

? ? ? ??? ? ? ??? ? ? ? 1、如果其外心在矩形外：則外心必在該三角形外

? ? ? ??? ? ? ??? ? ? ??? ? ? ? 檢查外心在邊表edges里的第一條邊和第二條邊的哪一側(cè)，利用叉乘判斷。如下圖，觀察以O(shè)為中心的一組三角形，若△AOB為第一個(gè)△，那么當(dāng)然第一條邊是AO第二條邊是BO，則判斷出外心P在矩形外，令A(yù)OP為方向o1、BOP為方向o2

若o1≠o2，則以外心P為端點(diǎn)、指向第一邊中點(diǎn)的射線需要和矩形求出兩個(gè)交點(diǎn)。比如現(xiàn)在o1就≠o2，o1順時(shí)針，o2逆時(shí)針

而若o1=o2，則需要判斷外心在哪一條邊的外側(cè)，如下圖，以O(shè)為中心的三角形，設(shè)第一個(gè)是△OAB，第二個(gè)△是OBC(三角形OBC看起來有點(diǎn)扁，但當(dāng)然OBC不共線，看起來像一條線，其實(shí)是△OBC)

第一條邊是AO、第二條是BO，此時(shí)o1的方向是AOP、o2的方向是BOP，都是逆時(shí)針，o1=o2，則判斷外心P在哪一條邊的"外側(cè)"，其實(shí)用肉眼看我們知道P在BO邊的外側(cè)，那怎么算呢，有很多種方法，比如還是利用叉乘之類的，那么現(xiàn)在為了不太繞，就用比較好理解的方式，而不用叉乘算（下文會(huì)講用叉乘的方式），這樣看起來會(huì)更清晰，設(shè)第一邊的中點(diǎn)為M1，求出直線PM1和直線BO的交點(diǎn)N，如下圖如果PM1的長(zhǎng)度2大于PN的長(zhǎng)度2，自然說明從點(diǎn)P出發(fā)的射線要先經(jīng)過BO這條邊，才能到達(dá)AO這條邊，所以P點(diǎn)在BO外側(cè)。反之若PM12<PN2則外心P就在第一條邊的外側(cè)

所以當(dāng)外心P在第一邊的外側(cè)時(shí)，與第一邊垂直的射線的端點(diǎn)是P、方向是第一邊的中點(diǎn)指向P，所以該射線必然和矩形沒有交點(diǎn)、不用求。而剛剛上圖顯然外心P在第二條邊的外側(cè)，所以與第一邊垂直的射線的端點(diǎn)是P、方向是P指向第一邊中點(diǎn)，所以該射線必然和矩形有兩個(gè)交點(diǎn)、需要求

? ? ? ?然后第一個(gè)外心的情況處理好了，就可以考慮后面的連接了，因?yàn)楸緛淼奶┥噙呅沃恍枰谝粋€(gè)外心直接連接第二個(gè)外心就行了，但現(xiàn)在有了矩形邊界，就要討論了。別忘了，現(xiàn)在處于第一個(gè)外心在矩形外的情況，那繼續(xù)判斷下一個(gè)外心(next P)是否在矩形外，如果是，則P和next P連成的線段可能和矩形有相交，也可能沒有，比如P和next P在矩形的同一側(cè)時(shí)就有可能和矩形沒有相交，所以此時(shí)就寫一個(gè)線段和矩形相交的函數(shù)即可。如果next P不在矩形外，那P要和next P連起來嘛，那P到next P的線段必然和矩形只有一個(gè)交點(diǎn)，把這個(gè)交點(diǎn)和next P兩個(gè)點(diǎn)按順序放進(jìn)泰森多邊形頂點(diǎn)表vor_cell里即可

? ? ? ? ? ? ? ? ? ? ? ? 2、如果第一個(gè)三角形外心在矩形內(nèi)：

? ? ? ? ? ? ? ? ? ? ????? ? ? ?同樣檢查外心在邊表edges里的第一條邊和第二條邊的哪一側(cè)? ? ??

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?如果外心P剛好是第一條邊的中點(diǎn)，假設(shè)第一邊是AO，計(jì)算出AO的法向量"干鍋牛肉"，將向量"干鍋牛肉"的起點(diǎn)平移到AO中點(diǎn)，計(jì)算向量"干鍋牛肉"現(xiàn)在的終點(diǎn)是否在AO外側(cè)，如果在，那射線方向就是該法向量方向、將其和矩形求出唯一一個(gè)交點(diǎn)，如果不在，那一開始求的法向量需反向、然后再將其起點(diǎn)平移到AO中點(diǎn)，然后以此為射線和矩形求出唯一交點(diǎn)

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?而如果外心P不在第一邊上面：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ?同樣檢查外心在邊表edges里的第一條邊和第二條邊的哪一側(cè)。以同樣的方式求出o1、o2，若o1=o2則外心P在某一邊的外側(cè)，則繼續(xù)判斷它在哪一邊的外側(cè)。如下圖，以O(shè)為中心的一簇三角形，第一個(gè)三角形是OAB，當(dāng)然也只有這一個(gè)△，假設(shè)第一邊是AO、第二邊就是BO了。方向o1為AOP、方向o2為BOP，現(xiàn)在o1=o2

那同樣的設(shè)第一邊的中點(diǎn)是M1，求出直線PM1和直線BO的交點(diǎn)N，如下圖，同樣的，PM12>PN2則外心P就在第二條邊BO的外側(cè)，則垂直于第一條邊的射線的方向是P到M1、射線的端點(diǎn)是P，求出該射線和矩形邊界V1V2V3V4的唯一交點(diǎn)

而如果PM12<PN2則說明外心P就在第一條邊AO的外側(cè)，那么射線的方向就是M1到P、射線出發(fā)點(diǎn)當(dāng)然還是P，如下圖

而當(dāng)o1≠o2時(shí)，垂直于第一條邊的射線的方向是P到第一邊中點(diǎn)、射線的端點(diǎn)是P，然后求出和矩形交點(diǎn)

? ? ? ?然后同樣，第一步處理完以后，就可以連接下一個(gè)外心了，因?yàn)楝F(xiàn)在的外心P在矩形內(nèi)，所以很簡(jiǎn)單，如果下一個(gè)外心next P在矩形外，那P到next P的射線和矩形求唯一交點(diǎn)即可，如果next P在矩形內(nèi)，那當(dāng)然直接連接next P即可

? ? ? ? ? ? ????對(duì)于最后一個(gè)三角形：本質(zhì)上和第一個(gè)△相同,即第一個(gè)△可以看成最后一個(gè)，而最后一個(gè)△也可以看成第一個(gè)

? ? ? ? ? ? ? ? ? ? ? ??1、如果其外心P在矩形外：

? ? ? ? ? ? ? ? ? ? ? ??? ? ? ?設(shè)倒數(shù)第二條邊是BO、最后第一邊是AO，方向o1是BOP，方向o2是AOP，設(shè)最后一邊的中點(diǎn)是M2（即AO的中點(diǎn)）

? ? ? ? ? ? ? ? ? ? ? ??? ? ? ?若o1=o2，則判斷判斷外心P在哪一條邊的外側(cè)，計(jì)算直線PM2和直線BO的交點(diǎn)N，若PM22<PN2則說明外心P就在最后一條邊AO的外側(cè)，則垂直于最后一條邊的射線的方向是M2到P、射線的起點(diǎn)是P，所以此時(shí)不會(huì)和矩形有交點(diǎn)、不用管；若PM22>PN2則說明外心P在倒數(shù)第二條邊AO的外側(cè)，則垂直于最后一條邊的射線的方向是P到M2、射線的起點(diǎn)是P，所以該射線需要和矩形求出兩個(gè)交點(diǎn)

? ? ? ? ? ? ? ? ? ? ? ??2、如果最后一個(gè)三角形外心P在矩形內(nèi)：

? ? ? ? ? ? ? ? ? ? ? ??? ? ? ?同樣判斷P是否在最后一條邊上(即為最后一條邊的中點(diǎn))，如果是，那就同樣的計(jì)算最后一條邊的法向量、法向量的方向是指向三角網(wǎng)外的、而不是指向三角網(wǎng)內(nèi)的，然后垂直于最后一邊的射線的方向就是法向量的方向

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?如果P不在最后一邊，則同樣的算o1、o2，若o1=o2，則判斷P在哪一邊（倒數(shù)第二條邊或最后一條邊）外側(cè)，根據(jù)在哪一邊外側(cè)決定垂直于最后一條邊的射線的方向，然后和矩形求唯一交點(diǎn)；若o1≠o2，則射線方向就是P指向最后一條邊中點(diǎn)

? ? ? ? ? ? ????對(duì)于既不是第一個(gè)也不是最后一個(gè)三角形的三角形：中間的三角形存在上一個(gè)外心和下一個(gè)外心，而泰森多邊形就是一個(gè)個(gè)外心連接得到的，所以本質(zhì)上能直接連接下一個(gè)外心，但是可能有的外心在矩形外

? ? ? ? ? ? ? ? ? ? ? ??1、如果下一個(gè)外心next P在矩形外：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?若當(dāng)前外心P也在矩形外：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 直接利用線段和矩形求交的函數(shù)！

? ? ? ? ? ? ? ? ? ? ? ??2、如果下一個(gè)外心next?P在矩形內(nèi)：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?若當(dāng)前外心P在矩形外：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 則P到next P這條線段與矩形有一個(gè)交點(diǎn)，那么當(dāng)然該交點(diǎn)以及下一個(gè)外心next P都按順序添加進(jìn)泰森多邊形表vor_cell里

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 若當(dāng)前外心P在矩形內(nèi)：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 此時(shí)當(dāng)然是最舒服的情況，直接連接下一個(gè)外心就行了，好爽啊

? ? ? ? ? ? ????判斷是否需要添加"角"：在從第一個(gè)三角形開始添加泰森多邊形頂點(diǎn)到最后一個(gè)三角形添加完后，還需要判斷是否需要添加"角"，也就是此時(shí)的vor_cell表里的第一個(gè)點(diǎn)和最后一個(gè)點(diǎn)之間是否"夾著"矩形的頂點(diǎn)，如下圖

比如以O(shè)為中心的一簇三角形，計(jì)算它的泰森多邊形頂點(diǎn)，從第一個(gè)三角形算到最后一個(gè)三角形，咱們可以得到泰森多邊形的頂點(diǎn)A、B、C、D，但是顯然此時(shí)第一個(gè)點(diǎn)A與最后一個(gè)點(diǎn)D之間夾的有矩形的頂點(diǎn)，那么此時(shí)就需要添加矩形的"角"。所以：

? ? ? ? ? ? ? ? ? ? ? ??1、如果vor_cell里第一個(gè)點(diǎn)和最后一個(gè)點(diǎn)在矩形的同一條邊上：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?此時(shí)不需要添加新的東西了，泰森多邊形已經(jīng)"完整"了。那怎么判斷兩點(diǎn)有沒有在矩形的同一邊上呢：假設(shè)這兩點(diǎn)是p1、p2、矩形的左上角是(x0,y0)、矩形的寬高是w和h，那么如果p1.x=x0且p2.x=x0則p1和p2就肯定在矩形同一邊、如果p1.x=x0+w并且p2.x=x0+w則p1和p2就肯定在矩形同一邊、如果p1.y=y0并且p2.y=y0則p1和p2就肯定在矩形同一邊、如果p1.y=y0+h并且p2.y=y0+h則p1和p2就肯定在矩形同一邊

? ? ? ? ? ? ? ? ? ??? ??2、如果vor_cell里第一個(gè)點(diǎn)和最后一個(gè)點(diǎn)不在矩形的同一條邊上：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?判斷第一點(diǎn)和最后一點(diǎn)之間是否只夾了一個(gè)矩形頂點(diǎn)。怎么判斷，這很簡(jiǎn)單，直接討論一下即可。比如，如果p1.x=x0并且p2.x≠x0并且p2.x≠x0+w，那么如果此時(shí)p2.y=y0，那么說明p1和p2之間只夾了一個(gè)矩形的頂點(diǎn)、并且這個(gè)頂點(diǎn)就是(x0,y0)，就像這樣，討論各種情況，就能判斷兩個(gè)點(diǎn)是否只夾了一個(gè)頂點(diǎn)。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?所以如果第一點(diǎn)和最后一點(diǎn)之間只夾了一個(gè)矩形頂點(diǎn)，那么直接把這個(gè)矩形的頂點(diǎn)添加進(jìn)泰森多邊形表vor_cell里

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?然而，你認(rèn)為這是對(duì)的嗎？當(dāng)?shù)谝稽c(diǎn)和最后一點(diǎn)之間只夾了一個(gè)矩形頂點(diǎn)的時(shí)候，其實(shí)有可能是要添加三個(gè)"角"的，因?yàn)樵蹅兊木匦慰蚍秶亲远x的，也就是你可以擴(kuò)大很多，如下圖，你就會(huì)發(fā)現(xiàn)兩點(diǎn)之間也有可能夾有3個(gè)矩形頂點(diǎn)

所以，當(dāng)?shù)谝稽c(diǎn)和最后一點(diǎn)之間只夾了一個(gè)矩形頂點(diǎn)時(shí)，需要用叉乘來判斷這個(gè)矩形頂點(diǎn)是不是可以直接添加，如果不能，就說明此時(shí)要添加矩形的三個(gè)頂點(diǎn)

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?如果第一點(diǎn)和最后一點(diǎn)之間夾了不止一個(gè)矩形頂點(diǎn)，那么必然需要添加兩個(gè)矩形的頂點(diǎn)進(jìn)去。首先判斷最后一個(gè)點(diǎn)在矩形哪條邊上，比如圖1.13的D點(diǎn)在V1V2邊上，那么你就需要判斷到底是V1點(diǎn)是"泰森多邊形"的頂點(diǎn)還是V2點(diǎn)是"泰森多邊形"的頂點(diǎn)，要知道泰森多邊形必然是凸多邊形，所以直接利用兩個(gè)叉乘來判斷需要添加哪個(gè)點(diǎn)。方向o1為泰森多邊形第一個(gè)頂點(diǎn)到第二個(gè)頂點(diǎn)到泰森多邊形中心點(diǎn)O，方向o2為泰森多邊形倒數(shù)第二個(gè)點(diǎn)到最后一個(gè)點(diǎn)到求出的矩形頂點(diǎn)V1，如果o1=o2，那矩形頂點(diǎn)V1就添加進(jìn)vor_cell表里，若o1≠o2則矩形頂點(diǎn)V2就添加進(jìn)泰森多邊形頂點(diǎn)表里。然后判斷第一個(gè)點(diǎn)在矩形哪一條邊上，如圖1.13的A點(diǎn)在V4V3邊上，剛剛計(jì)算的o1不用再重復(fù)算了，現(xiàn)在只用重新計(jì)算o2。方向o2為矩形頂點(diǎn)V4到泰森多邊形第一個(gè)點(diǎn)到泰森多邊形第二個(gè)點(diǎn)，如果o1=o2那么當(dāng)然就需要在vor_cell里添加進(jìn)V4點(diǎn)，而如果o1≠o2，那么當(dāng)然要添加的點(diǎn)就是V3了

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?還有就是，你可能覺得添加角除了在第一點(diǎn)和最后一點(diǎn)之間有可能要添加以外，中間連每個(gè)外心的時(shí)候也有可能夾得有矩形的角呢？這確實(shí)，所以你可以判斷當(dāng)前的外心是否在矩形外，如果在，那么在這"一進(jìn)一出"的過程中就有可能夾得有矩形的角，所以你可以只在外心在矩形外時(shí)判斷需不需要加角，但是考慮到矩形最多也就4個(gè)角，所以可以用一個(gè)計(jì)數(shù)變量cnt來計(jì)算此時(shí)已經(jīng)添加了幾個(gè)角，如果cnt已經(jīng)等于4了，就沒必要再檢查需不需要添加角了。

? ? ? ??二、當(dāng)該簇三角形是內(nèi)部三角形時(shí)：

? ? ? ? ? ? ????此時(shí)沒有第一個(gè)和最后一個(gè)三角形之說

? ? ? ? ? ? ??? 所以本身這個(gè)時(shí)候，直接將每個(gè)三角形的外心按順序連起來即可。不過由于咱們有設(shè)定矩形邊界，所以如果本身的泰森多邊形超過了矩形框，就需要被限制了、只用留下在矩形邊界內(nèi)的部分即可。

? ? ? ? ? ? ??? 那么在此時(shí)具體怎么連出泰森多邊形呢？

比如圖1.14以O(shè)為中心的一簇三角形是內(nèi)部三角形(中心點(diǎn)O不在三角網(wǎng)邊界上)，該簇三角形得到的泰森多邊形就是ABCDE。怎么連出來的呢？比如可以一條條邊的算，這樣判斷是否需要添加角的時(shí)候就不會(huì)多不會(huì)少。此時(shí)假設(shè)第一個(gè)外心是A、它在矩形內(nèi)，第二個(gè)外心是B也在矩形內(nèi)，那第一條邊就是AB，然后第三個(gè)外心發(fā)現(xiàn)在矩形的外部，所以當(dāng)然求出交點(diǎn)C，那第二條邊就是BC，然后該第三個(gè)外心連接第四個(gè)外心了，當(dāng)然第三個(gè)外心在矩形外部，所以求出交點(diǎn)D，所以第三條邊就是DE了，然后就已經(jīng)完成從第一個(gè)外心A連到最后一個(gè)外心E了。有了這一條條邊，就可以判斷什么時(shí)候需要添加角了，當(dāng)然就算有添加角的情況，最多也只會(huì)添加一個(gè)角，現(xiàn)在兩條邊之間不可能夾得有兩個(gè)矩形頂點(diǎn)，這顯然從幾何上講就不可能。把一條條邊拿出來，第一條邊是AB、第一條邊兩個(gè)點(diǎn)直接添加進(jìn)泰森多邊形頂點(diǎn)表，第二條邊是BC，檢查AB與BC之間是否需要加角，發(fā)現(xiàn)第一邊最后一個(gè)點(diǎn)就是第二條邊的第一個(gè)點(diǎn)、剛好是能連接上的、這中間不可能夾有矩形頂點(diǎn)，所以第二條邊的第二個(gè)點(diǎn)放入泰森多邊形頂點(diǎn)表vor_cell里，然后第三條邊是DE，發(fā)現(xiàn)第二條邊的第二點(diǎn)C不是第三邊的第一點(diǎn)D，所以C到D之間就可能夾有矩形頂點(diǎn)，所以就判斷是否需要加矩形頂點(diǎn)即可、需要就加不需要就把該邊兩個(gè)點(diǎn)都放入泰森多邊形頂點(diǎn)vor_cell表里。然后所有邊都檢查完了，那當(dāng)然，就還要檢查最后一點(diǎn)和第一點(diǎn)之間有沒有夾有矩形的頂點(diǎn)，如果有就添加如果沒有那所有的泰森多邊形頂點(diǎn)都添加完畢了！

????????這不就搞定了？

? ? ? ? 然后講一些細(xì)節(jié)。

? ? ? ? 首先在整體的理解一下，一個(gè)泰森多邊形可以說就是一簇三角形的外心連接起來得到的。但是當(dāng)某簇三角形是邊緣三角形時(shí)(該簇三角形的中心點(diǎn)在三角網(wǎng)邊界上)，第一個(gè)三角形不存在上一個(gè)外心、最后一個(gè)三角形不存在下一個(gè)外心，所以此時(shí)對(duì)于第一個(gè)三角形就要利用第一邊、對(duì)于最后一個(gè)三角形就要利用最后一邊。對(duì)于第一邊要作垂直于它的射線和矩形相交，但是射線的方向就要確定，所以判斷第一個(gè)三角形的外心是否在第一條邊外側(cè)。如果該外心在第一邊外側(cè)，則射線方向就是第一邊中點(diǎn)指向該外心的、射線的起點(diǎn)是該外心；如果該外心不在第一邊外側(cè)，則射線方向就是該外心指向第一邊中點(diǎn)、射線的起點(diǎn)當(dāng)然還是該外心。然后對(duì)于最后一邊也是同理，判斷最后一個(gè)外心是否在最后一條邊外側(cè)，以此來判斷垂直于最后一條邊的射線的方向。

? ? ? ? 關(guān)于一個(gè)點(diǎn)是否在三角形一邊的外側(cè)，可以這么定義：如圖1.15有一個(gè)三角形

假設(shè)△ABC的頂點(diǎn)方向是順時(shí)針或逆時(shí)針。然后有一點(diǎn)P，第一條邊和P連起來的方向是ABP、是順時(shí)針的，第二條邊和P連起來的方向BCP也是順時(shí)針的，第三條邊和P連起來的方向CAP是逆時(shí)針的，所以此時(shí)P點(diǎn)在三角形外部且P點(diǎn)必然在第三條邊CA的外側(cè)。也就是說，三角形每個(gè)邊和某點(diǎn)P連起來得到相應(yīng)的順序，假設(shè)得到的三個(gè)方向是不同的，那么哪一邊得到的那個(gè)方向不同就說明P在哪一邊外側(cè)。所以顯然，一個(gè)點(diǎn)不可能同時(shí)在三角形兩條邊的外側(cè)，如果點(diǎn)在三角形外部，則必然只在某一條邊的外側(cè)。

? ? ? ? 所以比如判斷第一個(gè)三角形的外心是否在第一邊的外側(cè)很簡(jiǎn)單，剛剛上文用了比較長(zhǎng)度的方法，但當(dāng)然用叉乘的計(jì)算量是更小的，所以當(dāng)然建議用叉乘來算。在上文中講了，edges邊表里每條邊的方向都是指向該簇三角形中心的，如下圖，假設(shè)該簇三角形的中心點(diǎn)是A

所以算出方向BAP和方向CAP是相同的，說明P在三角形外側(cè)，那么就需要看P是否在第一邊外側(cè)，假設(shè)現(xiàn)在的第一邊是CA吧，那么你就可以利用另一條邊判斷P是否在第一邊外側(cè)。如下圖

這樣，方向CAP和方向CBP相同，說明P在CA或CB邊外側(cè)，而剛剛第一次計(jì)算已經(jīng)知道P在BA或CA邊外側(cè)，那當(dāng)然，P是不可能同時(shí)在兩條邊外側(cè)的，所以一定可以確定P在CA邊外側(cè)

? ? ? ? 然后是射線和矩形求交點(diǎn)。求交點(diǎn)這里不用用任意兩條直線求交點(diǎn)的方式，因?yàn)榫匦蔚倪叢皇撬降木褪秦Q直的，所以寫一個(gè)水平線和直線求交點(diǎn)和豎直線和直線求交點(diǎn)的函數(shù)即可。這樣不僅減小計(jì)算量而且也增加了精確度，因?yàn)楦↑c(diǎn)數(shù)運(yùn)算一大堆的話，誤差就會(huì)變大。然后還需要注意，比如當(dāng)射線和矩形的交點(diǎn)是矩形的頂點(diǎn)的時(shí)候，當(dāng)然不能重復(fù)了，所以求交點(diǎn)的時(shí)候，矩形每條邊都只保留一個(gè)端點(diǎn)、另一個(gè)端點(diǎn)取不到，這樣算射線和矩形的交點(diǎn)時(shí)就不重不漏了，如下圖，矩形每邊分離開看得更清楚

? ? ? ? 當(dāng)然前面一開始也說了，我寫的這個(gè)庫會(huì)生成的是百分百正確的泰森多邊形，所以，哪怕是一個(gè)或者兩個(gè)離散點(diǎn)，同樣也可以生成泰森多邊形！要知道三角網(wǎng)當(dāng)然至少需要3個(gè)點(diǎn)，那樣才能連成一個(gè)三角形。但是低于3點(diǎn)要生成泰森多邊形呢？那當(dāng)然直接討論一下即可。首先一個(gè)點(diǎn)很簡(jiǎn)單，剛剛說了矩形框里是要包含所有離散點(diǎn)的，所以一點(diǎn)生成泰森多邊形就會(huì)得到矩形框。而兩點(diǎn)的話，作這兩點(diǎn)連成的邊的中垂線、和矩形會(huì)有兩個(gè)交點(diǎn)，然后再把矩形的頂點(diǎn)補(bǔ)上就能得到兩個(gè)泰森多邊形了

? ? ? ??在有了泰森多邊形以后，就可以做各種各樣的效果了，比如下圖這樣的效果，大家稍微動(dòng)動(dòng)腦就能做出這種效果，因?yàn)槿绻麜?huì)生成泰森多邊形了，那沒有理由連如此簡(jiǎn)單的效果都想不到怎么做

因?yàn)橛辛颂┥噙呅?，所以可以利用clip，讓圓放大、并用泰森多邊形形狀的clip限制住圓的范圍，如果這樣簡(jiǎn)單的思路都想不到，那么你應(yīng)該好好反思了（很多東西大家應(yīng)該能自己想到，沒理由每一步都要?jiǎng)e人幫忙，那比如我自己一直是自學(xué)的沒人教我，那我是怎么想出來那些算法和代碼的呢）。其實(shí)此時(shí)最多也就考慮一下圓最大放大到多大，這很簡(jiǎn)單，算bbox找到最大的一個(gè)泰森多邊形的即可，然后就可以設(shè)定圓的半徑了，只要能覆蓋住最大的泰森多邊形就行了。

? ? ? ? 另外，我這個(gè)取名叫polyc的庫，其中的c指的是cell，意思是這是一個(gè)生成多邊形細(xì)胞的庫，所以我取了這么一個(gè)名字。

? ? ? ? 然后具體代碼在相應(yīng)的視頻里講

????????然后下面是我的函數(shù)庫和其他函數(shù)庫的對(duì)比測(cè)試。在同樣的取點(diǎn)方式下、取同樣的點(diǎn)數(shù)、在同樣的邊界框內(nèi)的對(duì)比：

取點(diǎn)方式都是相同的，采用之前我講過的自己的取點(diǎn)方式，如下圖：

取一萬個(gè)點(diǎn)生成一萬個(gè)泰森多邊形，寬1000高600的bbox：

我的庫：0.6到0.7秒（當(dāng)然根據(jù)電腦的情況決定，電腦不好的時(shí)候就能花0.8秒）

老外的庫：23到35秒（當(dāng)然根據(jù)電腦的情況決定）

其中截圖"紅筆"勾出的是domo前輩寫的ranpoint，這個(gè)ranpoint就是直接調(diào)用老外寫的函數(shù)庫，可以看到老外的這個(gè)庫，生成10000個(gè)點(diǎn)竟然耗費(fèi)了將近30秒。當(dāng)然文章前面也說了，老外的這個(gè)庫，有很高的幾率會(huì)出現(xiàn)bug、生成錯(cuò)誤圖形

DD子前輩的庫：

DD子前輩的庫同樣有很高的幾率生成錯(cuò)誤圖形，給我的感覺是有40%到90%的幾率生成錯(cuò)誤圖形，甚至基本上每次應(yīng)用都會(huì)出錯(cuò)。下面只用了1000個(gè)點(diǎn)生成泰森多邊形，居然耗時(shí)了接近6秒鐘，得到了一個(gè)錯(cuò)誤圖形

放大看的話，不僅有奇怪的突出，還有多邊形的重合，矩形的角落也出現(xiàn)了缺失

泰森多邊形細(xì)胞之間是不會(huì)出現(xiàn)重合的，所以圖中這樣有很多重合的多邊形(重合部分看著"顏色更深")是較大的錯(cuò)誤，但是前輩的這個(gè)庫這種重合問題出現(xiàn)的幾率卻非常的高。然后耗時(shí)也是，如圖一千個(gè)點(diǎn)就耗時(shí)了接近6秒

那么如果是像其他函數(shù)庫那樣測(cè)試10000個(gè)點(diǎn)呢，就會(huì)很絕望了，因?yàn)镈D子前輩的函數(shù)庫會(huì)花掉你接近半個(gè)小時(shí)的時(shí)間：

可以看到DD子前輩的函數(shù)庫只生成一張一萬點(diǎn)的voronoi圖就花了接近半個(gè)小時(shí)(而且結(jié)果是錯(cuò)誤的、有重疊)...雖然我知道很多用aeg做特效的人不在意執(zhí)行時(shí)間，不過很多時(shí)候可以只花幾秒應(yīng)用的模板，沒必要花十幾分鐘應(yīng)用，我之前的專欄有講過我有點(diǎn)測(cè)速強(qiáng)迫癥...

????????所以通過測(cè)試可以看出，我寫的這個(gè)函數(shù)庫對(duì)比其他函數(shù)庫來說，我的函數(shù)庫同時(shí)保證了正確性百分百、執(zhí)行速度非?？?、靈活度高。