【Aegisub】极度高效的拆字算法、连通域提取
注：本文是讲拆字算法 (连通域提取) 的，并不是我模拟笔画拆分、虚假笔画分割（软件：Aegisub） 这个视频里的拆假笔画算法，那个是我写的另一个算法，希望不了解拆字的小伙伴不要搞错了。
本回给大家介绍一个可以说目前为止最优的拆字算法。我之前懒得写，直接用的现成的，但是后来无意中发现前辈们的算法是有些可修复的问题的。比如kyanko前辈，还是像之前文章提到过的，kyanko前辈几乎所有函数的执行效率都特别的低，而且相应的拆字算法是会出错的，然后domo前辈的拆字算法速度就稍快一点，但是算法本身也是带有错误的（下文都会具体说明）。所以为了水教程，我就自己写了一个拆字算法，这个方法一样是没有其他人提出过，同时也是目前我知道的所有拆字算法中正确率最高、执行速度最快的算法（请看完全文、请看完全文、请看完全文）
然后先是几种拆字算法的对比（从正确率和速度上）：
用kyanko前辈的拆字，如图1.01
就一个字循环100次，花费了0.437秒
而如果用其他拆字算法测速，就有图1.02
我自己的拆字是用了0.050秒，domo前辈的拆字用了0.074秒 ( 分别比0.437秒快了8.74倍和5.9倍 )
用于测速的绘图是m 15 58 l 15 59 l 18 53 l 18 52 b 17 52 17 52 16 53 b 18 50 19 48 21 45 l 20 45 l 18 48 b 19 44 23 39 27 34 b 32 28 36 27 39 29 b 41 32 41 34 38 35 b 38 36 37 36 37 36 b 36 36 35 36 35 36 b 32 38 29 40 26 44 b 24 47 21 50 17 56 b 16 57 16 58 15 58 l 15 58 m 43 59 l 49 59 l 49 56 b 48 56 46 57 45 58 b 44 58 44 59 43 59 l 43 59 m 48 68 l 47 68 b 45 68 40 69 32 70 b 31 70 31 70 30 70 b 24 72 21 71 21 68 b 21 68 21 67 22 66 b 22 65 23 65 23 65 b 23 65 23 65 23 64 b 23 63 24 63 24 63 b 30 62 34 61 35 60 b 38 59 41 58 46 55 b 47 54 48 53 49 53 l 49 49 b 48 49 46 49 45 49 b 43 49 41 49 40 49 l 37 49 b 34 49 33 48 32 47 b 32 45 34 43 38 42 b 38 42 38 41 38 41 b 41 40 44 38 46 38 b 47 38 47 37 48 37 b 49 37 50 36 50 35 l 50 27 b 50 26 50 26 49 26 b 49 23 50 21 53 20 b 56 20 57 21 57 23 l 56 24 b 56 26 56 29 57 32 l 57 35 b 57 35 57 36 57 36 b 60 36 62 35 64 35 b 67 36 69 38 71 39 l 70 40 b 71 41 71 42 70 43 b 70 44 69 45 67 45 b 67 45 66 45 66 45 b 65 45 64 46 62 47 b 61 48 61 48 60 49 b 60 49 60 49 60 49 b 57 50 56 51 56 52 b 56 53 56 54 56 55 b 57 56 57 57 57 58 l 63 58 b 71 57 75 58 76 61 b 75 64 74 65 71 66 l 68 66 b 66 66 64 66 62 66 b 59 66 57 67 57 68 b 56 71 55 74 55 77 b 55 78 55 79 55 80 b 55 82 54 84 54 85 b 53 87 52 89 52 91 b 51 94 50 97 49 98 b 48 98 48 97 48 97 b 48 97 48 96 48 96 b 47 89 47 84 47 81 b 47 76 47 72 48 68 l 48 68
以上几种拆字的速度对比，全部是使用了bounding的 (kyanko前辈本身已经对齐了不用加)，所以当然绘图的平移也是算在内的，并且以上只是举个例子，但是我实际做过各种测试，当然结果和上面的举例是一样的。（放心，没有重复操作，如果大家对速度有疑问可以自己动手测试，正所谓实践是检验真理的唯一标准）
然后进行正确性的对比：
domo前辈的拆字算法中，需要判断外部内部，还要计数计算包含多少个之类的，但是显然这不是正确的(且在有大量多层包含的时候执行速度会极度减慢)，下图1.03
老实说，这个图并没有出现m与m之间的相交，所以本来该是可以正确拆开连通域的，但是如果光是数数，就肯定是不对的
图1.03的绘图代码为m 0 0 l 280 0 l 290 240 l -30 220 m 110 40 l 230 110 l 230 210 l 20 200 l 10 130 m 130 80 l 50 120 l 80 190 l 190 170 m 130 100 l 90 130 l 120 170 l 160 160 m 130 120 l 140 150 l 130 150 l 110 130
kyanko前辈的拆字算法，不仅有判断包含，也有绘图方向的判断，其实之前提过，kyanko前辈的函数慢是有很多原因导致的，尤其是，一个函数慢了以后，将其作为辅助函数到处的使用，那就会影响一堆函数的速度。。扯远了，kyanko前辈应该是没有弄清楚绘图的填充规则，正如之前的视频所说，assdraw的绘图填充方式是和svg的non-zero规则一样的，所以其实不能说绘图方向相反就一定出现掏空之类的，那样不太严谨，虽然大部分情况是"够用"的
所以同样，所有诸如图1.03那样的绘图，用kyanko前辈的算法也是不能正确拆开的。
我感觉kyanko前辈在写拆字算法的时候，一定程度上受到了domo前辈的影响，导致陷入了惯性思维。我自己写拆字的时候，因为意识到绘图的填充规则是non-zero，所以一开始就尽量地在往交点计数的方向思考，不过后面想的实际算法居然更加简洁
先提一下连通域是什么意思。如下面两个图
惊奇判断
为什么叫惊奇判断呢，因为我自己瞎取的名字，因为莫名的好听。那么惊奇判断指的是什么呢，指的是判断一个m是否构成新的连通域。
如下图1.04
显然，第1和第3个m构成一个多连通域，然后第2个m构成一个单连通域
再比如图1.05
1和3构成一个多连通域，2构成一个单连通域，4构成一个单连通域。我们拆字的任务，实际上就是把这些连通域拆出来，那这不是很简单吗，因为......
惊奇判断：对于某个m是否构成新的连通域，只需要取出该m的第一个点(或该m的路径上的任意一点)，判断其是否包含在除该m以外的所有m构成的绘图中，如果点是在内的，那么显然该m不构成新的连通域，反之，该m构成新的连通域，以此，来直接划分出各个连通域
举例说，比如上图1.05。我们首先判断谁都可以，比如咱们判断3，获取第3个m的第一个点，判断该点是否在除第3个m以外的所有m组成的绘图中，发现是在的，那3就不会自己跳出去构成一个新的连通域。然后判断比如2，取2的第一个点，判断它在不在除2以外的所有m构成的绘图中，欸，不在，那2就会构成新的连通域，将第2个m放进某个表里存起来。然后再比如判断第4个，同样使用惊奇判断，得到结论，4也是会构成新的连通域的，然后判断1同样也是会构成新的连通域。如此一来，就有1、2、4一定会参与构成三个连通域，那么接下来，剩一个3，直接判断3包含于1、2、4中的哪个就行了！
再来一个例子，比如图1.06
利用惊奇判断，得到结果1构成一个新的连通域，而2、3不构成新的连通域，然后再判断2、3都包含于1，所以1、2、3共同构成一个连通域
这个算法既没有大量地判断不必要的包含关系、也没有判断完全不需要判断的绘图方向，assdraw是用的和svg一样的non-zero规则,所以就连自交图形的填充方式，你都能瞬间知道，而如果判断路径方向的话，自交路径的方向是啥？所以，利用惊奇判断，对任意没有m与另一m碰撞/相交的绘图，都能百分百绝对正确的高效拆分
那么接下来，就是拆字、连通域提取的伪代码了：
取出每个m放进m_tbl表里。建立最终要返回的表final
建立cnt表，目的是记录提取的m
对m_tbl中每个m：
取其第一点，
判断此点是否包含于除该m以外的所有m构成的绘图中
如果不包含就提取出该m，让final[#final+1]={ 该m }，cnt[#cnt+1]=此时索引
endfor
利用cnt，去掉原始m_tbl中所有已经被提取出的m
对每个final，建立临时表domain为了装连通域
对m_tbl里每个m
检查其是否包含于final[i][1]里，如果包含于，那么在domain这个表里添加进该m
endfor
local s=final[i][1]连接table.concat(domain)
计算bbox，重新赋值final[i]={ s=s，x=cx，y=cy }
endfor
返回final表
endfunction
啊对，忘了说，之前讲过怎么高速判断点是否在某绘图内部，可以仔细看以前的视频
那么下面就是代码了：
判断点是否在m_tbl构成的绘图内：
惊奇判断：
连通域提取：
还是那句话，实践是检验真理的唯一标准、实践是检验真理的唯一标准、实践是检验真理的唯一标准。我认为大家需要提高个人写代码的能力，因为很多人直接用别人的代码，甚至不知道哪一种代码的执行速度更快，甚至不知道有些代码是错误的，起码你学习一下，至少能自己看出来别人的代码为什么执行速度比较慢吧？这就是为什么我一直在视频里倡导大家自己多练习代码的原因之一
我自己有点强迫症，一般会让代码在确保正确性优势的情况下，再对代码速度进行加速优化（那当然除非有的时候我懒得写，哇哈哈，哇哈哈，哇哈哈哈）
不知道此时你有没有发现一丝异样？为何我贴了所谓的代码截图，却没有复制过来代码？为何我在上文反复强调要自己写代码？那是因为上面的代码我留了一个错误、而且留了一个可以提速的机会！！你看，这多好，这让你可以在确保正确率和速度方面得到锻炼，哇哈哈，哇哈哈，哇哈哈哈
哪有写文章还留伏笔的？那当然是文章的作者了，对吧
那么接下来，讲一下上文中的错误在哪，以及如何提速。首先惊奇判断当然是没错的，那么错在哪呢？错在后面的判断包含关系时，默认了m只会包含于一个m里，而实际上，比如图1.07，很显然，比如第6个m，它不会构成新的连通域，但是在后面判断包含的时候，6同时包含于1、3、5，那么你怎么知道6该和哪一个m构成正确的连通域呢
其实出现图1.07这样的情况只有一种可能，那就是出现了套娃！因为我们知道，任意两个m之间是不会相交的，那么这就很好办了，如果一个m有同时包含于其他多个m的话，该m一定是与这多个m当中最小的一个m合作构成连通域，所以咱们只需要一开始bounding一下就可以了一开始就按bounding box从小到大来排列每一个m，这样后面判断包含的时候，就不会有任何担心了。强调一点，因为最后我们一定会对每个拆出的部件进行bounding，所以其实现在一开始求bounding是完全不多余的操作，而且一开始得到的bounding可以储存起来，然后后面就不需要重复求bounding了。
那么然后就是讲算法怎么提速了。其实上文中有一个明显的点，就是进行了重复匹配，我以前也说过，匹配本身算是很耗时的一种操作，所以如果能不重复匹配的情况下就不要重复匹配，比如kyanko前辈的很多函数里就有大量的重复匹配，导致速度极慢，所以大家匹配的时候要注意尽量不要匹配一遍以后又在哪又匹配一遍。那么上文中哪里重复匹配了呢？那就是对每个m的重复匹配，因为上文的算法中，不停地、不停地在重复匹配每个m里的点[-.%d]+ [-.%d]+，可是每个m里，那些点不都是一样的吗，那么匹配一遍存起来不就完了？为什么要重复匹配？上文算法里，判断点包含以及惊奇判断，都是在不停地匹配m里的点，而这些点又不可能变，不需要重复匹配。
那么现在给出，目前所有拆字算法中正确率最高、且速度最快的算法的代码：
local function line_isect(x1,y1,x2,y2,y)
local top,bottom=math.min(y1,y2),math.max(y1,y2)
if y>=top and y<bottom and bottom-top>1e-4 then
return x1+((x2-x1)/(y2-y1))*(y-y1)
end
end
判断点是否在m_tbl构成的绘图内：
function Xshape.pt_in_paths(m_tbl,pt_x,pt_y)
local cnt=0
for m=1,#m_tbl do
local pt=m_tbl[m]
for i=1,#pt-1 do
local x=line_isect(pt[i][1],pt[i][2],pt[i+1][1],pt[i+1][2],pt_y)
if x and x<=pt_x*1 then
cnt=cnt+Xshape.sgn(pt[i+1][2]-pt[i][2])
end
end
end
return cnt~=0
end
惊奇判断：
function Xshape.new_domain(m_tbl,m_idx)
local cnt=0 local pt_x,pt_y=m_tbl[m_idx][1][1],m_tbl[m_idx][1][2]
for m=1,#m_tbl do
if m~=m_idx then
local pt=m_tbl[m]
for i=1,#pt-1 do
local x=line_isect(pt[i][1],pt[i][2],pt[i+1][1],pt[i+1][2],pt_y*1)
if x and x<=pt_x*1 then
cnt=cnt+Xshape.sgn(pt[i+1][2]-pt[i][2])
end
end
end
end
return cnt==0
end
连通域提取：
function Xshape.domain_split(ass_shape,mode)
local m,m_tbl,cnt={},{},{} local ass_shape=ass_shape:gsub(' *$','')..' ' local info,final={},{}
for each in ass_shape:gmatch('m[^m]+') do
info[#info+1]={each,Xshape.bbox(each)}
end
table.sort(info,function (a,b)
return a[2].w*a[2].h<b[2].w*b[2].h
end)
for i=1,#info do
local pt={}
for x,y in (info[i][1]):gmatch('([-.%d]+) ([-.%d]+)') do
pt[#pt+1]={x,y}
end
if pt[1][1]~=pt[#pt][1] or pt[1][2]~=pt[#pt][2] then
pt[#pt+1]={pt[1][1],pt[1][2]}
end
m[#m+1]=pt
end
for i=1,#m do
if #m[i]<3 then
cnt[#cnt+1]=i
else
if Xshape.new_domain(m,i) then
m_tbl[#m_tbl+1]={m[i]} final[#final+1]=info[i] cnt[#cnt+1]=i
end
end
end
for i=#cnt,1,-1 do
table.remove(m,cnt[i]) table.remove(info,cnt[i])
end
for i=1,#m_tbl do
local domain={}
for i2=#m,1,-1 do
local pt_x,pt_y=m[i2][1][1],m[i2][1][2]
if Xshape.pt_in_paths(m_tbl[i],pt_x*1,pt_y*1) then
domain[#domain+1]=info[i2][1] table.remove(m,i2) table.remove(info,i2)
end
end
local s,cx,cy=Xshape.align_by_bbox(final[i][1]..table.concat(domain),final[i][2],mode)
final[i]={s=s,x=cx,y=cy}
end
return final
end
另：我这个拆字算法甚至允许你填入的绘图有孤立点！而对于其他的拆字算法，输入有孤立点的绘图当然就有可能会拆字错误！
所以其实总结来说，拆字算法也就几步而已：惊奇判断、判断点包含、连通域提取
可以测试：m 0 0 l 256 1 l 262 166 l -9 169 m 93 10 l 63 9 l 64 36 l 97 35 m 71 13 l 91 14 l 95 34 l 67 33 m 87 17 l 75 17 l 73 31 l 91 30 m 79 21 l 85 20 l 88 28 l 77 28 m 74 19 l 71 19 l 69 26 l 72 24 m 69 71 l 39 70 l 40 97 l 73 96 m 47 74 l 67 75 l 71 95 l 43 94 m 63 78 l 51 78 l 49 92 l 67 91 m 55 82 l 61 81 l 64 89 l 53 89 m 50 80 l 47 80 l 45 87 l 48 85 m 49 40 l 19 39 l 20 66 l 53 65 m 27 43 l 47 44 l 51 64 l 23 63 m 43 47 l 31 47 l 29 61 l 47 60 m 35 51 l 41 50 l 44 58 l 33 58 m 30 49 l 27 49 l 25 56 l 28 54 m 110 36 l 247 39 l 239 142 l 106 136 l 108 37 m 231 48 l 124 45 l 114 131 l 235 135 m 225 51 l 131 49 l 119 127 l 233 131 m 139 55 l 158 53 l 157 64 l 142 66 m 3 -24 l 59 -24 l 56 -7 l 1 -7 m 136 -25 l 74 -22 l 74 -5 l 133 -1 l 148 -4 m 169 55 l 216 57 l 225 125 l 166 125 m 206 61 l 176 60 l 173 122 l 220 122 m 181 62 l 204 64 l 217 120 l 176 120 m 94 82 m 50 123 m 89 149 m 188 65 l 180 117 l 215 117 l 199 67 m 190 73 l 196 71 l 212 113 l 185 114 m 197 81 l 193 76 l 191 112 l 205 111 m 4 106 l 46 112 l 47 161 l 3 162 m 13 115 l 41 117 l 43 154 l 8 157 m 34 123 m 2 -4 m 35 128 l 15 129 l 19 150 l 41 148
以上这个绘图字符串，拆100次的速度对比如图1.10
我自己的拆字用时0.062，而domo前辈的拆字用时0.56，我自己的拆字在速度上快了9.03倍，前辈们的算法速度慢当然是因为在这种有很多套娃出现的情况下，进行多次无意义的包含判断导致的。另外，上面这个测试绘图代码，只有我自己的算法能正确拆分，用其他的拆字算法就会错误拆分，而且速度还会慢6到9倍。
本文写于2021年1月11日晚（做个测试, 看看我过久以后才会发布这篇专栏）
