注：本文是講拆字算法 (連通域提取) 的，并不是我模擬筆畫(huà)拆分、虛假筆畫(huà)分割（軟件：Aegisub）?這個(gè)視頻里的拆假筆畫(huà)算法，那個(gè)是我寫(xiě)的另一個(gè)算法，希望不了解拆字的小伙伴不要搞錯(cuò)了。

? ? ?? 本回給大家介紹一個(gè)可以說(shuō)目前為止最優(yōu)的拆字算法。我之前懶得寫(xiě)，直接用的現(xiàn)成的，但是后來(lái)無(wú)意中發(fā)現(xiàn)前輩們的算法是有些可修復(fù)的問(wèn)題的。比如kyanko前輩，還是像之前文章提到過(guò)的，kyanko前輩幾乎所有函數(shù)的執(zhí)行效率都特別的低，而且相應(yīng)的拆字算法是會(huì)出錯(cuò)的，然后domo前輩的拆字算法速度就稍快一點(diǎn)，但是算法本身也是帶有錯(cuò)誤的（下文都會(huì)具體說(shuō)明）。所以為了水教程，我就自己寫(xiě)了一個(gè)拆字算法，這個(gè)方法一樣是沒(méi)有其他人提出過(guò)，同時(shí)也是目前我知道的所有拆字算法中正確率最高、執(zhí)行速度最快的算法（請(qǐng)看完全文、請(qǐng)看完全文、請(qǐng)看完全文）

? ?? ? 然后先是幾種拆字算法的對(duì)比（從正確率和速度上）：

用kyanko前輩的拆字，如圖1.01

就一個(gè)字循環(huán)100次，花費(fèi)了0.437秒

而如果用其他拆字算法測(cè)速，就有圖1.02

我自己的拆字是用了0.050秒，domo前輩的拆字用了0.074秒 ( 分別比0.437秒快了8.74倍和5.9倍 )

用于測(cè)速的繪圖是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?

以上幾種拆字的速度對(duì)比，全部是使用了bounding的 (kyanko前輩本身已經(jīng)對(duì)齊了不用加)，所以當(dāng)然繪圖的平移也是算在內(nèi)的，并且以上只是舉個(gè)例子，但是我實(shí)際做過(guò)各種測(cè)試，當(dāng)然結(jié)果和上面的舉例是一樣的。（放心，沒(méi)有重復(fù)操作，如果大家對(duì)速度有疑問(wèn)可以自己動(dòng)手測(cè)試，正所謂實(shí)踐是檢驗(yàn)真理的唯一標(biāo)準(zhǔn)）

然后進(jìn)行正確性的對(duì)比：

domo前輩的拆字算法中，需要判斷外部?jī)?nèi)部，還要計(jì)數(shù)計(jì)算包含多少個(gè)之類的，但是顯然這不是正確的(且在有大量多層包含的時(shí)候執(zhí)行速度會(huì)極度減慢)，下圖1.03

老實(shí)說(shuō)，這個(gè)圖并沒(méi)有出現(xiàn)m與m之間的相交，所以本來(lái)該是可以正確拆開(kāi)連通域的，但是如果光是數(shù)數(shù)，就肯定是不對(duì)的

圖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前輩的拆字算法，不僅有判斷包含，也有繪圖方向的判斷，其實(shí)之前提過(guò)，kyanko前輩的函數(shù)慢是有很多原因?qū)е碌模绕涫?，一個(gè)函數(shù)慢了以后，將其作為輔助函數(shù)到處的使用，那就會(huì)影響一堆函數(shù)的速度。。扯遠(yuǎn)了，kyanko前輩應(yīng)該是沒(méi)有弄清楚繪圖的填充規(guī)則，正如之前的視頻所說(shuō)，assdraw的繪圖填充方式是和svg的non-zero規(guī)則一樣的，所以其實(shí)不能說(shuō)繪圖方向相反就一定出現(xiàn)掏空之類的，那樣不太嚴(yán)謹(jǐn)，雖然大部分情況是"夠用"的

