一、背景和需求分析

　　拆分字体/图形的连通区域在许多其它特效工具（After Effects、TCAX）中已经有了现成的实现方式如：

　　AE拆字脚本：https://www.bilibili.com/video/av3322029
　　AE的拆字脚本提供了分析过程的控制参数，控制参数会影响到拆分的质量，且依赖于字号大小；从视频上来看，拆分单字用时较长，推测没有直接用字体的矢量信息进行计算，而是用了一些其它的方法来进行连通域的判断，不得不说效率不高。

　　TCAX(基于Python)的拆字算法：论坛挂了有空补上
　　利用了一些数学原理，比如叉乘矢量求和判断cw/ccw之类的算法，原则上需要遍历所有的控制点，具体效果和效率也没有办法进行实测。

　　几年(SuJiKiNen)编写了独立的函数库A3Shape，给Aegisub提供了一些Yutils没有提供的矢量操作函数，使得矢量特效的制作更加多样化。
　　早在很多年(5+)前，Aegisub的Lua运行环境更换成了LuaJIT，这意味着用Aegisub制作字幕时可以适当地利用现成的C接口。Youka就利用LuaJIT的特性编写了我们熟知的Yutils函数库，它利用系统的字体相关的API来直接获取字体的矢量信息并进行ASS绘图代码化，极大地丰富了字幕特效制作的玩法。
　　基于上述的Lua函数库，我们可以通过非数学的方式(从代码上看是这样，实际使用的函数多少利用了数学知识)，仅仅使用逻辑分析来拆分字体/图形中的连通域，制作新的特效。

二、Yutils部分

　　利用Yutils自带的函数进行文字转矢量绘图操作，具体代码和效果参考下图：

　　为了在后面利用矢量绘图，我们把矢量绘图的字符串存为 text, 它包含着多个连通区域；或者我们自己准备一个矢量图形，作为后续分解的对象。

三、相关概念和逻辑分析

在第四部分我分享了注释过的代码，这里先说明一下注释中使用的概念：
　　1. 最大化拆分，指的是不考虑图形的时针方向(cw/ccw)，拆出所有闭合区域，有正有负；
　　2. 图形，指连通区域，在下面的过程中大多数是指单连通域；
　　3. 该图形，指的是循环计数 i 对应的图形；某图形，指的是循环计数 j 对应的图形；
　　4. 实体点，三次贝塞尔曲线的两个控制点以外的有记录的点；
　　5. 正确定义的原图形，指的是图形两两间只存在包含和被包含关系；相对地，下图为错误定义的原图形(正常字体设计中不会出现的情况)：

• 

• 

　　这里我们预先准备了一个较为复杂的测试图形：

m 64 -15 l 134 -15 l 134 75 l 64 75 m 87 10 l 87 51 l 111 51 l 111 10 m 18 -8 l 30 -8 l 30 25 l 18 25 m -83 -31 l -70 -31 l -70 -19 l -83 -19 m -74 -13 l -20 -13 l -20 69 l -74 69 m -68 -6 l -68 8 l -28 8 l -28 -6 m -55 12 l -55 46 l -35 46 l -35 12 m -118 -71 l -118 -71 l 180 -71 l 180 111 l -118 111 m 49 -41 l 49 88 l 149 88 l 148 -41 m -96 -42 l -96 86 l -1 86 l -1 -42 m 12 -30 l 12 45 l 35 45 l 35 -30 m 37 -91 l 37 -104 l 166 -104 l 166 -91 m -118 -108 l -118 -88 l 15 -88 l 15 -108

流程：
　　text = split_by_m(text)  --原图形最大化拆分
　　record = rec(text)       --记录拆分各部分之间的包含与被包含关系
　　new_table = record_handler(record,text)  --生成新的图形table
　　shape = shape_assembler(new_table)       --按已有信息组装新的图形table

　　下图为拆分后的图形，共13个单连通域，红色对应后文的情况1，绿色对应情况2，蓝色对应情况3。

各情况举例说明：
　　情况1——独立图形
　　① 4号图形的外部图形有10和8，共2个(偶数)，且没有内部图形
　　② 12号图形既没有外部也没有内部图形
　　情况2——非最外侧的复连通域
　　① 1号图形的内部有2号图形(1个 大于等于 1)，且外部有8号和9号2个(不为0的偶数)图形
　　情况3——最外侧的复连通域
　　① 8号图形没有外部图形，内部图形数量不为0
　　下方shape_assembler函数中，我详细注释了这三种情况下的处理方式。执行一套分析下来，最终可以从13个单连通图形合并得到7个连通域的正确结果。

四、连通区域拆分使用的函数

--删除空元素的函数，以防无法按顺序访问table元素
function delete_empty(tbl,mode)
	if mode == 1 then
		for i=#tbl,1,-1 do
			if tbl[i] == "" then
				_G.table.remove(tbl, i)
			end
		end
	elseif mode==2 then
		for i=#tbl,1,-1 do
			if (tbl[i].shape_i == "" or tbl[i].shape == nil) then
				_G.table.remove(tbl, i)
			end
		end
	end
	return tbl
end

--检查表中是否存在某元素的函数
function is_include(value, tbl)
    for k,v in _G.ipairs(tbl) do
      if v == value then
          return true
      end
    end
    return false
