【Aegisub】泰森多边形、voronoi细胞生成算法

2021-12-18 14:55 作者:多华宫与火火里 0人读过 | 我要投稿

因为见到的几个泰森多边形函数库都有一些bug和问题，所以我自己写了一个生成泰森多边形的函数库。我自己写的这个函数库正确度百分之百、灵活度更高、执行速度很快。而比如老外写的那个Voronoi就有相当严重的bug (https://gist.github.com/tnlogy/9081637也同https://bitbucket.org/Jmaa/luafortune/src)，有超高的几率出现bug，而我写的这个库，是目前唯一一个能得到百分百正确的泰森多边形图案的库，不仅正确率有完全的优势，而且拥有更高的灵活度，执行速度也非常快。我的库和其他库的对比测试在文章末尾！

先看看实际生成的泰森多边形都是怎么样的（顺便附带了作为生成泰森多边形基础的三角网图案）。先看效果，然后再讲算法，这些算法都是我自己想的，我也会很细致具体的讲清楚

如图1.01，这是用一张随机的三角网生成的泰森多边形，并且还人为设定了边界范围。可见在原有的三角网范围上，横向和纵向的边界范围全部扩大了。

那么当然也可以就用原本的三角网的范围来设定泰森多边形的边界，如图1.02

对于边界的设定，只要确保边界框是能包含住所有的离散点就都可以生成相应的voronoi cell（泰森多边形细胞）。然后图1.03，还是一张随机的三角网，但是设定的泰森多边形边界在几个方向都扩大了

因为该函数库生成voronoi cell是基于任意三角网的，所以圆形的三角网当然也可以，如图1.04

当然还是一样的，泰森多边形的边界范围可以自定义，所以也可以弄大的边界，如图1.05

还有大家熟悉的矩形的三角网生成的泰森多边形，如图1.06

边界扩大一点看看，如图1.07

当然我不太喜欢基于矩形三角网生成的泰森多边形，你瞧瞧，上面两张图，边界上的泰森多边形也太"规则"了吧？我都泰森多边形了，我要更随机的，那好看啊，这矩形三角网生成的泰森多边形边界基本都这么工工整整的、这么规则完全不好看。

说了一堆，那么什么是泰森多边形呢？之前讲过三角网的生成算法，其实在生成的三角网基础上就可以继续生成泰森多边形。三角网有几个顶点就对应几个泰森多边形，也就是，以某一个顶点为中心的一簇delaunay三角形就可以来生成一个泰森多边形，简单来说，将这一簇三角形的外心按顺序连接起来就可以得到这一簇三角形对应的泰森多边形了，如图1.08（其实看刚刚上面的几个图应该就很容易看出来了）。

图1.08中，这些黑色顶点是随机的离散点，然后根据这些随机点生成了一张三角网，也就是这些黑线连成的三角网。有了三角网，就可以根据这三角网生成泰森多边形了，有几个随机点就会生成几个泰森多边形细胞。比如P这个点，以P这个点为中心的三角形一共有6个，把这一簇三角形的外心按顺序连起来就得到了以P这个点为中心的voronoi cell，即多边形ABCDEF。三角形的外心当然就是三角形三条边的中垂线的交点了。显然现在图1.08中一共有10个黑色的离散点，所以相应的voronoi cell也有10个，也就是红线连出的那一个个泰森多边形细胞。在知道了voronoi是什么以后，就可以考虑具体的算法了。

那么现在就有几个问题需要面对：

1、在生成了随机的三角网以后，怎么找到以每个顶点为中心的一簇三角形

2、找到一簇三角形以后，怎么把三角形按照顺序排好（无论顺时针或逆时针排列都可以）

3、求出各个三角形的外心以后，如果外心超过设定的边界范围(如矩形框)怎么办（因为一个泰森多边形是靠一簇三角形的每个外心连线连起来的，但如果外心在边界外面，那连接后的图形就会超过边界范围了、就会超出矩形框了）

4、对于顶点在边界上的一簇三角形，它们没有形成“闭合”的一圈三角形, 那要怎么连成泰森多边形

对于1：首先要用到之前讲的函数，判断一个点是否是一个点集中的点，如图1.09

然后就可以根据某个三角形里是否有相应的顶点来判断这个三角形是否是属于那个顶点的一簇三角形。也就是，for循环遍历三角网的每一个顶点p[i]，再for循环遍历每一个三角形 tris[i1] 检查该三角形里有没有p[i]点，即check(tris[i1],p[i])，如果三角形里有这个顶点，说明这个三角形是以这个顶点为中心的三角形之一，于是把这个三角形装进一个临时的表里，当遍历完所有三角形时（即内层循环for i1=1,#tris do结束时），这个临时的表里就装有现在以这个顶点为中心的所有三角形

对于2：现在找到一簇三角形以后，就要对这一簇三角形排序，使它们按照顺时针或逆时针排序。观察一下图1.10

这样一簇以O点为“中心”的三角形，本身顺序是乱的，现在需要按顺序排列，不管是顺时针还是逆时针，只要朝一个方向排列就可以了。假设第一个三角形是OAE那么这个三角形里，除了O的两个点一个是A一个是E，随便任选一点作为起点，比如E，那么此时排序的第一个三角形就是OAE，然后该三角形的点除开O、E，就剩下A，那么就可以找这一簇三角形里还有哪个三角形顶点有一个是A的，因为那个三角形就一定和△OAE相邻。所以现在就能找到△OBA，只有这个三角形有顶点A，所以△OBA和△OAE相邻，那么现在得到了排序的第二个三角形OBA，而△OBA里除开O和A就只剩下B了，这样就又开始找这一簇三角形里谁还有B点，然后就可以找到△OCB也有B点，那么当然△OCB就是排序的第三个三角形了，因为它和第二个三角形OBA相邻，然后此时当然又要按照OCB里除开O、B两点，剩下的C来找第四个三角形，以此类推。

其实在找的过程中，还需要同时保存边的信息(等会会讲这样做的用处)，就是说，一开始第一个三角形是OAE，因为是从E开始的，那么第一条变为OE、第二条变为OA，每找到一个三角形，就还要记得这样把边的信息存储在另一个专门放边的表里。所以现在第三条边是OB、第四条边是OC等等等等，以此类推。不过，现在图1.10这一簇三角形是能绕一圈的，但是你生成的三角网，总有在边界的三角形，比如像图1.11这样的以O为中心的一簇三角形（举个例子,这些三角形都是随便画的...），如果该离散点在三角网的边界上的话，当然以这个点为中心的一簇三角形就不能绕着一圈了，这样意味着不是每个三角形都像刚刚那样，有两个相邻的三角形，在最边上的三角形实际只有一个相邻的三角形(如以O点为中心的三角形OEF，与它相邻的三角形只有ODE一个。同样△OAB也只有一个相邻的△OBC)，那么这样排序怎么办呢？

现在如果像刚才一样，随便找个三角形就开始排序的话是不行的。比方说，随便找△ODC为第一个三角形，OC为第一条边，那么这样找，就是OD为第二条边，找到第二个三角形ODE, 然后OE第三条边，第三个三角形就是OEF，第四条边就是OF，然后又找，哪个三角形还有F点的？啊，没了。找不到下一个和OEF相邻的三角形了，所以说，如果按照刚刚的找法，是没办法对边界的一簇三角形成功排序的。显然，现在如果要排序，就可考虑从最边上的三角形开始排序，而不是随便找一个三角形就开始排序，比如从三角形OAB开始排序、而且必须以OA为第一条边, OB就是第二条边，这样就能找到第二个三角形OBC，以此类推下去，最后就能排序完所有三角形，因为从边上开始找，就不会出现找的过程中提前找到在边上的三角形了。

所以现在要解决的问题就是如何知道三角形是不是最边上的呢？要是说刚刚那种随便一个三角形为起点的话就特别轻松舒服，但是现在的话就必须找哪个点是在最边上的，因为要让这边上的三角形排第一个的话，边上的三角形肯定只有一个相邻的，所以比如点A和点F都是只存在于一个三角形上，除了△OBA以外，这一簇三角形里没有任何一个三角形有A点，那这样当然就说明△OBA是在边上的三角形了。所以要找在最边上的三角形只需要看每个三角形的顶点，如果有哪一个顶点只是这个三角形的顶点、其它三角形都没有这个顶点的话，就能说明该三角形在边上了。

所以总结一下就是，对于任意一簇三角形，先检查有没有一个顶点只是这一个三角形的顶点，如果有，则说明这一簇三角形不是能绕一圈的三角形，所以就按最边上的三角形开始排序，如果检查出来所有顶点都同时是其它某三角形的顶点的话，说明这一簇三角形能绕一圈，此时就随便按任何一个三角形开始排序就可以了。这样就解决了排序问题，排出来的三角形当然可能顺时针或逆时针，不过这当然没有关系，只要是按顺序的，不就可以继续直接连线了吗，因为一个泰森多边形是一簇三角形的外心依次连线得到的。

在排序以后，就得到了两个临时的表，一个三角形表tris，一个边表edges。如下图

比如以A为中心，那可以得到比如表tris里第一个三角形是ABD、第二个三角形是ABC，表edges的第一条边是AD、第二条边是AB、第三条边是AC。比如以B为中心，那可以得到比如表tris里第一个三角形是ABD、第二个三角形是BDC、第三个三角形是BCA，表edges的第一条边是BD、第二条边是BC、第三条边是BA。比如以C为中心，那可以得到比如表tris里第一个三角形是CBD、第二个三角形是CAB，表edges的第一条边是CD、第二条边是CB、第三条边是CA。所以这样你就应该知道为什么刚刚说在三角形排序的同时还需要得到一个边表，因为和三角形同顺序的一条条边是有作用的，当某一簇三角形的中心点在边界时，tris表的三角形数量必然小于edges表里的边的数目，而如果某簇三角形的中心点不在边缘，那tris表里的三角形数和edges表的边数就是一样的。所以首先边表的第一个用处是，当#tris等于#edges时，说明该簇三角形不在边缘(即能绕一圈)，而当#tris≠#edges时说明该簇三角形有头有尾(即不能绕一圈)。

边表edges里储存一条条边，每条边有两个点，每条边的第二个点都为该簇三角形的中心点，所以每条边的方向可以看成是都是指向这个中心点的。如上图，以A为中心的三角形，边表的第一条是{D点，A点}、第二条是{B点、A点}、第三条是{C点、A点}。有了边表以后，比如要求第一边的中垂线啥的就很方便

对于3：现在就是计算一簇排好序的三角形的各个外心，然后连线，但是外心可能超出你设定的边界范围，如图1.12

图1.12只是一个局部，举个例子而已。比如△OAB、△OBC、△OCD、△ODA构成的这一簇以O为中心的三角形，因为他们的外心连起来就是泰森多边形，所以计算出△OAB的外心P1、△OBC的外心P2、△OCD的外心P3、△ODA的外心P4，然后因为我们的三角形是排好序的，所以直接外心按顺序连接即可。但是显然，现在连出的泰森多边形太大了，超出了上面可见的人为设定的矩形边框外，若我们只想要在矩形边界内的部分，那就需要求只和矩形相交的部分了。关于这个问题会在下文中更详细的讲解

对于4：因为图1.12里的这一簇三角形的“中心”O点并不在三角网的边界上，显然这一簇三角形也确实是绕了一圈的，而像是以A点或以D点为“中心”的一簇三角形就是在边缘的一簇三角形了，在连线的时候对于在边缘的一簇三角形，他们的连线方式就有一些小区别。很简单的道理，本来说一簇三角形的每个外心连起来就是泰森多边形了，但是如果这簇三角形在边缘，那么它就不能绕一圈了，那最后一个三角形要怎么连接下一个外心呢，它后面根本没有下一个三角形了。所以对于中心点在三角网边界的一簇三角形在连线时，对于第一个三角形就要利用它的第一条边的中垂线，对于最后一个三角形就要利用最后一条边的中垂线了，如下图。

那在简单描述了这几个问题的处理方式以后，再来细讲

首先肯定需要求比如射线和矩形框的交点，这很简单，如下图射线AB与一条直线L求交点，交点是P

射线的端点是A，方向是A到B。然后求交点很简单，先把射线当做直线来和另一条直线L求交点，假设交点是P，那如果P是射线和直线的交点的话，向量AB和向量AP的方向就应该是相同的。而当然P点本来就在直线AB上，那AB和AP当然是共线的，所以要判断向量AP和向量AB是否同向只需要进行简单的符号判断即可，如下图

只要ΔX的符号和Δx的符号相同并且ΔY的符号和Δy的符号相同，那P一定就在射线AB上，而如果P不在射线AB上的话，那么必然有ΔX的符号和Δx的符号相反并且ΔY的符号和Δy的符号相反，当然别忘了直线与射线的交点刚好是射线的端点的情况(那时Δx和Δy都等于0)

然后要求射线和矩形的交点的话，只需要保证：1、交点在矩形上，2、交点在射线上

这样就可以具体讨论中心点在边缘或不在边缘的一簇三角形怎么连成泰森多边形了。现在咱们假设一个泰森多边形的顶点要把它收集起来、放在名叫vor_cell的表里

一、当该簇三角形是边缘三角形时：

对于第一个三角形：

1、如果其外心在矩形外：则外心必在该三角形外

检查外心在边表edges里的第一条边和第二条边的哪一侧，利用叉乘判断。如下图，观察以O为中心的一组三角形，若△AOB为第一个△，那么当然第一条边是AO第二条边是BO，则判断出外心P在矩形外，令AOP为方向o1、BOP为方向o2

若o1≠o2，则以外心P为端点、指向第一边中点的射线需要和矩形求出两个交点。比如现在o1就≠o2，o1顺时针，o2逆时针

而若o1=o2，则需要判断外心在哪一条边的外侧，如下图，以O为中心的三角形，设第一个是△OAB，第二个△是OBC(三角形OBC看起来有点扁，但当然OBC不共线，看起来像一条线，其实是△OBC)

第一条边是AO、第二条是BO，此时o1的方向是AOP、o2的方向是BOP，都是逆时针，o1=o2，则判断外心P在哪一条边的"外侧"，其实用肉眼看我们知道P在BO边的外侧，那怎么算呢，有很多种方法，比如还是利用叉乘之类的，那么现在为了不太绕，就用比较好理解的方式，而不用叉乘算（下文会讲用叉乘的方式），这样看起来会更清晰，设第一边的中点为M1，求出直线PM1和直线BO的交点N，如下图如果PM1的长度²大于PN的长度²，自然说明从点P出发的射线要先经过BO这条边，才能到达AO这条边，所以P点在BO外侧。反之若PM1²<PN²则外心P就在第一条边的外侧

所以当外心P在第一边的外侧时，与第一边垂直的射线的端点是P、方向是第一边的中点指向P，所以该射线必然和矩形没有交点、不用求。而刚刚上图显然外心P在第二条边的外侧，所以与第一边垂直的射线的端点是P、方向是P指向第一边中点，所以该射线必然和矩形有两个交点、需要求

然后第一个外心的情况处理好了，就可以考虑后面的连接了，因为本来的泰森多边形只需要第一个外心直接连接第二个外心就行了，但现在有了矩形边界，就要讨论了。别忘了，现在处于第一个外心在矩形外的情况，那继续判断下一个外心(next P)是否在矩形外，如果是，则P和next P连成的线段可能和矩形有相交，也可能没有，比如P和next P在矩形的同一侧时就有可能和矩形没有相交，所以此时就写一个线段和矩形相交的函数即可。如果next P不在矩形外，那P要和next P连起来嘛，那P到next P的线段必然和矩形只有一个交点，把这个交点和next P两个点按顺序放进泰森多边形顶点表vor_cell里即可

2、如果第一个三角形外心在矩形内：

同样检查外心在边表edges里的第一条边和第二条边的哪一侧

如果外心P刚好是第一条边的中点，假设第一边是AO，计算出AO的法向量"干锅牛肉"，将向量"干锅牛肉"的起点平移到AO中点，计算向量"干锅牛肉"现在的终点是否在AO外侧，如果在，那射线方向就是该法向量方向、将其和矩形求出唯一一个交点，如果不在，那一开始求的法向量需反向、然后再将其起点平移到AO中点，然后以此为射线和矩形求出唯一交点

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

同样检查外心在边表edges里的第一条边和第二条边的哪一侧。以同样的方式求出o1、o2，若o1=o2则外心P在某一边的外侧，则继续判断它在哪一边的外侧。如下图，以O为中心的一簇三角形，第一个三角形是OAB，当然也只有这一个△，假设第一边是AO、第二边就是BO了。方向o1为AOP、方向o2为BOP，现在o1=o2

那同样的设第一边的中点是M1，求出直线PM1和直线BO的交点N，如下图，同样的，PM1²>PN²则外心P就在第二条边BO的外侧，则垂直于第一条边的射线的方向是P到M1、射线的端点是P，求出该射线和矩形边界V1V2V3V4的唯一交点

而如果PM1²<PN²则说明外心P就在第一条边AO的外侧，那么射线的方向就是M1到P、射线出发点当然还是P，如下图

而当o1≠o2时，垂直于第一条边的射线的方向是P到第一边中点、射线的端点是P，然后求出和矩形交点

然后同样，第一步处理完以后，就可以连接下一个外心了，因为现在的外心P在矩形内，所以很简单，如果下一个外心next P在矩形外，那P到next P的射线和矩形求唯一交点即可，如果next P在矩形内，那当然直接连接next P即可

对于最后一个三角形：本质上和第一个△相同,即第一个△可以看成最后一个，而最后一个△也可以看成第一个

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

设倒数第二条边是BO、最后第一边是AO，方向o1是BOP，方向o2是AOP，设最后一边的中点是M2（即AO的中点）

若o1=o2，则判断判断外心P在哪一条边的外侧，计算直线PM2和直线BO的交点N，若PM2²<PN²则说明外心P就在最后一条边AO的外侧，则垂直于最后一条边的射线的方向是M2到P、射线的起点是P，所以此时不会和矩形有交点、不用管；若PM2²>PN²则说明外心P在倒数第二条边AO的外侧，则垂直于最后一条边的射线的方向是P到M2、射线的起点是P，所以该射线需要和矩形求出两个交点

2、如果最后一个三角形外心P在矩形内：

同样判断P是否在最后一条边上(即为最后一条边的中点)，如果是，那就同样的计算最后一条边的法向量、法向量的方向是指向三角网外的、而不是指向三角网内的，然后垂直于最后一边的射线的方向就是法向量的方向

如果P不在最后一边，则同样的算o1、o2，若o1=o2，则判断P在哪一边（倒数第二条边或最后一条边）外侧，根据在哪一边外侧决定垂直于最后一条边的射线的方向，然后和矩形求唯一交点；若o1≠o2，则射线方向就是P指向最后一条边中点

对于既不是第一个也不是最后一个三角形的三角形：中间的三角形存在上一个外心和下一个外心，而泰森多边形就是一个个外心连接得到的，所以本质上能直接连接下一个外心，但是可能有的外心在矩形外

1、如果下一个外心next P在矩形外：

若当前外心P也在矩形外：

直接利用线段和矩形求交的函数！

2、如果下一个外心next P在矩形内：

若当前外心P在矩形外：

则P到next P这条线段与矩形有一个交点，那么当然该交点以及下一个外心next P都按顺序添加进泰森多边形表vor_cell里

若当前外心P在矩形内：

此时当然是最舒服的情况，直接连接下一个外心就行了，好爽啊

判断是否需要添加"角"：在从第一个三角形开始添加泰森多边形顶点到最后一个三角形添加完后，还需要判断是否需要添加"角"，也就是此时的vor_cell表里的第一个点和最后一个点之间是否"夹着"矩形的顶点，如下图

比如以O为中心的一簇三角形，计算它的泰森多边形顶点，从第一个三角形算到最后一个三角形，咱们可以得到泰森多边形的顶点A、B、C、D，但是显然此时第一个点A与最后一个点D之间夹的有矩形的顶点，那么此时就需要添加矩形的"角"。所以：

1、如果vor_cell里第一个点和最后一个点在矩形的同一条边上：

此时不需要添加新的东西了，泰森多边形已经"完整"了。那怎么判断两点有没有在矩形的同一边上呢：假设这两点是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里第一个点和最后一个点不在矩形的同一条边上：

判断第一点和最后一点之间是否只夹了一个矩形顶点。怎么判断，这很简单，直接讨论一下即可。比如，如果p1.x=x0并且p2.x≠x0并且p2.x≠x0+w，那么如果此时p2.y=y0，那么说明p1和p2之间只夹了一个矩形的顶点、并且这个顶点就是(x0,y0)，就像这样，讨论各种情况，就能判断两个点是否只夹了一个顶点。

所以如果第一点和最后一点之间只夹了一个矩形顶点，那么直接把这个矩形的顶点添加进泰森多边形表vor_cell里

然而，你认为这是对的吗？当第一点和最后一点之间只夹了一个矩形顶点的时候，其实有可能是要添加三个"角"的，因为咱们的矩形框范围是自定义的，也就是你可以扩大很多，如下图，你就会发现两点之间也有可能夹有3个矩形顶点

所以，当第一点和最后一点之间只夹了一个矩形顶点时，需要用叉乘来判断这个矩形顶点是不是可以直接添加，如果不能，就说明此时要添加矩形的三个顶点

如果第一点和最后一点之间夹了不止一个矩形顶点，那么必然需要添加两个矩形的顶点进去。首先判断最后一个点在矩形哪条边上，比如图1.13的D点在V1V2边上，那么你就需要判断到底是V1点是"泰森多边形"的顶点还是V2点是"泰森多边形"的顶点，要知道泰森多边形必然是凸多边形，所以直接利用两个叉乘来判断需要添加哪个点。方向o1为泰森多边形第一个顶点到第二个顶点到泰森多边形中心点O，方向o2为泰森多边形倒数第二个点到最后一个点到求出的矩形顶点V1，如果o1=o2，那矩形顶点V1就添加进vor_cell表里，若o1≠o2则矩形顶点V2就添加进泰森多边形顶点表里。然后判断第一个点在矩形哪一条边上，如图1.13的A点在V4V3边上，刚刚计算的o1不用再重复算了，现在只用重新计算o2。方向o2为矩形顶点V4到泰森多边形第一个点到泰森多边形第二个点，如果o1=o2那么当然就需要在vor_cell里添加进V4点，而如果o1≠o2，那么当然要添加的点就是V3了

还有就是，你可能觉得添加角除了在第一点和最后一点之间有可能要添加以外，中间连每个外心的时候也有可能夹得有矩形的角呢？这确实，所以你可以判断当前的外心是否在矩形外，如果在，那么在这"一进一出"的过程中就有可能夹得有矩形的角，所以你可以只在外心在矩形外时判断需不需要加角，但是考虑到矩形最多也就4个角，所以可以用一个计数变量cnt来计算此时已经添加了几个角，如果cnt已经等于4了，就没必要再检查需不需要添加角了。

二、当该簇三角形是内部三角形时：

此时没有第一个和最后一个三角形之说

所以本身这个时候，直接将每个三角形的外心按顺序连起来即可。不过由于咱们有设定矩形边界，所以如果本身的泰森多边形超过了矩形框，就需要被限制了、只用留下在矩形边界内的部分即可。

那么在此时具体怎么连出泰森多边形呢？

比如图1.14以O为中心的一簇三角形是内部三角形(中心点O不在三角网边界上)，该簇三角形得到的泰森多边形就是ABCDE。怎么连出来的呢？比如可以一条条边的算，这样判断是否需要添加角的时候就不会多不会少。此时假设第一个外心是A、它在矩形内，第二个外心是B也在矩形内，那第一条边就是AB，然后第三个外心发现在矩形的外部，所以当然求出交点C，那第二条边就是BC，然后该第三个外心连接第四个外心了，当然第三个外心在矩形外部，所以求出交点D，所以第三条边就是DE了，然后就已经完成从第一个外心A连到最后一个外心E了。有了这一条条边，就可以判断什么时候需要添加角了，当然就算有添加角的情况，最多也只会添加一个角，现在两条边之间不可能夹得有两个矩形顶点，这显然从几何上讲就不可能。把一条条边拿出来，第一条边是AB、第一条边两个点直接添加进泰森多边形顶点表，第二条边是BC，检查AB与BC之间是否需要加角，发现第一边最后一个点就是第二条边的第一个点、刚好是能连接上的、这中间不可能夹有矩形顶点，所以第二条边的第二个点放入泰森多边形顶点表vor_cell里，然后第三条边是DE，发现第二条边的第二点C不是第三边的第一点D，所以C到D之间就可能夹有矩形顶点，所以就判断是否需要加矩形顶点即可、需要就加不需要就把该边两个点都放入泰森多边形顶点vor_cell表里。然后所有边都检查完了，那当然，就还要检查最后一点和第一点之间有没有夹有矩形的顶点，如果有就添加如果没有那所有的泰森多边形顶点都添加完毕了！

这不就搞定了？

然后讲一些细节。

首先在整体的理解一下，一个泰森多边形可以说就是一簇三角形的外心连接起来得到的。但是当某簇三角形是边缘三角形时(该簇三角形的中心点在三角网边界上)，第一个三角形不存在上一个外心、最后一个三角形不存在下一个外心，所以此时对于第一个三角形就要利用第一边、对于最后一个三角形就要利用最后一边。对于第一边要作垂直于它的射线和矩形相交，但是射线的方向就要确定，所以判断第一个三角形的外心是否在第一条边外侧。如果该外心在第一边外侧，则射线方向就是第一边中点指向该外心的、射线的起点是该外心；如果该外心不在第一边外侧，则射线方向就是该外心指向第一边中点、射线的起点当然还是该外心。然后对于最后一边也是同理，判断最后一个外心是否在最后一条边外侧，以此来判断垂直于最后一条边的射线的方向。

关于一个点是否在三角形一边的外侧，可以这么定义：如图1.15有一个三角形

假设△ABC的顶点方向是顺时针或逆时针。然后有一点P，第一条边和P连起来的方向是ABP、是顺时针的，第二条边和P连起来的方向BCP也是顺时针的，第三条边和P连起来的方向CAP是逆时针的，所以此时P点在三角形外部且P点必然在第三条边CA的外侧。也就是说，三角形每个边和某点P连起来得到相应的顺序，假设得到的三个方向是不同的，那么哪一边得到的那个方向不同就说明P在哪一边外侧。所以显然，一个点不可能同时在三角形两条边的外侧，如果点在三角形外部，则必然只在某一条边的外侧。

所以比如判断第一个三角形的外心是否在第一边的外侧很简单，刚刚上文用了比较长度的方法，但当然用叉乘的计算量是更小的，所以当然建议用叉乘来算。在上文中讲了，edges边表里每条边的方向都是指向该簇三角形中心的，如下图，假设该簇三角形的中心点是A

所以算出方向BAP和方向CAP是相同的，说明P在三角形外侧，那么就需要看P是否在第一边外侧，假设现在的第一边是CA吧，那么你就可以利用另一条边判断P是否在第一边外侧。如下图

这样，方向CAP和方向CBP相同，说明P在CA或CB边外侧，而刚刚第一次计算已经知道P在BA或CA边外侧，那当然，P是不可能同时在两条边外侧的，所以一定可以确定P在CA边外侧

然后是射线和矩形求交点。求交点这里不用用任意两条直线求交点的方式，因为矩形的边不是水平的就是竖直的，所以写一个水平线和直线求交点和竖直线和直线求交点的函数即可。这样不仅减小计算量而且也增加了精确度，因为浮点数运算一大堆的话，误差就会变大。然后还需要注意，比如当射线和矩形的交点是矩形的顶点的时候，当然不能重复了，所以求交点的时候，矩形每条边都只保留一个端点、另一个端点取不到，这样算射线和矩形的交点时就不重不漏了，如下图，矩形每边分离开看得更清楚

当然前面一开始也说了，我写的这个库会生成的是百分百正确的泰森多边形，所以，哪怕是一个或者两个离散点，同样也可以生成泰森多边形！要知道三角网当然至少需要3个点，那样才能连成一个三角形。但是低于3点要生成泰森多边形呢？那当然直接讨论一下即可。首先一个点很简单，刚刚说了矩形框里是要包含所有离散点的，所以一点生成泰森多边形就会得到矩形框。而两点的话，作这两点连成的边的中垂线、和矩形会有两个交点，然后再把矩形的顶点补上就能得到两个泰森多边形了

在有了泰森多边形以后，就可以做各种各样的效果了，比如下图这样的效果，大家稍微动动脑就能做出这种效果，因为如果会生成泰森多边形了，那没有理由连如此简单的效果都想不到怎么做

因为有了泰森多边形，所以可以利用clip，让圆放大、并用泰森多边形形状的clip限制住圆的范围，如果这样简单的思路都想不到，那么你应该好好反思了（很多东西大家应该能自己想到，没理由每一步都要别人帮忙，那比如我自己一直是自学的没人教我，那我是怎么想出来那些算法和代码的呢）。其实此时最多也就考虑一下圆最大放大到多大，这很简单，算bbox找到最大的一个泰森多边形的即可，然后就可以设定圆的半径了，只要能覆盖住最大的泰森多边形就行了。

另外，我这个取名叫polyc的库，其中的c指的是cell，意思是这是一个生成多边形细胞的库，所以我取了这么一个名字。

然后具体代码在相应的视频里讲

然后下面是我的函数库和其他函数库的对比测试。在同样的取点方式下、取同样的点数、在同样的边界框内的对比：

取点方式都是相同的，采用之前我讲过的自己的取点方式，如下图：