所以同樣，所有諸如圖1.03那樣的繪圖，用kyanko前輩的算法也是不能正確拆開(kāi)的。

我感覺(jué)kyanko前輩在寫(xiě)拆字算法的時(shí)候，一定程度上受到了domo前輩的影響，導(dǎo)致陷入了慣性思維。我自己寫(xiě)拆字的時(shí)候，因?yàn)橐庾R(shí)到繪圖的填充規(guī)則是non-zero，所以一開(kāi)始就盡量地在往交點(diǎn)計(jì)數(shù)的方向思考，不過(guò)后面想的實(shí)際算法居然更加簡(jiǎn)潔

????????先提一下連通域是什么意思。如下面兩個(gè)圖

驚奇判斷

? ? ???為什么叫驚奇判斷呢，因?yàn)槲易约合谷〉拿?，因?yàn)槟暮寐?tīng)。那么驚奇判斷指的是什么呢，指的是判斷一個(gè)m是否構(gòu)成新的連通域。

如下圖1.04

顯然，第1和第3個(gè)m構(gòu)成一個(gè)多連通域，然后第2個(gè)m構(gòu)成一個(gè)單連通域

再比如圖1.05

1和3構(gòu)成一個(gè)多連通域，2構(gòu)成一個(gè)單連通域，4構(gòu)成一個(gè)單連通域。我們拆字的任務(wù)，實(shí)際上就是把這些連通域拆出來(lái)，那這不是很簡(jiǎn)單嗎，因?yàn)?.....

驚奇判斷：對(duì)于某個(gè)m是否構(gòu)成新的連通域，只需要取出該m的第一個(gè)點(diǎn)(或該m的路徑上的任意一點(diǎn))，判斷其是否包含在除該m以外的所有m構(gòu)成的繪圖中，如果點(diǎn)是在內(nèi)的，那么顯然該m不構(gòu)成新的連通域，反之，該m構(gòu)成新的連通域，以此，來(lái)直接劃分出各個(gè)連通域

? ? ? ?舉例說(shuō)，比如上圖1.05。我們首先判斷誰(shuí)都可以，比如咱們判斷3，獲取第3個(gè)m的第一個(gè)點(diǎn)，判斷該點(diǎn)是否在除第3個(gè)m以外的所有m組成的繪圖中，發(fā)現(xiàn)是在的，那3就不會(huì)自己跳出去構(gòu)成一個(gè)新的連通域。然后判斷比如2，取2的第一個(gè)點(diǎn)，判斷它在不在除2以外的所有m構(gòu)成的繪圖中，欸，不在，那2就會(huì)構(gòu)成新的連通域，將第2個(gè)m放進(jìn)某個(gè)表里存起來(lái)。然后再比如判斷第4個(gè)，同樣使用驚奇判斷，得到結(jié)論，4也是會(huì)構(gòu)成新的連通域的，然后判斷1同樣也是會(huì)構(gòu)成新的連通域。如此一來(lái)，就有1、2、4一定會(huì)參與構(gòu)成三個(gè)連通域，那么接下來(lái)，剩一個(gè)3，直接判斷3包含于1、2、4中的哪個(gè)就行了！

? ? ???再來(lái)一個(gè)例子，比如圖1.06

? ? ???利用驚奇判斷，得到結(jié)果1構(gòu)成一個(gè)新的連通域，而2、3不構(gòu)成新的連通域，然后再判斷2、3都包含于1，所以1、2、3共同構(gòu)成一個(gè)連通域

? ? ???這個(gè)算法既沒(méi)有大量地判斷不必要的包含關(guān)系、也沒(méi)有判斷完全不需要判斷的繪圖方向，assdraw是用的和svg一樣的non-zero規(guī)則,所以就連自交圖形的填充方式，你都能瞬間知道，而如果判斷路徑方向的話，自交路徑的方向是啥？所以，利用驚奇判斷，對(duì)任意沒(méi)有m與另一m碰撞/相交的繪圖，都能百分百絕對(duì)正確的高效拆分

