算法 & 数据结构——多边形填充
在很多图形相关的编辑器里都会有选区功能，有的只能按某种固定形状选择，比如：矩形，圆形……，有的可以按任意形状选择，有的甚至可以分析图片自动选区（例如：Photoshop魔法棒工具），今天来说说任意形状选区怎么实现。
通过鼠标描点，再用线段连接，组合成一个几何选区，这看似没有难度，它实际上……的确没有难度。如果要填充选区内部，这就有一丢丢难度（至少很久前我被这个问题困住很久）。
计算机图形接口
在计算机里，图片普遍都是矩形的，当渲染一张图片到屏幕时，这张图片会被拆成两个三角形，这两个三角形将图片斜角对折切开，然后提交到渲染管道，而这个渲染管道则由显卡接管。
至于为什么会被拆成三角形，因为计算机3D渲染技术已经非常成熟，而3D渲染完全可以渲染2D图像，因此显卡只需要按3D渲染的架构设计就可以了，但是，3D图形比2D图形复杂的多，因为2D形状统统都可以在一个矩形的图片上画出来，而3D要显示一个形状需要模型，而怎么构建这个模型就成了问题。例如：立方体模型，六个面，那可以用六个正方形来构建。但是球形或更复杂的模型，纯用正方形去拼凑完全不可能，因此这可能需要各种各样的形状，从而导致非常凌乱。如果有一种图元可以拼凑出任意形状的模型，那一切都完美，三角形正是这样的图元，它虽然不能完美拼凑任意形状的模型，却可以在硬件允许的情况下无限近似任意形状的模型。当前流行的显卡通常只支持三角形硬件加速，听说俄罗斯还有人搞圆形硬件加速的？
上面大概已经说明三角形和渲染管道的关系了，下面进入正题。
闭合路径
要填充一个不规则的选区，要把它拆分成多个三角形，而怎么拆分成三角形就是问题所在。
任意形状选区
在拆分三角形之前，需要计算出选区内包含的所有闭合路径，因为一个选区可能会有多个闭合路径，就像上图显示，选区包含了两个闭合路径，要填充这两个闭合路径．
选区的数据结构是一组顶点列表[p0, p1, p2...pN]
从 p2 开始遍历：
pi -> p(i+1) 正好构成一条线段，将这条线段与前面的线段做相交检测，一旦相交，则说明此时遇到了一个闭合路径．
记录交点CrossP，
记录交点线段的起点CrossA，
记录交点线段的终点CrossB．
[CrossP, CrossB, ..., pi] 顶点列表则是该闭合路径．
随后将这个闭合路径的顶点列表从原始顶点列表中剔除，并将CrossP插入到CrossB的位置．
直到把原始顶点列表遍历完毕，则所有的闭合路径都被计算出来了．
三角形切割
已经得到了所有的闭合路径，接下来就可以切割三角形了．这非常容易，因为每一个闭合路径都是一个多边形，只需要求得这个多边形的中点，再从中点依次连接到各个顶点就可以了．
切割三角形
从图中可以清楚的看到闭合路径的中心，以及从中心连接到各个顶点的线段，因为图中的闭合路径只有四个顶点，因此只需要切割四个三角形就足够了．
计算多边形中心的公式：
(p[i] + p[i+1] + p[N]) / N
如果一切都是这么容易，那活着就舒坦了，几何学告诉我们，上述算法并不是总是凑效．
凹多边形切割
凹多边形闭合路径
从图中可以看出，闭合路径只有一个，但这个路径是凹多边形，按上述的方法求得中心很可能在多边形外面，连接出来的三角形并不正确．需要先把凹多边形切割成凸多边形，这非常容易．
只需要在多边形的凹点处，延伸出一条线段，连接到最近的边，这条线段作为交界，划分出两个多边形，再分别将这两个多边形重复此步骤，直到没有凹点，则这个多边形是凸多边形．
首先需要知道如何判断一个多边形是凹的还是凸的．
以左上角为原点的２D坐标系来说．
当一个顺时针排列的多边形，某一条边往左拐，这个多边形是凹多边形．
当一个逆时针排列的多边形，某一条边往右拐，这个多边形是凹多边形．
计算边的拐向很容易，只要判断两条边的向量积符号是正是负就行了．
// 向量拐向公式
// 具体拐向跟坐标系有关，在本例中，顺时针排列，向量积小于零是左拐．
Cross(p0p1, p1p2) < 0? "左拐?右拐?": "左拐?右拐?"
因为顶点顺序是随机的，因此可能是顺时针排列也可能是逆时针排列，所以要先计算出这个多边形的排列顺序，计算思路非常容易：
只需要遍历多边形顶点，对所有边计算拐向，如果左拐向多余右拐向，则是逆时针排列，否则是顺时针排列．
float Cutting::Polygon::CheckOrder(const math::Points & points)
{
auto order0 = 0; // 顺时针
auto order1 = 0; // 逆时针
for (auto i = 0; i != points.size(); ++i)
{
auto & a = points.at(INDEX(i , points.size()));
auto & b = points.at(INDEX(i + 1, points.size()));
auto & c = points.at(INDEX(i + 2, points.size()));
if (CheckOrder(a, b, c) < 0)
{
++order1;
}
else
{
++order0;
}
}
return order0 > order1 ? 1.0f : -1.0f;
}
整个算法到这就结束了，下图是凹多边形切割后的形状，很容易发现，多了几根线段，这些线段正是切分成凸多边形的线段，而闭合路径也由１个变成了３个，再用上述的方法计算三角形就容易多了．
切割凹多边形
填充选区
效果展示
png
png
