[0085] 然后进行填色。
[0086] 使用列表A保存本轮需要填补处理的多边形,列表B为本轮处理后产生的对应的外接凸包络,也即凸多边形,列表C为本轮处理后产生的需要填补处理的多边形。
[0087] 第一轮处理后,列表B的多边形成员使用目标色着色。
[0088] 第二轮处理后,列表B的多边形成员使用目标色的反色着色。
[0089] 第2n-1(n>=1)轮处理后,列表B的多边形成员使用目标色着色。
[0090] 第2n轮处理后,列表B的多边形成员使用目标色的反色着色。
[0091] 其中,列表B中的多边形都是凸多边形了。
[0092] 着色方法使用种子点扫描线算法。种子点为凸多边形的重心,其必然在多边形内部。扫描线结合活动边表,针对种子点的上下两部分进行扫描着色。
[0093] 下面再具体举个例子:
[0094] 如图8所示,其为原始多边形,由两个多边形Y1和Y2自交形成,则进行判断得到多边形Y1和Y2分别为两个子原始多边形,则需要对多边形Y1和Y2均要进行填补;
[0095] 如图9所示,对于多边形Y1来说,要形成外接凸包络,需要填补Y11和Y12,而对于多边形Y2来说,要形成外接凸包络,需要填补Y21和Y22,
[0096] 则第一轮进行填补的多变形为Y1、Y2,分别形成外接凸包络X1和X2,对X1和X2用目标色着色。而第二轮需要填补处理的多边形为Y11和Y12,以及Y21和Y22。
[0097] 如图10所示,其中,Y12、Y21和Y22已经是外接凸包络,所以只要用目标色的反色着色即可,而Y11则不同,其还是有凹角,所以Y11要填补成外接凸包络N1后再着色,而外接凸包络N1中需要填补的多边形为N11。
[0098] 则第二轮进行填补的多边形为Y12、Y21和Y22,以及N1,并用目标色的反色着色。
[0099] 如图11所示,第三轮对多边形为N11进行填补,形成外接凸包络M1,对外接凸包络M1使用目标色着色,且填补的多边形为M11,则M11为第四轮需要填补处理的多边形。
[0100] 而在第四轮中,由于M11已经是外接凸多边形,所以,整个多边形已经没有新的增加的多边形,所以只要对M11使用目标色的反色进行着色即可。
[0101] 这样通过四个轮次的着色,即可完成整个多边形的着色,着色方法使用种子点扫描线算法。种子点为凸多边形的重心,其必然在多边形内部。扫描线结合活动边表,针对种子点的上下两部分进行扫描着色。
[0102] 整个过程中,需要对本轮进行填补处理的多边形进行保存,对本轮的需要着色的外接凸包络进行保存,对本轮处理形成的新多边形,也即本轮形成的需要处理的多边形进行保存。
[0103] 与现有最好技术相比,本发明的优点在于:
[0104] 将复杂多边形转换为凸多边形,而凸多边形的着色方法相对简单,提高算法效率,也即,1.使用多边形填补方法,将任意多边形的填色转换为凸多边形的填色;2.使用XOR方法填色。
[0105] 实施例2
[0106] 系统图如图12所示,一种单连通的任意多边形区域填充系统,包括填补单元、填色单元,所述填补单元用于对原始多边形的凹角进行填补并形成外接凸包络,所述填色单元用于对所述外接凸包络进行填色。
[0107] 本系统适用于于实施例1的单连通的任意多边形区域填充方法,通过填补单元对有凹角的多边形填补形成凸多边形后再进行着色。
[0108] 进一步地,该系统还包括判断单元、计算单元、存储单元。其中,[0109] 判断单元用于判断各种条件;
[0110] 计算单元用于各种公式等的计算;
[0111] 存储单元用于存储各种数据。
[0112] 判断单元、计算单元和存储单元可设置为隶属于填补单元,更加高效地完成多边形凹角的填补,也更利于填色单元根据填补单元的结果进行更加快捷、方便的填色作业。
[0113] 本文中所描述的具体实施例仅仅是对本发明精神作举例说明。本发明所属技术领域的技术人员可以对所描述的具体实施例做各种各样的修改或补充或采用类似的方式替代,但并不会偏离本发明的精神或者超越所附权利要求书所定义的范围。