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

c/c++

浏览数:183

2019-6-20

AD:资源代下载服务

需求

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

光栅化

.  要在屏幕显示填充的图形,必然要将图形光栅化到屏幕上,而目前所有的底层图形API仅支持对三角形的填充,因此要实现任意形状填充需要将这个形状切割成多个三角形,再通过图形API进行绘制.

.  上图是一个简单又不简单的选区,通过6个点组合出一个简单的几何形状,但不简单的是,这个几何有一处交叉,因此构成了两个闭合空间.如果把两个闭合空间分离出来,再逐个切割三角形,则会简单很多.

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

结果

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

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

算法: 在多边形的凹点处,延伸出一条线段,连接到最近的边,这条线段作为交界,划分出两个多边形,再分别将这两个多边形重复此步骤,直到没有凹点,则这个多边形是凸多边形.

结果

.  从上图可以看到,凹多边形多出了几条边,这几条边将凹多边形切分成了多个凸多边形,剩下的事就好办了,只要按凸多边形切分三角形就行了.

本文到这就结束了,以下是更复杂的形状填充演示.

作者:落单的毛毛虫