本文主要是介绍线段树算法 ---- 扫描线之面积并,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、扫描线算法
基本思想
按扫描线顺序,计算扫描线与多边形的相交区间,再用要求的颜色显示这些区间的象素,即完成填充工作。
对于一条扫描线填充过程可以分为四个步骤:
(1) 求交:计算扫描线与多边形各边的交点
(2) 排序:把所有交点按 x 坐标递增顺序来排序
(3) 配对:确定扫描线与多边形的相交区间,第一个与第二个,第三个与第四个等等,每对交点代表扫描线与多边形的一个相交区间
(4) 填充:显示相交区间的象素
存在问题1:当扫描线与多边形顶点相交时,交点的取舍问题
解决方法:当扫描线与多边形的顶点相交时,若共享顶点的两条边分别落在扫描线的两边,交点只算一个;若共享顶点的两条边在扫描线的同一边,这时交点作为零个或两个,取决于该点是多边形的局部最高点或局部最低点。
具体实现
这篇关于线段树算法 ---- 扫描线之面积并的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!