最近没事在研究PS中一些我比较感兴趣的功能的实现方法，上一次实现了套索的蚂蚁线功能，效果还行。这次就来看看套索本身是如何实现的。

总体来说要实现这个功能主要包括以下几个方面：1、套索也即复杂多边形的内外部识别；2、生成bitmap(类似于GDI中的region(区域))；3、根据bitmap转换成套索；4、bitmap布尔操作。

---原理、实现---

1、套索也即复杂多边形的内外部识别

如何识别一个复杂多边形的内部区域，有两种常用的方法：1、奇偶规则(odd-even rule) 2、非零环绕数规则(nonzero winding-number rule)。

PS中使用的是非零环绕数规则，这个网上资料很多，在这简单说一下规则：首先假定多边形的边是有方向的：比如规定顺时针是正方向，逆时针是负方向。这时判断一个点是否在多边形内，可以从这一点向多边形外发射一条直线，直线每经过一条边根据此边是正方向还是负方向分别+1和-1，最后统计如果非零则此点在多边形内，否则在外。为了方便计算一般引一条与X轴平行的线进行计算，这个方法主要的麻烦就在射线与边线以及边线与边线之间的交点计算，因为求交点是判断线段方向的前提，从图形学上来说计算线段的相交性及交点都是比较麻烦的事。

有没有办法可以简化这些计算呢？上面的计算之所以麻烦是因为是从一般图形学角度来看的——线段是无限连续的，只能通过线段整体判断方向；如果只从计算机图形学的角度看——线段被光栅化、不再是连续的、最小单位是像素、线段可以用连续的像素点表示——这个线段可以被离散化的特性就是简化计算的关键——判断方向不再需要计算线段交点，只通过相邻点的坐标值比较即可判断。

具体方法就是以像素为单位，沿着绘制多边形边的顺序，对每个经过的坐标点维护一个值，顺时针移动时(比较Y值即可，比上一个点Y值大的表示顺时针)+1，逆时针移动-1，与X轴平行的点设为0，然后通过扫描这个结构(在此是一个二维表)，就可以确定多边形的内外部区域，生成bitmap。

2、生成bitmap(类似于GDI中的region(区域))

类似边界标志算法，用平行于X轴的扫描线自左向右扫描上面生成的二维表结构，累加扫描经过的像素对应的值，不为0的即为内部点，填充到bitmap(位图)。

3、根据bitmap转换成套索

自上向下、从左到右两个方向扫描bitmap，记录轮廓线。

4、bitmap布尔操作

与、或、非、异或、减

具体看dome和代码

效果图： 图1 原始线段

           图2 边线赋值、区分内外

           图3 新边缘

                        图1                                                                         图2                                                                        图3

---存在问题---

前面说了线段可以被离散化的特性是简化计算的关键，但代价是引入了交点计算误差，从理论上说两相反方向的线段相交必有一个交点(见图4)，根据非零环绕规则这个点的环绕数为0(1+-1=0)，是一个外部的不应该显示的点。在用像素模拟线段交点时，根据的是像素是否重叠来判断交点的，但在有的情况下两条线段会出现相交而没有像素重叠的情况(见图5)，这样简化方法无法判定交点，对此只能当作相邻的方向相反的像素来处理，本应环绕数为0而断开的位置，会有1个或几个(根据斜率)像素继续存在，会造成本不该联通的位置联通，同时用户使用此功能时也可能产生混乱。

                   图4                                                               图5

---解决办法---

解决办法很简单就是不理它、无视它、塞到桌子下面当作这个世界依然完美，因为photoshop就是这么干的(有没有"说的如此有道理我竟然无言以对"的感觉)？嗯~试着猜一下PS允许这样干的理由：1、误差影响范围有限，只在交点出现并且只影响周围有限几个像素；2、这个功能本身不需要那么精确。

---一点感想---

想了很多办法也做不到与ps的bitmap轮廓线完全相同，不过各有优劣，ps大法虽好，这个细节做的也并非完美^^，不一样就不一样吧。

相关算法找准关键字——“非零环绕数规则“、“多边形填充中的边界标志算法”——网上搜一搜都有。

如何实现photoshop的套索功能