? ? ???那么接下來(lái)，就是拆字、連通域提取的偽代碼了：

取出每個(gè)m放進(jìn)m_tbl表里。建立最終要返回的表final
建立cnt表，目的是記錄提取的m

對(duì)m_tbl中每個(gè)m：
????????????????取其第一點(diǎn)，
????????????????判斷此點(diǎn)是否包含于除該m以外的所有m構(gòu)成的繪圖中
????????????????如果不包含就提取出該m，讓final[#final+1]={?該m?}，cnt[#cnt+1]=此時(shí)索引
endfor

利用cnt，去掉原始m_tbl中所有已經(jīng)被提取出的m

對(duì)每個(gè)final，建立臨時(shí)表domain為了裝連通域
????????對(duì)m_tbl里每個(gè)m
????????????????檢查其是否包含于final[i][1]里，如果包含于，那么在domain這個(gè)表里添加進(jìn)該m
?????????endfor
?????????local?s=final[i][1]連接table.concat(domain)
?????????計(jì)算bbox，重新賦值final[i]={?s=s，x=cx，y=cy?}
endfor
返回final表
endfunction

啊對(duì)，忘了說(shuō)，之前講過(guò)怎么高速判斷點(diǎn)是否在某繪圖內(nèi)部，可以仔細(xì)看以前的視頻

? ? ???那么下面就是代碼了：

判斷點(diǎn)是否在m_tbl構(gòu)成的繪圖內(nèi)：

驚奇判斷：

連通域提?。?/strong>

? ? ???還是那句話，實(shí)踐是檢驗(yàn)真理的唯一標(biāo)準(zhǔn)、實(shí)踐是檢驗(yàn)真理的唯一標(biāo)準(zhǔn)、實(shí)踐是檢驗(yàn)真理的唯一標(biāo)準(zhǔn)。我認(rèn)為大家需要提高個(gè)人寫(xiě)代碼的能力，因?yàn)楹芏嗳酥苯佑脛e人的代碼，甚至不知道哪一種代碼的執(zhí)行速度更快，甚至不知道有些代碼是錯(cuò)誤的，起碼你學(xué)習(xí)一下，至少能自己看出來(lái)別人的代碼為什么執(zhí)行速度比較慢吧？這就是為什么我一直在視頻里倡導(dǎo)大家自己多練習(xí)代碼的原因之一

? ? ???我自己有點(diǎn)強(qiáng)迫癥，一般會(huì)讓代碼在確保正確性優(yōu)勢(shì)的情況下，再對(duì)代碼速度進(jìn)行加速優(yōu)化（那當(dāng)然除非有的時(shí)候我懶得寫(xiě)，哇哈哈，哇哈哈，哇哈哈哈）

? ? ???不知道此時(shí)你有沒(méi)有發(fā)現(xiàn)一絲異樣？為何我貼了所謂的代碼截圖，卻沒(méi)有復(fù)制過(guò)來(lái)代碼？為何我在上文反復(fù)強(qiáng)調(diào)要自己寫(xiě)代碼？那是因?yàn)樯厦娴拇a我留了一個(gè)錯(cuò)誤、而且留了一個(gè)可以提速的機(jī)會(huì)??！你看，這多好，這讓你可以在確保正確率和速度方面得到鍛煉，哇哈哈，哇哈哈，哇哈哈哈
? ? ???哪有寫(xiě)文章還留伏筆的？那當(dāng)然是文章的作者了，對(duì)吧

? ? ???那么接下來(lái)，講一下上文中的錯(cuò)誤在哪，以及如何提速。首先驚奇判斷當(dāng)然是沒(méi)錯(cuò)的，那么錯(cuò)在哪呢？錯(cuò)在后面的判斷包含關(guān)系時(shí)，默認(rèn)了m只會(huì)包含于一個(gè)m里，而實(shí)際上，比如圖1.07，很顯然，比如第6個(gè)m，它不會(huì)構(gòu)成新的連通域，但是在后面判斷包含的時(shí)候，6同時(shí)包含于1、3、5，那么你怎么知道6該和哪一個(gè)m構(gòu)成正確的連通域呢

