今天給大家分享一下計(jì)算機(jī)圖形學(xué)中狞山，掃描線填充算法。
題目主要有下面一些限制：
- 有一個(gè)畫(huà)板叉寂，這個(gè)畫(huà)板有一定的寬高限制
- 畫(huà)板有一些封閉圖形
- 然后在畫(huà)板隨機(jī)取一點(diǎn)萍启，將這點(diǎn)所在封閉圖形或者是在所有封閉圖形外畫(huà)板內(nèi)的區(qū)域進(jìn)行填充。
這里畫(huà)板的顏色就取白色，畫(huà)筆的顏色就取黑色勘纯。
程序思路
在此題中局服，主要的難點(diǎn)在于圖形填充。我使用了圖形學(xué)中的掃描線填充算法來(lái)進(jìn)行實(shí)現(xiàn)驳遵。主要的思路就是：
隨機(jī)的點(diǎn)的點(diǎn)作為一個(gè)種子點(diǎn)加入一個(gè)種子點(diǎn)棧中淫奔。
從棧中取出一個(gè)種子點(diǎn)，分別向兩邊進(jìn)行填充堤结，直到遇到了封閉圖形的邊界點(diǎn)或者是畫(huà)板的邊界就停止唆迁。
經(jīng)過(guò)第一步會(huì)得到兩個(gè)變量。leftX表示上面最左邊被填充的點(diǎn)的x坐標(biāo)竞穷，rightX表示上面最右邊被填充的點(diǎn)的x坐標(biāo)唐责。
然后，對(duì)這次的掃描行的上一行在[leftX, rightX]區(qū)間中進(jìn)行掃描来庭。遇到非畫(huà)板顏色(封閉圖形的邊界點(diǎn))就將邊界點(diǎn)左邊的點(diǎn)作為新的種子點(diǎn)添進(jìn)一個(gè)棧數(shù)據(jù)結(jié)構(gòu)中妒蔚。如果rightX所在的點(diǎn)為畫(huà)板顏色仍然作為種子點(diǎn)添加進(jìn)去。
對(duì)掃描行下一行依然用類似的算法進(jìn)行新的種子點(diǎn)的添加月弛。
然后循環(huán)從棧中取出種子點(diǎn)并回到第二步肴盏。直到種子點(diǎn)棧為空為止。
下面是一張種子生成的位置及時(shí)間：
image
代碼分析
image
Component包
Canvas類
表示畫(huà)板的類帽衙。保存有一個(gè)畫(huà)板寬畫(huà)板高的二維int數(shù)據(jù)表示各個(gè)點(diǎn)的顏色*
Graph類
所有圖形的接口類菜皂。SimpleGraph類為一個(gè)簡(jiǎn)單的實(shí)現(xiàn)類
Paint類
表示畫(huà)筆的類。保存一個(gè)畫(huà)筆的顏色厉萝。
Point類
表示點(diǎn)的類恍飘。保存點(diǎn)的x、y坐標(biāo)谴垫。
utils包
Colors類
顏色工具類章母。int值有32位，剛好可以8位一組分別存儲(chǔ)RGBA翩剪。這個(gè)類就是用于將RGBA分別的值合成一個(gè)int顏色值乳怎，或者通過(guò)一個(gè)顏色值獲取對(duì)應(yīng)的RGBA值。
DrawGraphStrategy類
這個(gè)類是用于通過(guò)Canvas前弯、Paint以及Graph在Canvas上畫(huà)圖的類蚪缀。SimpleGraphStrategy為簡(jiǎn)單的遍歷Graph集合畫(huà)圖的類。通過(guò)一個(gè)Strategy恕出，如果有必要可以通過(guò)Strategy對(duì)Graph進(jìn)行一下過(guò)濾询枚。
主類
FillProgram
這個(gè)類是重要的類金蜀，是用來(lái)組裝所有的類的惠险。
- 首先通過(guò)其中的init方法可以將Canvas重置渣慕，然后通過(guò)DrawGraphStrategy類在畫(huà)板上進(jìn)行封閉圖形的繪制
- 然后通過(guò)調(diào)用fillFromASeedPoint方法可以給定一個(gè)初始的種子點(diǎn)對(duì)點(diǎn)所在的封閉圖形，或者所有封閉圖形外進(jìn)行填充眨猎。
Main類
這個(gè)類主要用于啟用一個(gè)簡(jiǎn)單的事例程序的强经。
詳細(xì)代碼
代碼中注釋很詳細(xì)兰迫，而且上面對(duì)每個(gè)類都做了相應(yīng)的分析。這里就只把代碼貼出來(lái)了！
component包
Canvas
package component;
import utils.Colors;
/**
* 畫(huà)板類
* <p>
* created by anriku on 2019-03-29
*/
public class Canvas {
// 用一個(gè)二維數(shù)組存儲(chǔ)畫(huà)板對(duì)應(yīng)位置的顏色棘利。int有32位，由低到高依次存儲(chǔ)RGBA。
private int[][] mColors;
// 畫(huà)板的背景色
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);
}
/**
* 重置畫(huà)板的所有點(diǎn)的顏色
*
* @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 畫(huà)板寬度
*/
public int getWidth() {
return mColors[0].length;
}
/**
* @return 畫(huà)板高度
*/
public int getHeight() {
return mColors.length;
}
/**
* 設(shè)置對(duì)應(yīng)點(diǎn)的顏色
*
* @param x 點(diǎn)的x坐標(biāo)
* @param y 點(diǎn)的y坐標(biāo)
* @param color 顏色
*/
public void setColorByPosition(int x, int y, int color) {
mColors[y][x] = color;
}
/**
* 獲取對(duì)應(yīng)點(diǎn)的顏色
*
* @param x 點(diǎn)的x坐標(biāo)
* @param y 點(diǎn)的y坐標(biāo)
* @return 返回對(duì)應(yīng)點(diǎn)的顏色
*/
public int getColorByPosition(int x, int y) {
return mColors[y][x];
}
/**
* 獲取畫(huà)板的背景顏色
*
* @return 顏色
*/
public int getCanvasBgColor() {
return mCanvasBgColor;
}
/**
* 顯示畫(huà)板的內(nèi)容毕谴。
* W：表示背景色
* B：表示畫(huà)筆色
*/
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 {
/**
* 所有圖形提供一個(gè)公共的遍歷所有圖形的點(diǎn)的方法循帐。實(shí)現(xiàn)交給各個(gè)圖形自己瘪匿。
* <p>
* 如果是多邊形或者有規(guī)則的弧形可以自己使用對(duì)應(yīng)的方程來(lái)遍歷點(diǎn)棋弥。
* 如果是不規(guī)則圖形可以把所有點(diǎn)存儲(chǔ)在一個(gè)數(shù)組中進(jìn)行遍歷粉寞。
*
* @param onTraverse 回掉方法
*/
void traverseAllPoint(OnTraverse onTraverse);
/**
* 回掉接口
*/
interface OnTraverse {
void onTraverse(int x, int y);
}
}
Paint
package component;
import utils.Colors;
/**
* 畫(huà)筆
* created by anriku on 2019-03-29
*/
public class Paint {
// 畫(huà)筆的顏色
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;
/**
* 代表一個(gè)點(diǎn)
* <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) {
// 簡(jiǎn)單的畫(huà)兩個(gè)靠角落的矩形測(cè)試双炕。
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組成對(duì)應(yīng)的顏色int。
*
* @param red 紅色值
* @param green 綠色值
* @param blue 藍(lán)色值
* @param transparent 透明值
* @return 返回對(duì)應(yīng)的顏色
*/
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;
}
/**
* 獲取顏色中的藍(lán)色的值
*
* @param color 顏色
* @return 藍(lán)色的值。范圍位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;
/**
* 主要有兩個(gè)功能：
* 1. 對(duì)畫(huà)板初始化
* 2. 從一個(gè)種子點(diǎn)開(kāi)始進(jìn)行填充
* <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;
}
/**
* 對(duì)填充程序進(jìn)行初始化
* <p>
* 主要的工作是對(duì)畫(huà)板進(jìn)行重置死相；
* 然后是通過(guò)對(duì)應(yīng)的策略在畫(huà)板上進(jìn)行畫(huà)圖。
*/
public void init() {
mCanvas.resetCanvasColor(mCanvas.getCanvasBgColor());
mDrawGraphStrategy.drawGraphOnCanvas(mCanvas, mGraphs, mPaint);
}
/**
* 從一個(gè)種子點(diǎn)開(kāi)始填充
*
* @param point 種子點(diǎn)
*/
public void fillFromASeedPoint(Point point) {
Stack<Point> stack = new Stack<>();
stack.push(point);
while (!stack.isEmpty()) {
Point popPoint = stack.pop();
stack.addAll(fill(popPoint));
}
}
/**
* 真正實(shí)現(xiàn)填充算法的方法
*
* @param point 種子點(diǎn)
* @return 新的種子點(diǎn)
*/
private List<Point> fill(Point point) {
int leftX = point.x;
int rightX = point.x + 1;
int y = point.y;
// 向左進(jìn)行填充
for (; leftX >= 0; leftX--) {
if (mCanvas.getColorByPosition(leftX, y) == mCanvas.getCanvasBgColor()) {
mCanvas.setColorByPosition(leftX, y, mPaint.getPaintColor());
} else {
break;
}
}
// 向右進(jìn)行填充
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<>();
// 添加當(dāng)前行的上一行的新的種子點(diǎn)
newPoints.addAll(getNewPoints(leftX, rightX, point.y - 1));
// 添加當(dāng)前一行下一行的新的種子點(diǎn)
newPoints.addAll(getNewPoints(leftX, rightX, point.y + 1));
return newPoints;
}
/**
* 本次掃描行的附近一行的新的種子點(diǎn)咬像。
*
* @param leftX 本次掃描行左邊最后被填充的點(diǎn)
* @param rightX 本次掃描行右邊最后被填充的點(diǎn)
* @param y 獲取新種子點(diǎn)的行坐標(biāo)
* @return 返回新的種子點(diǎn)
*/
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的畫(huà)板算撮，顏色為白色
Canvas canvas = new Canvas(10, 10, Colors.getColor(255, 255, 255, 255));
// 黑色的畫(huà)筆
Paint paint = new Paint(Colors.getColor(0, 0, 0, 255));
// 將被畫(huà)到畫(huà)板的圖形
List<Graph> graphs = new ArrayList<Graph>() {{
add(new SimpleGraph());
}};
// 將圖形畫(huà)到畫(huà)板的策略類
DrawGraphStrategy strategy = new SimpleDrawGraphStrategy();
// 進(jìn)行填充的程序
FillProgram fillProgram = new FillProgram(canvas, paint, graphs, strategy);
// 進(jìn)行初始化生宛，主要是將畫(huà)板的顏色重置，然后在畫(huà)板上畫(huà)上圖形
fillProgram.init();
System.out.println("填充前的畫(huà)板：");
// 顯示填充前的畫(huà)板
canvas.displayCanvas();
System.out.println("==========================================");
// 從一個(gè)種子點(diǎn)開(kāi)始進(jìn)行填充
fillProgram.fillFromASeedPoint(new Point(0, 0));
System.out.println("填充后的畫(huà)板：");
// 顯示填充后的畫(huà)板
canvas.displayCanvas();
}
}
總結(jié)
今天的內(nèi)容沒(méi)啥可總結(jié)的肮柜，其實(shí)主要的就是掃描線算法的實(shí)現(xiàn)陷舅。其實(shí)這道題是我面試阿里的一道筆試題，剛開(kāi)始沒(méi)啥思路审洞，但是后面仔細(xì)想了下問(wèn)題發(fā)現(xiàn)是之前學(xué)習(xí)計(jì)算機(jī)圖形學(xué)的掃描線填充算法莱睁，想想其實(shí)現(xiàn)的算法也不是太復(fù)雜。