end

--简单的字符串分割函数
function split(str, split_char)      
    local sub_str_tab = {}
    while true do          
        local pos = string.find(str, split_char) 
        if not pos then              
            _G.table.insert(sub_str_tab,str)
            break
        end  
        local sub_str = string.sub(str, 1, pos - 1)              
        _G.table.insert(sub_str_tab,sub_str)
        str = string.sub(str, pos + 1, string.len(str))
    end      
    return sub_str_tab
end

--以 "m" 为标记拆分图形(最大化拆分)，并获取部分实体坐标
function split_by_m(text)
	text = split(text,"m")
	_G.table.remove(text,1)
	point = {}
	for i=1,#text do
		point[i] = {}
		text[i] = "m"..text[i]
		for x,y in string.gmatch(text[i],"[m|l|b] (-?%d+) (-?%d+)") do
			_G.table.insert(point[i],{x = x,y = y})
		end
	end
	return text
end

--记录拆分后的图形间包含与被包含关系
function rec(text)
	new_shape_tbl = {}
	record = {}
	for i=1,#text do
		for j=1,#text do
			x,y = _G.tonumber(point[j][1].x),_G.tonumber(point[j][1].y)
			--对于正确定义的原图形，如果某图形中有任意一个实体点落入了该图形中，则该图形包含某图形 
			if (shape.contains_point(text[i],x,y) and i~=j) then
				_G.table.insert(record,{inner = j,outer = i})
			else
				_G.table.insert(record,"")
			end
		end
	end
	return record
end

--处理包含与被包含关系的记录
function record_handler(record_tbl,text)
	info_tbl = {}
	outer = {}
	inner = {}
	--分析每一条记录
	for i=1,#record_tbl do
		outer[i]={}  --记录该图形被哪些图形包含
		inner[i]={}  --记录该图形包含了哪些图形
		for j=1,#record_tbl do
			if record_tbl[j].inner == i then
				_G.table.insert(outer[i],record_tbl[j].outer)
			end
			if record_tbl[j].outer == i then
				_G.table.insert(inner[i],record_tbl[j].inner)
			end
		end
		--合成总的信息table：图形编号、外部图形数量，外部图形的编号，内部图形数量，内部图形的编号，图形对应的绘图代码
		_G.table.insert(info_tbl,{shape_i = i, o_count = #outer[i],outer = outer[i],in_count = #inner[i],inner=inner[i], shape = text[i]})
	end
	return delete_empty(info_tbl)
end

--依据分析结果重组ass图形
function shape_assembler(info_tbl)
	new_t = {}
	delete_empty(info_tbl,2) --删除空记录
	_G.table.sort(info_tbl,function (a,b) return a.o_count > b.o_count end) --按照外部图形数量排序，即从最内部的图形开始
	info_tbl["n"]= #info_tbl
	--图形i 后称 该图形
	for i=1,info_tbl.n do
		--第一种情况，如果该图形 没有外部图形且没有内部图形 或 外部图形为偶数个且没有内部图形 这样的图形属于独立图形，无需组合直接保存即可
		if ((info_tbl[i].o_count==0 or info_tbl[i].o_count%2==0) and info_tbl[i].in_count==0) then
			new_t[i] = info_tbl[i]
		--第二种情况，如果该图形 内部图形数量大于等于1，外部图形数量不为0，且外部图形数量为偶数 这样的图形属于非最外部镂空图形的外圈
		elseif (info_tbl[i].in_count>=1 and info_tbl[i].o_count~=0 and info_tbl[i].o_count%2==0) then
			--从该图形开始查找内圈
			for j=i,1,-1 do
				--如果 该图形 的编号在 某图形 的外部编号表中
				if is_include(info_tbl[i].shape_i,info_tbl[j].outer) then
					info_tbl[i].shape = info_tbl[i].shape.." "..info_tbl[j].shape  --连接该图形和某图形
				end
			end
		new_t[i] = info_tbl[i]
		--第三种情况，如果该图形 没有外部图形，但是有内部图形 这样的图形是最外圈
		elseif (info_tbl[i].o_count==0 and info_tbl[i].in_count~=0) then
			--从该图形开始查找内圈
			for j=i,1,-1 do
				--如果 该图形 的编号在 某图形 的外部编号表中，并且 某图形 只有1个外部
				if is_include(info_tbl[i].shape_i,info_tbl[j].outer) and #info_tbl[j].outer==1 then
					info_tbl[i].shape = info_tbl[i].shape.." "..info_tbl[j].shape  --连接该图形和某图形
				end
			end
			new_t[i] = info_tbl[i]
		else 
			new_t[i] =""
		end
	end
	new_t = delete_empty(new_t,1)
	--重新生成一个只含有绘图代码的table
	for i=1,#new_t do
		new_t[i] = new_t[i].shape
	end
	return new_t
end

五、结语

　　好久不写这么多东西了，全文没有使用复杂的数学概念，仅靠规律总结和简单逻辑分析判断，达到了拆分矢量图形连通区域的目的。
　　该方法还没有经过大量的实际验证，但可以确认的是效率较为可观，对于各种字体基本都兼容。如有错误或更好的解决方法望不吝赐教。