【Aegisub】判断点是否包含在任意(含曲线命令的)绘图内
（提醒：对于知道A3shape的人，可能知道A3有提供判断点包含的函数，但是那个函数实际上是有一点错误的，也就是并不能正确的判断点包含，文章后面会讲它为何错。当然知不知道A3shape都不影响你看这篇文章，因为这篇文章就是讲怎么判断点包含的）
之前的视频讲了assdraw的填充方式 ( 和svg的non-zero规则一样 )，也讲了如何判断点是否包含于任意直线绘图内，那么，如果绘图里有贝塞尔曲线呢，又怎样快速地进行点包含的判断呢？
相信如果你理解了填充规则，就知道，在有曲线时一样可以用可爱的扫描线来判断绘图的填充情况，那么重点就是扫描线与绘图交点的计算了。当绘图有曲线命令的时候，就需要计算扫描线和曲线的交点，所以实际上就是要解三次方程。解三次方程有很多种方法，比如用二分法或牛顿迭代，当然如果用二分法的话，迭代次数会比用牛顿法的要多。那么你猜咱们这里用什么方法呢，二分法牛顿法弦截法？很好，那么现在用公式法解三次方程
然后下一个问题，或者说下一个注意事项，我们求得了曲线和绘图的交点以后，是每一个求得的交点都要参与计数吗？大家回想一下以前讲的判断点是否包含于全直线绘图中，当我们实际计数的时候，比如线段AB和水平线有交点C，只有当交点C的纵坐标不等于线段AB的bottom（也就是A、B两点的纵坐标最大值）的时候，才会计数，而如果交点的纵坐标y等于该线段的"最大y"的话，实际上是不需要更改cnt的。所以同理，在对水平线和曲线的交点计数的时候，需要满足这个原则，就叫端点计数原则吧，或者叫不添脚原则？(不是叫不舔脚原则)，等一下，要不然叫Lua真是一门恶心语言原则？想不到好的叫法了，就叫端点计数原则吧...
接下来，主要用例子来解析说明端点计数原则的用法。端点计数原则当然指的就是，如果水平线和某段路径的交点的y坐标小于该段路径的最大y坐标，则计数、cnt更新，否则，不计数、cnt不变化。先从全直线的情况说吧...比如图1.01
假设我们要判断点A是否包含在图1.01所指定的绘图中，那么就过A点作水平线，和绘图取交点，如图1.02
现在直接看图的话水平线和绘图有3个交点，但是实际计数的点只有N、M，因为A这个交点的纵坐标是线段AB的bottom（也就是AB的y最大），所以AB段和水平线的交点是不会参与计数的。同样，线段AC和水平线的交点A的纵坐标是线段AC的bottom（即AC段的最大y），所以AC段和水平线的交点也是不参与计数的。那么，此时的计数情况就是，在N处，该段路径向上，所以cnt增加1就等于1，所以N点到下一个交点M这一部分是填充的，然后在M处，该段路径向下，所以cnt=cnt-1就等于0，所以M右边的部分都不填充。
再比如图1.03，m 0 0 l 0 19 l 0 29 l 42 29 l 42 0 m 9 5 l 32 5 l 32 26 l 9 26
现在假设要判断点A是否在绘图内，那么过A点作水平线，得到图1.04
为了突出端点计数原则，现在我们首先不用端点计数原则来判断点包含，然后再用端点计数原则来判断点包含。
假设不用端点计数原则，水平线与BP1段相交得到P1，由于BP1向下，那么cnt=cnt-1=-1,然后水平线与P1C也相交于点P1，又计数，cnt = cnt - 1 = -2，然后到下一个交点P2，此时该段路径向上，cnt=cnt+1=-1，我们发现，此时的cnt不等于0，那么按照cnt的情况，P2到P3之间的部分应该填充，所以点A应该是包含在绘图内的，可是显然，这是不对的，A点并不包含在绘图内！
而我们这一次再来用端点计数原则看看，水平线与BP1段相交得到P1，而此时点P1的纵坐标等于BP1段的底bottom（即BP1段的最大y），所以这个P1不参与此次计数，cnt=0依旧，然后水平线与P1C也相交于点P1，此时点P1的纵坐标不等于P1C段的底bottom（即P1C段的最大y），所以这个P1就要计数，cnt = cnt - 1 = -1，然后到下一个交点P2，此时该段路径向上，cnt=cnt+1=0，所以，现在cnt就等于0，按照此情况，P2到P3之间的部分就是不填充的，所以点A就不包含在绘图内，这便是正确的结果。
那么现在来看看有绘图中含有曲线命令的例子，如图1.05，m 2 9 b 5 -26 18 -20 23 0 b 28 12 44 17 48 -19 l 50 20 l 2 20
假设我们要判断点A是否在图1.05指定的绘图内部，那么过点A作水平线和绘图取交点，得到图1.06
那么现在又和刚才一样的，为了突出端点计数原则，现在我们首先不用端点计数原则来判断点包含，然后再用端点计数原则来判断点包含。
假设不用端点计数原则，水平线与第一条贝塞尔有第一个交点P1，根据点P1处的时间参数 t 和此时的一阶导数，得到此时P1处的方向信息，当然“向上”了，所以cnt = cnt+1 = 1，然后水平线与第一条贝塞尔还有第二个交点P2，同样求出P2点的切线方向，方向向下，所以cnt=cnt-1=0，再然后水平线和第二条贝塞尔有第一个交点P2，求出该点方向，方向向下，所以cnt=cnt-1=-1，然后水平线和第二条贝塞尔还有第二个交点P3，求出该点方向，方向向上，所以cnt=cnt+1=0，所以，根据现在cnt的情况，我们发现，在P2到P3之间，cnt=-1，所以P2到P3这一部分应该填充，然后，P3到P4，cnt等于0，所以P3到P4这一部分应该不填充, 很显然，这是错误的，因为A明明是不在绘图内部的！
而我们又一次来用端点计数原则看看，水平线与第一条贝塞尔有第一个交点P1，而P1并不是该条贝塞尔曲线的端点，所以放心地计数，cnt=cnt+1=1，然后水平线与第一条贝塞尔还有第二个交点P2，此时P2是该条贝塞尔曲线的端点，所以需要判断一下了，不过这时当然不是用这一整条贝塞尔的最大y和P2的y比较，而是这样，现在P2是该贝塞尔的终点，所以咱们用上一个点(即该贝塞尔的第二个控制点)和终点的y比较，判断终点的y坐标是否更大，更大就说明P2也是y更大的，即P2的纵坐标y等于“该段”路径的bottom，那么是bottom就像刚刚说的,不参与计数，cnt不变依旧等于1，再然后水平线和第二条贝塞尔有第一个交点P2，判断出P2是该条贝塞尔的端点，所以需要判断是否P2的y是bottom，现在P2是该条贝塞尔的起点，所以要用到下一个点（也就是该条贝塞尔的第一个控制点）和起点比较，显然，现在起点P2的y比第一个控制点C的y要小，所以P2的纵坐标y不是bottom，所以，现在就需要计数，那么cnt = cnt - 1 = 0，然后水平线和第二条贝塞尔还有第二个交点P3，P3并不是该条贝塞尔曲线的端点，所以肯定不是bottom，直接计数，cnt=cnt+1=1，所以根据此时的情况，我们就知道，在P2到P3之间cnt等于0，所以P2到P3这一部分不填充，而P3到P4的cnt等于1，所有P3到P4这一部分是要填充的，所以当然也可知A点是不在绘图内部的。
继续举例，解释在绘图有贝塞尔曲线命令时，端点计数原则该怎么使用，如图1.07和图1.08，m 0 0 b -3 -13 9 -18 19 -18 b 22 -9 32 -5 34 3
假设现在想判断A这个点，是否在绘图内部
过A点作水平线，得到图1.09
现在直接用端点计数原则来判断点包含，水平线与第一条贝塞尔有交点P，发现P是该条贝塞尔的端点，且P是该条曲线的终点，那么就像刚刚说的，应该配合上一个点来判断P是否是bottom，可是问题来了，现在点C和点P的y是一样的，那如果你把P当成bottom的话，就不会改变计数，而在下一条曲线的时候，P是端点但是不是bottom，所以会计数，那么，那样的话，cnt最后会等于-1，不等于0，那么A就会被判断为在绘图内部，而这是不对的，所以，现在当C和终点P的纵坐标y一样的时候，需要再往前看，也就是C的前一个点B，看B的y是否大于P的y，发现，P的纵坐标比B的纵坐标小，所以P不是bottom而是top，所以此时实际上是需要计数的，而方向就是向上（因为P是终点且P不是bottom），所以cnt=cnt+1=1，然后再来，水平线和第二条贝塞尔曲线有交点P，判断出P是该条贝塞尔曲线的起点，则找出下一点D，判断P和D的纵坐标谁大，发现，P的y更小，所以P不是bottom，所以需要计数，此时方向一定向下（因为P是曲线起点且P不是bottom），所以cnt=cnt-1=0，所以，在该条水平线上，当横坐标x大于P的时候，均不填充，那么由于A的横坐标x大于P的，所以A处不填充，即A不在绘图内部！
所以总结一下，当水平线和贝塞尔曲线有交点P时，如果P不是该条贝塞尔曲线的端点，那么必然计数，而如果P是端点，那么：①若P是曲线起点（即时间参数t=0），则逐一查看后面的点（即曲线的第一个控制点到曲线终点）直到检测出P是否是bottom为止，若P为bottom则交点P并不参与计数，若P不是bottom则cnt必然减1，即cnt=cnt-1。②若P是曲线终点（即时间参数t=1），则逐一查看前面的点（即曲线的第二个控制点到曲线起点），直到检测出P是否是bottom为止，若P为bottom则交点P并不参与计数，若P不是bottom则cnt必然加1，即cnt = cnt + 1。
所以端点计数原则就是和端点有关系的，不管是直线还是曲线，只要你交点不是端点，则必然计数，如果交点是端点且该点不是bottom，同样也是必然计数，如果交点是端点且该点是bottom，那么该交点才不会参与计数、才不会改变cnt。
具体地说完端点计数原则以后，就回头聊一聊水平线和绘图求交点吧。水平线和直线求交点当然没啥问题，那么主要就是水平线和贝塞尔曲线求交点了。
水平线和贝塞尔曲线求交点有点需要注意的，就是“精度”问题。比如判别式Δ>0时，三次方程除了有一个实根外，还有一对共轭复根，但是有的时候求出来的共轭复根的虚部非常非常小，比如3.994250345898757e-7i就很小很小，然后结合原方程就有肉眼可见的问题，本来应该得到两个实根，却得到了一个实根两个复根，所以比方说你可以计算当求得的复根的虚部很小的时候，将其取舍掉，但是这样计算量会增大，因为要多算不需要计算的复根，所以这里需要的是对判别式做判断，如果判别式特别接近于0，那么就认为判别式等于0，这样就能直接按Δ=0来计算方程的根，就不用求不必要的复根了。
实际上，Lua计算浮点数的时候有精度问题，所以计算的判别式Δ特别接近0的时候，不易知道它具体数值是多少。甚至不同版本的Lua计算结果会不一样，比如
而如果用同样的代码，直接在aeg里面试试，会得到这样的结果
得到的这两个结果差距是很大的，虽然它们都接近0。
所以为了确保曲线和水平线的交点是曲线的端点时，能求出理想的解，可以让Δ接近0时就当作0、然后为了确保不会有多余解和遗漏的解，在Δ>0时需要判断0和1是否是方程的解(因为Δ>0也可能很接近0)、在Δ<0时需要判断3个根里有没有重复的，如果有就去除掉重复的(因为Δ<0也可能很接近0，有可能本身应该是当作Δ=0算但实际却当作了Δ<0算，那么3个实根中就会有两个是几乎一样的数值)
还有就是如果用太多的除法运算，也会导致计算结果不稳定，所以可以尽量减少代码里的除法运算。
然后除开解方程以外，剩下其他判断点包含的代码在视频里讲
那么说起求交点，其实光是求交点的话你也可以用其他方法。比如求两条贝塞尔曲线的交点，假设这两条曲线是A1和B1，那么你可以求出A1的边界框bbox1和B1的边界框bbox2然后如果两条曲线的边界框没有重合部分，那么说明曲线A1和曲线B1没有交点，而如果两个边界框有重合部分，那么就拆分两条曲线，将A1拆为A2和A3、B1拆为B2和B3，然后再求拆出来的这4条曲线的边界框，然后看哪两个边界框是有重合的，然后一直这么重复算下去，直到计算到最后求出的边界框是足够小的就可以了。所以此时你就可以设定一个精度了。那么同样的，曲线和直线求交点也可以类似的计算。
之前的视频里说过，我看了一下qt库的c++源码(就是很多年前就有的一个由外国人写的库)，其判断点包含的时候就有一点错误。qt库中使用的方法就是拆分贝塞尔曲线，并且还限制了拆分的次数，当然本来也不可能无限的拆分下去。那我大概写了一个Lua版本的扫描线与贝塞尔曲线的交点计数函数：
local function bezier_isect_cnt(x1,y1,x2,y2,x3,y3,x4,y4,y,n)
local top,bottom=math.min(y1,y2,y3,y4),math.max(y1,y2,y3,y4)
local left,right=math.min(x1,x2,x3,x4),math.max(x1,x2,x3,x4)
local n=n and n+1 or 0
if y>=top and y<bottom then
local w,h=right-left,bottom-top
if n>=32 or (w<0.001 and h<0.001) then
if x1<=pt_x then
cnt=cnt+Xshape.sgn(y4-y1)
end
else
local f_x2,f_y2,f_x3,f_y3,tx,ty,s_x2,s_y2,s_x3,s_y3=Xshape.split_bezier_into_two(x1,y1,x2,y2,x3,y3,x4,y4)
bezier_isect_cnt(x1,y1,f_x2,f_y2,f_x3,f_y3,tx,ty,y,n)
bezier_isect_cnt(tx,ty,s_x2,s_y2,s_x3,s_y3,x4,y4,y,n)
end
end
end
显然参数的n就是为了限制递归的次数的
那么为什么说qt库的判断点包含有错误呢？咱们先来看看错误在哪。比如下图1.10
图1.10的绘图代码是m 36 5 l 36 34 b 37 38 33 39 25 37 b 24 36 24 36 24 34 b 25 33 25 33 27 34 b 31 35 33 35 33 34 l 33 6 b 33 5 33 4 34 4 b 36 4 36 5 36 5 l 36 5 m 25 8 b 25 7 25 6 26 6 b 27 6 28 7 28 8 l 28 28 b 28 29 27 30 26 30 b 25 30 25 29 25 28 l 25 8 m 15 20 l 21 20 b 22 20 23 20 23 21 b 23 23 22 23 21 23 l 15 23 l 15 34 b 15 38 13 39 8 37 b 7 37 6 36 6 35 b 7 34 7 34 9 34 b 11 35 12 35 11 33 l 11 23 l 4 23 b 2 23 2 23 2 21 b 2 20 2 20 4 20 l 11 20 l 11 16 b 11 15 12 14 13 14 b 14 14 15 15 15 16 l 15 20 m 6 5 b 9 6 11 7 14 9 b 15 7 17 6 18 5 b 19 4 19 4 20 4 b 21 5 21 6 20 7 b 19 8 18 9 17 11 b 18 11 19 12 21 14 b 21 14 22 14 22 14 b 23 15 23 16 23 17 b 22 18 21 18 20 17 b 18 16 16 15 14 13 b 11 15 8 16 5 17 b 3 17 2 17 2 16 b 2 15 2 14 3 14 b 6 13 8 12 11 11 b 10 11 8 10 5 8 b 4 8 4 7 4 6 b 4 5 5 5 6 5 l 6 5 m 10 26 b 8 30 7 33 5 34 b 4 35 3 35 2 35 b 2 34 2 33 3 32 b 4 31 5 28 6 25 b 7 24 7 23 9 24 b 9 24 10 25 10 26 l 10 26 m 19 24 b 21 27 22 29 23 31 b 24 33 23 34 23 34 b 22 35 21 34 20 33 b 18 30 17 28 16 26 b 15 25 15 24 16 24 b 17 23 18 23 19 24 l 19 24
那么从图上可以清楚地看到，点(19,38)一定是不在图形内的、而且是“一点关系”都不挨着的。但是如果用利用qt库的A3shape来判断点包含的话，就会得到点是包含的这个结论，如图1.11和图1.12
而实际上，不仅仅是(19,38)会被判断为在图形内，甚至有“一排”点都会被判断为在图形内部，如图1.13
那你肯定会想到底是为啥。其实很简单，因为图形中有贝塞尔曲线刚好和扫描线是相切的！！啊，怎么会这样啊，哦不，你瞧瞧，哇，你身上有只飞碟耶！那就来碗飞碟泡饭吧！不好意思，刚才键盘上太多灰了。对，飞碟指的就是UFO。好吧，那么水平线和曲线相切只有一个交点的话，那就是此时这个曲线的方向是沿着水平方向的，所以我们的计数变量cnt应该加0、也就是cnt应该不变，而qt库中，却没有这么贴心的考虑，因为拆分贝塞尔曲线不可能一直拆分下去, 那么当曲线和水平线相切的时候，怎么也不可能把曲线拆分到一个点，那根据其代码，计数不是1就会是-1，那就完全忽略了0的情况。
所以不知道为什么qt库没有考虑到曲线有可能和水平线相切的情况，导致交点计数错误。那么这样带来的结果是什么呢，比如说，如果咱们用qt库的判断点包含函数来将图形转像素，就会得到图1.14、图1.15这样的结果
可以看到，由于点包含判断错误了，所以求出的像素点就不对了。
在看了利用qt库的A3shape的bug以后，咱们知道现在既然能判断一个点是否包含在一个带有曲线路径的绘图内，那就可以利用这个方式，来快速的将图形转像素了，单独写一个转像素的函数（当然不是用判断点包含的函数来写，而是用判断点包含的思路来写），这样写出的函数就比Yutils的转像素更快（曲线越多，快的就越多）。那么直接将曲线绘图转像素的函数就在后面的视频中讲。
另外，文章中一些名字完全是我瞎取的，因为带有曲线的交点计数算法是我自己瞎想的，所以为了方便称呼就取名为端点计数原则了，然后比如此时bottom这名字也是我瞎取的，但是我觉得这名字还是比较贴切的，应该比较好理解。
本文写于2021年1月22日（测试一下我多久会发布这篇专栏，绝大部分专栏都会等上半年多才发布）