其實(shí)出現(xiàn)圖1.07這樣的情況只有一種可能，那就是出現(xiàn)了套娃！因?yàn)槲覀冎?，任意兩個(gè)m之間是不會(huì)相交的，那么這就很好辦了，如果一個(gè)m有同時(shí)包含于其他多個(gè)m的話，該m一定是與這多個(gè)m當(dāng)中最小的一個(gè)m合作構(gòu)成連通域，所以咱們只需要一開(kāi)始bounding一下就可以了一開(kāi)始就按bounding box從小到大來(lái)排列每一個(gè)m，這樣后面判斷包含的時(shí)候，就不會(huì)有任何擔(dān)心了。強(qiáng)調(diào)一點(diǎn)，因?yàn)樽詈笪覀円欢〞?huì)對(duì)每個(gè)拆出的部件進(jìn)行bounding，所以其實(shí)現(xiàn)在一開(kāi)始求bounding是完全不多余的操作，而且一開(kāi)始得到的bounding可以儲(chǔ)存起來(lái)，然后后面就不需要重復(fù)求bounding了。

? ? ???那么然后就是講算法怎么提速了。其實(shí)上文中有一個(gè)明顯的點(diǎn)，就是進(jìn)行了重復(fù)匹配，我以前也說(shuō)過(guò)，匹配本身算是很耗時(shí)的一種操作，所以如果能不重復(fù)匹配的情況下就不要重復(fù)匹配，比如kyanko前輩的很多函數(shù)里就有大量的重復(fù)匹配，導(dǎo)致速度極慢，所以大家匹配的時(shí)候要注意盡量不要匹配一遍以后又在哪又匹配一遍。那么上文中哪里重復(fù)匹配了呢？那就是對(duì)每個(gè)m的重復(fù)匹配，因?yàn)?span id="s0sssss00s" class="color-default">上文的算法中，不停地、不停地在重復(fù)匹配每個(gè)m里的點(diǎn)[-.%d]+ [-.%d]+，可是每個(gè)m里，那些點(diǎn)不都是一樣的嗎，那么匹配一遍存起來(lái)不就完了？為什么要重復(fù)匹配？上文算法里，判斷點(diǎn)包含以及驚奇判斷，都是在不停地匹配m里的點(diǎn)，而這些點(diǎn)又不可能變，不需要重復(fù)匹配。

? ? ???那么現(xiàn)在給出，目前所有拆字算法中正確率最高、且速度最快的算法的代碼：

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

判斷點(diǎn)是否在m_tbl構(gòu)成的繪圖內(nèi)：

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

連通域提?。?/strong>

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

另：我這個(gè)拆字算法甚至允許你填入的繪圖有孤立點(diǎn)！而對(duì)于其他的拆字算法，輸入有孤立點(diǎn)的繪圖當(dāng)然就有可能會(huì)拆字錯(cuò)誤！

所以其實(shí)總結(jié)來(lái)說(shuō)，拆字算法也就幾步而已：驚奇判斷、判斷點(diǎn)包含、連通域提取

可以測(cè)試：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?

以上這個(gè)繪圖字符串，拆100次的速度對(duì)比如圖1.10

我自己的拆字用時(shí)0.062，而domo前輩的拆字用時(shí)0.56，我自己的拆字在速度上快了9.03倍，前輩們的算法速度慢當(dāng)然是因?yàn)樵谶@種有很多套娃出現(xiàn)的情況下，進(jìn)行多次無(wú)意義的包含判斷導(dǎo)致的。另外，上面這個(gè)測(cè)試?yán)L圖代碼，只有我自己的算法能正確拆分，用其他的拆字算法就會(huì)錯(cuò)誤拆分，而且速度還會(huì)慢6到9倍。

本文寫(xiě)于2021年1月11日晚（做個(gè)測(cè)試, 看看我過(guò)久以后才會(huì)發(fā)布這篇專欄）

標(biāo)簽：