今天给大家分享一下计算机图形学中，扫描线填充算法。
题目主要有下面一些限制：
- 有一个画板，这个画板有一定的宽高限制
- 画板有一些封闭图形
- 然后在画板随机取一点，将这点所在封闭图形或者是在所有封闭图形外画板内的区域进行填充。
这里画板的颜色就取白色，画笔的颜色就取黑色。
程序思路
在此题中，主要的难点在于图形填充。我使用了图形学中的扫描线填充算法来进行实现。主要的思路就是：
随机的点的点作为一个种子点加入一个种子点栈中。
从栈中取出一个种子点，分别向两边进行填充，直到遇到了封闭图形的边界点或者是画板的边界就停止。
经过第一步会得到两个变量。leftX表示上面最左边被填充的点的x坐标，rightX表示上面最右边被填充的点的x坐标。
然后，对这次的扫描行的上一行在[leftX, rightX]区间中进行扫描。遇到非画板颜色(封闭图形的边界点)就将边界点左边的点作为新的种子点添进一个栈数据结构中。如果rightX所在的点为画板颜色仍然作为种子点添加进去。
对扫描行下一行依然用类似的算法进行新的种子点的添加。
然后循环从栈中取出种子点并回到第二步。直到种子点栈为空为止。
下面是一张种子生成的位置及时间：
image
代码分析
image
Component包
Canvas类
表示画板的类。保存有一个画板宽画板高的二维int数据表示各个点的颜色*
Graph类
所有图形的接口类。SimpleGraph类为一个简单的实现类
Paint类
表示画笔的类。保存一个画笔的颜色。
Point类
表示点的类。保存点的x、y坐标。
utils包
Colors类
颜色工具类。int值有32位，刚好可以8位一组分别存储RGBA。这个类就是用于将RGBA分别的值合成一个int颜色值，或者通过一个颜色值获取对应的RGBA值。
DrawGraphStrategy类
这个类是用于通过Canvas、Paint以及Graph在Canvas上画图的类。SimpleGraphStrategy为简单的遍历Graph集合画图的类。通过一个Strategy，如果有必要可以通过Strategy对Graph进行一下过滤。
主类
FillProgram
这个类是重要的类，是用来组装所有的类的。
- 首先通过其中的init方法可以将Canvas重置，然后通过DrawGraphStrategy类在画板上进行封闭图形的绘制
- 然后通过调用fillFromASeedPoint方法可以给定一个初始的种子点对点所在的封闭图形，或者所有封闭图形外进行填充。
Main类
这个类主要用于启用一个简单的事例程序的。
详细代码
代码中注释很详细，而且上面对每个类都做了相应的分析。这里就只把代码贴出来了！
component包
Canvas
package component;
import utils.Colors;
/**
* 画板类
* <p>
* created by anriku on 2019-03-29
*/
public class Canvas {
// 用一个二维数组存储画板对应位置的颜色。int有32位，由低到高依次存储RGBA。
private int[][] mColors;
// 画板的背景色
private int mCanvasBgColor;
public Canvas() {
this(1000, 1000);
}
public Canvas(int width, int height) {
this(width, height, Colors.getColor(255, 255, 255, 255));
}
public Canvas(int width, int height, int color) {
mColors = new int[height][width];
mCanvasBgColor = color;
resetCanvasColor(color);
}
/**
* 重置画板的所有点的颜色
*
* @param color 重置颜色
*/
public void resetCanvasColor(int color) {
int width = getWidth();
int height = getHeight();
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
mColors[y][x] = color;
}
}
}
/**
* @return 画板宽度
*/
public int getWidth() {
return mColors[0].length;
}
/**
* @return 画板高度
*/
public int getHeight() {
return mColors.length;
}
/**
* 设置对应点的颜色
*
* @param x 点的x坐标
* @param y 点的y坐标
* @param color 颜色
*/
public void setColorByPosition(int x, int y, int color) {
mColors[y][x] = color;
}
/**
* 获取对应点的颜色
*
* @param x 点的x坐标
* @param y 点的y坐标
* @return 返回对应点的颜色
*/
public int getColorByPosition(int x, int y) {
return mColors[y][x];
}
/**
* 获取画板的背景颜色
*
* @return 颜色
*/
public int getCanvasBgColor() {
return mCanvasBgColor;
}
/**
* 显示画板的内容。
* W：表示背景色
* B：表示画笔色
*/
public void displayCanvas() {
for (int y = 0; y < getHeight(); y++) {
for (int x = 0; x < getWidth(); x++) {
if (getColorByPosition(x, y) == getCanvasBgColor()) {
System.out.print("W");
} else {
System.out.print("B");
}
}
System.out.println();
}
}
}
Graph
package component;
/**
* created by anriku on 2019-03-29
*/
public interface Graph {
/**
* 所有图形提供一个公共的遍历所有图形的点的方法。实现交给各个图形自己。
* <p>
* 如果是多边形或者有规则的弧形可以自己使用对应的方程来遍历点。
* 如果是不规则图形可以把所有点存储在一个数组中进行遍历。
*
* @param onTraverse 回掉方法
*/
void traverseAllPoint(OnTraverse onTraverse);
/**
* 回掉接口
*/
interface OnTraverse {
void onTraverse(int x, int y);
}
}
Paint
package component;
import utils.Colors;
/**
* 画笔
* created by anriku on 2019-03-29
*/
public class Paint {
// 画笔的颜色
private int mPaintColor;
public Paint() {
this(Colors.getColor(0, 0, 0, 255));
}
public Paint(int mPaintColor) {
this.mPaintColor = mPaintColor;
}
public int getPaintColor() {
return mPaintColor;
}
}
Point
package component;
/**
* 代表一个点
* <p>
* created by anriku on 2019-03-29
*/
public class Point {
public int x;
public int y;
public Point() {
this(0, 0);
}
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
SimpleGraph
package component;
/**
* created by wenyipeng on 2019-03-29
*/
public class SimpleGraph implements Graph {
@Override
public void traverseAllPoint(OnTraverse onTraverse) {
// 简单的画两个靠角落的矩形测试。
for (int y = 0; y < 5; y++) {
onTraverse.onTraverse(5, y);
}
for (int x = 6; x < 10; x++) {
onTraverse.onTraverse(x, 4);
}
for (int y = 7; y < 10; y++) {
onTraverse.onTraverse(3, y);
}
for (int x = 0; x < 3; x++) {
onTraverse.onTraverse(x, 7);
}
}
}
utils包
Colors
package utils;
/**
* 颜色工具类
* <p>
* created by anriku on 2019-03-29
*/
public class Colors {
private static int mask = 255;
/**
* red、green、blue、transport组成对应的颜色int。
*
* @param red 红色值
* @param green 绿色值
* @param blue 蓝色值
* @param transparent 透明值
* @return 返回对应的颜色
*/
public static int getColor(int red, int green, int blue, int transparent) {
int color = 0;
color |= red;
color |= green << 8;
color |= blue << 16;
color |= transparent << 24;
return color;
}
/**
* 获取颜色中的红色的值
*
* @param color 颜色
* @return 红色的值。范围位0~255
*/
public static int getRed(int color) {
return color & mask;
}
/**
* 获取颜色中的绿色的值
*
* @param color 颜色
* @return 绿色的值。范围位0~255
*/
public static int getGreen(int color) {
return (color >>> 8) & mask;
}
/**
* 获取颜色中的蓝色的值
*
* @param color 颜色
* @return 蓝色的值。范围位0~255
*/
public static int getBlue(int color) {
return (color >>> 16) & mask;
}
/**
* 获取颜色中的透明度的值
*
* @param color 颜色
* @return 透明度的值。范围位0~255
*/
public static int getTransparent(int color) {
return (color >>> 24) & mask;
}
}
DrawGraphStrategy
package utils;
import component.Canvas;
import component.Graph;
import component.Paint;
import java.util.List;
/**
* created by anriku on 2019-03-29
*/
public interface DrawGraphStrategy {
void drawGraphOnCanvas(Canvas canvas, List<Graph> graphs, Paint paint);
}
SimpleDrawGraphStrategy
package utils;
import component.Canvas;
import component.Graph;
import component.Paint;
import java.util.List;
/**
* created by anriku on 2019-03-29
*/
public class SimpleDrawGraphStrategy implements DrawGraphStrategy {
@Override
public void drawGraphOnCanvas(Canvas canvas, List<Graph> graphs, Paint paint) {
drawGraphs(canvas, graphs, paint);
}
public void drawGraphs(Canvas canvas, List<Graph> graphs, Paint paint) {
for (Graph graph : graphs) {
drawGraph(canvas, graph, paint);
}
}
public void drawGraph(Canvas canvas, Graph graph, Paint paint) {
graph.traverseAllPoint(new Graph.OnTraverse() {
@Override
public void onTraverse(int x, int y) {
canvas.setColorByPosition(x, y, paint.getPaintColor());
}
});
}
}
主包
FillProgram
import component.*;
import utils.DrawGraphStrategy;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* 主要有两个功能：
* 1. 对画板初始化
* 2. 从一个种子点开始进行填充
* <p>
* created by anriku on 2019-03-30
*/
public class FillProgram {
private Canvas mCanvas;
private Paint mPaint;
private List<Graph> mGraphs;
private DrawGraphStrategy mDrawGraphStrategy;
public FillProgram(Canvas canvas, Paint paint, List<Graph> graphs, DrawGraphStrategy drawGraphStrategy) {
this.mCanvas = canvas;
this.mPaint = paint;
this.mGraphs = graphs;
this.mDrawGraphStrategy = drawGraphStrategy;
}
/**
* 对填充程序进行初始化
* <p>
* 主要的工作是对画板进行重置；
* 然后是通过对应的策略在画板上进行画图。
*/
public void init() {
mCanvas.resetCanvasColor(mCanvas.getCanvasBgColor());
mDrawGraphStrategy.drawGraphOnCanvas(mCanvas, mGraphs, mPaint);
}
/**
* 从一个种子点开始填充
*
* @param point 种子点
*/
public void fillFromASeedPoint(Point point) {
Stack<Point> stack = new Stack<>();
stack.push(point);
while (!stack.isEmpty()) {
Point popPoint = stack.pop();
stack.addAll(fill(popPoint));
}
}
/**
* 真正实现填充算法的方法
*
* @param point 种子点
* @return 新的种子点
*/
private List<Point> fill(Point point) {
int leftX = point.x;
int rightX = point.x + 1;
int y = point.y;
// 向左进行填充
for (; leftX >= 0; leftX--) {
if (mCanvas.getColorByPosition(leftX, y) == mCanvas.getCanvasBgColor()) {
mCanvas.setColorByPosition(leftX, y, mPaint.getPaintColor());
} else {
break;
}
}
// 向右进行填充
for (; rightX < mCanvas.getWidth(); rightX++) {
if (mCanvas.getColorByPosition(rightX, y) == mCanvas.getCanvasBgColor()) {
mCanvas.setColorByPosition(rightX, y, mPaint.getPaintColor());
} else {
break;
}
}
leftX++;
rightX--;
List<Point> newPoints = new ArrayList<>();
// 添加当前行的上一行的新的种子点
newPoints.addAll(getNewPoints(leftX, rightX, point.y - 1));
// 添加当前一行下一行的新的种子点
newPoints.addAll(getNewPoints(leftX, rightX, point.y + 1));
return newPoints;
}
/**
* 本次扫描行的附近一行的新的种子点。
*
* @param leftX 本次扫描行左边最后被填充的点
* @param rightX 本次扫描行右边最后被填充的点
* @param y 获取新种子点的行坐标
* @return 返回新的种子点
*/
private List<Point> getNewPoints(int leftX, int rightX, int y) {
List<Point> points = new ArrayList<>();
if (y < 0 || y >= mCanvas.getHeight()) {
return points;
}
for (int x = leftX; x <= rightX; x++) {
if (mCanvas.getColorByPosition(x, y) == mCanvas.getCanvasBgColor() &&
(x == rightX || x >= mCanvas.getWidth() - 1 || mCanvas.getColorByPosition(x + 1, y) == mCanvas.getCanvasBgColor())) {
points.add(new Point(x, y));
}
}
return points;
}
}
Main
import component.*;
import utils.Colors;
import utils.DrawGraphStrategy;
import utils.SimpleDrawGraphStrategy;
import java.util.ArrayList;
import java.util.List;
/**
* created by anriku on 2019-03-29
*/
public class Main {
public static void main(String[] args) {
// 10 x 10的画板，颜色为白色
Canvas canvas = new Canvas(10, 10, Colors.getColor(255, 255, 255, 255));
// 黑色的画笔
Paint paint = new Paint(Colors.getColor(0, 0, 0, 255));
// 将被画到画板的图形
List<Graph> graphs = new ArrayList<Graph>() {{
add(new SimpleGraph());
}};
// 将图形画到画板的策略类
DrawGraphStrategy strategy = new SimpleDrawGraphStrategy();
// 进行填充的程序
FillProgram fillProgram = new FillProgram(canvas, paint, graphs, strategy);
// 进行初始化，主要是将画板的颜色重置，然后在画板上画上图形
fillProgram.init();
System.out.println("填充前的画板：");
// 显示填充前的画板
canvas.displayCanvas();
System.out.println("==========================================");
// 从一个种子点开始进行填充
fillProgram.fillFromASeedPoint(new Point(0, 0));
System.out.println("填充后的画板：");
// 显示填充后的画板
canvas.displayCanvas();
}
}
总结
今天的内容没啥可总结的，其实主要的就是扫描线算法的实现。其实这道题是我面试阿里的一道笔试题，刚开始没啥思路，但是后面仔细想了下问题发现是之前学习计算机图形学的扫描线填充算法，想想其实现的算法也不是太复杂。
