算法 & 数据结构——任意多边形填充

需求

.　　在计算机中，选区是一个很常见的功能，例如windows按住鼠标左键拖动划出矩形选区，Photshop经过钢笔工具任意形状选区．选区自己不过是经过线段闭合的一个几何形状，可是如何填充这个选区，则是一件相对棘手的问题．算法

光栅化

.　　要在屏幕显示填充的图形，必然要将图形光栅化到屏幕上，而目前全部的底层图形API仅支持对三角形的填充，所以要实现任意形状填充须要将这个形状切割成多个三角形，再经过图形API进行绘制．windows

.　　上图是一个简单又不简单的选区，经过６个点组合出一个简单的几何形状，但不简单的是，这个几何有一处交叉，所以构成了两个闭合空间．若是把两个闭合空间分离出来，再逐个切割三角形，则会简单不少．工具

算法： 从多边形的第三个顶点开始，每一个顶点与下一个顶点造成一条线段，再依次与以前的顶点线段求交点，一旦出现交点，则必然产生一个闭合路径，以交点为界，剥离这个闭合路径便可，循环此步骤，直到没有交点为止．.net

结果3d

.　　上图的几何将闭合空间剥离以后，获得两个凸多边形，而凸多边形很容易切分出多个三角形，上图颜色区分了每一个三角形，其实现思路是从凸多边形的中心到凸多边形的每一个顶点造成三角形，也能够从凸多边形的某一个点依次到每一个顶点造成三角形．这个方法只适合凸多边形，当选区是凹多边形的时候，它就会出问题．blog

.　　上图是一个简单的凹多边形，对于凹多边形，不能直接切分三角形，要先切分凸多边形，再切分三角形．bfc

算法： 在多边形的凹点处，延伸出一条线段，链接到最近的边，这条线段做为交界，划分出两个多边形，再分别将这两个多边形重复此步骤，直到没有凹点，则这个多边形是凸多边形．循环

结果方法

.　　从上图能够看到，凹多边形多出了几条边，这几条边将凹多边形切分红了多个凸多边形，剩下的事就好办了，只要按凸多边形切分三角形就好了．im

本文到这就结束了，如下是更复杂的形状填充演示．