android 색칠하기 알고리즘

android 색칠하기 알고리즘을 검색해 보았다.

FloodFill Algoritham 이라고 검색하면 나온다.

사용자가 선택한 포인트 좌표값의 색깔과 인접한 근처의 색깔을  지정한 색깔로 바꾸는 알고리즘이다.

1. 기본적인 FloodFill  Algoritham : 처리 속도가 좀 느리다. 약 2초 전후

혹자는 JNI로 변환하면 빠르다고 한다. ( http://aroundck.tistory.com/m/post/2592 )

   //
public class FloodFill {
	public void floodFill(Bitmap image, Point node, int targetColor, int replacementColor) {
		int width = image.getWidth();
		int height = image.getHeight();
		int target = targetColor;
		int replacement = replacementColor;
		if (target != replacement) {
			Queue queue = new LinkedList();
			do {

				int x = node.x;
				int y = node.y;
				while (x > 0 && image.getPixel(x - 1, y) == target) {
					x--;

				}
				boolean spanUp = false;
				boolean spanDown = false;
				while (x < width && image.getPixel(x, y) == target) {
					image.setPixel(x, y, replacement);
					if (!spanUp && y > 0 && image.getPixel(x, y - 1) == target) {
						queue.add(new Point(x, y - 1));
						spanUp = true;
					} else if (spanUp && y > 0
							&& image.getPixel(x, y - 1) != target) {
						spanUp = false;
					}
					if (!spanDown && y < height - 1
							&& image.getPixel(x, y + 1) == target) {
						queue.add(new Point(x, y + 1));
						spanDown = true;
					} else if (spanDown && y < height - 1
							&& image.getPixel(x, y + 1) != target) {
						spanDown = false;
					}
					x++;
				}
			} while ((node = queue.poll()) != null);
		}
	}
}

2. 지정된 컬러로 바꾸는 대신에 지정된 이미지로 바꿀수 있도록 수정해 보았다. 

이때는 사용자가 선택한 포인트 좌표값의 색깔대신에 경계선의 색깔을 입력해야한다.

단점은 한번만 배경을 바꿀 수 있다는것.. ㅠ.ㅠ 제대로 수정하려면 시간이 좀 걸릴듯..

   //
public class FloodFill {
	public void floodFillImageOnce(Bitmap image, Point node, int targetColor, Bitmap fillImage) {  // 배경 이미지로 한번만 칠하기, 두번 안됨.
		int width = image.getWidth();
		int height = image.getHeight();
		int target = targetColor;


		Queue queue = new LinkedList();
		do {

			int x = node.x;
			int y = node.y;
			while (x > 0 && image.getPixel(x - 1, y) == target) {
				x--;

			}
			boolean spanUp = false;
			boolean spanDown = false;
			while (x < width && image.getPixel(x, y) == target) {
				image.setPixel(x, y, fillImage.getPixel(x, y));
				if (!spanUp && y > 0 && image.getPixel(x, y - 1) == target) {
					queue.add(new Point(x, y - 1));
					spanUp = true;
				} else if (spanUp && y > 0
						&& image.getPixel(x, y - 1) != target) {
					spanUp = false;
				}
				if (!spanDown && y < height - 1
						&& image.getPixel(x, y + 1) == target) {
					queue.add(new Point(x, y + 1));
					spanDown = true;
				} else if (spanDown && y < height - 1
						&& image.getPixel(x, y + 1) != target) {
					spanDown = false;
				}
				x++;
			}
		} while ((node = queue.poll()) != null);

	}	

3. QueueLinearFloodFiller  아주 빠름. (추천)

   //
package com.cheil.gscm.colorpainting;

import java.util.LinkedList;
import java.util.Queue;

import android.graphics.Bitmap;
import android.graphics.Canvas;
import android.graphics.Color;

public class QueueLinearFloodFiller {

	protected Bitmap image = null;
	protected int[] tolerance = new int[] { 0, 0, 0 };
	protected int width = 0;
	protected int height = 0;
	protected int[] pixels = null;
	protected int fillColor = 0;
	protected int[] startColor = new int[] { 0, 0, 0 };
	protected boolean[] pixelsChecked;
	protected Queue ranges;

	// Construct using an image and a copy will be made to fill into,
	// Construct with BufferedImage and flood fill will write directly to
	// provided BufferedImage
	public QueueLinearFloodFiller(Bitmap img) {
		copyImage(img);
	}

	public QueueLinearFloodFiller(Bitmap img, int targetColor, int newColor) {
		useImage(img);

		setFillColor(newColor);
		setTargetColor(targetColor);
	}
	
	public QueueLinearFloodFiller(Bitmap img, int targetColor, Bitmap newImg) {
		useImage(img);

		setTargetColor(targetColor);
	}	


	public void setTargetColor(int targetColor) {
		startColor[0] = Color.red(targetColor);
		startColor[1] = Color.green(targetColor);
		startColor[2] = Color.blue(targetColor);
	}

	public int getFillColor() {
		return fillColor;
	}

	public void setFillColor(int value) {
		fillColor = value;
	}

	public int[] getTolerance() {
		return tolerance;
	}

	public void setTolerance(int[] value) {
		tolerance = value;
	}

	public void setTolerance(int value) {
		tolerance = new int[] { value, value, value };
	}

	public Bitmap getImage() {
		return image;
	}

	public void copyImage(Bitmap img) {
		// Copy data from provided Image to a BufferedImage to write flood fill
		// to, use getImage to retrieve
		// cache data in member variables to decrease overhead of property calls
		width = img.getWidth();
		height = img.getHeight();

		image = Bitmap.createBitmap(width, height, Bitmap.Config.RGB_565);
		Canvas canvas = new Canvas(image);
		canvas.drawBitmap(img, 0, 0, null);

		pixels = new int[width * height];

		image.getPixels(pixels, 0, width, 1, 1, width - 1, height - 1);
	}

	public void useImage(Bitmap img) {
		// Use a pre-existing provided BufferedImage and write directly to it
		// cache data in member variables to decrease overhead of property calls
		width = img.getWidth();
		height = img.getHeight();
		image = img;

		pixels = new int[width * height];

		image.getPixels(pixels, 0, width, 1, 1, width - 1, height - 1);
	}

	protected void prepare() {
		// Called before starting flood-fill
		pixelsChecked = new boolean[pixels.length];
		ranges = new LinkedList();
	}

	// Fills the specified point on the bitmap with the currently selected fill
	// color.
	// int x, int y: The starting coords for the fill
	public void floodFill(int x, int y) {
		// Setup
		prepare();

		if (startColor[0] == 0) {
			// ***Get starting color.
			int startPixel = pixels[(width * y) + x];
			startColor[0] = (startPixel >> 16) & 0xff;
			startColor[1] = (startPixel >> 8) & 0xff;
			startColor[2] = startPixel & 0xff;
		}

		// ***Do first call to floodfill.
		LinearFill(x, y);

		// ***Call floodfill routine while floodfill ranges still exist on the
		// queue
		FloodFillRange range;

		while (ranges.size() > 0) {
			// **Get Next Range Off the Queue
			range = ranges.remove();

			// **Check Above and Below Each Pixel in the Floodfill Range
			int downPxIdx = (width * (range.Y + 1)) + range.startX;
			int upPxIdx = (width * (range.Y - 1)) + range.startX;
			int upY = range.Y - 1;// so we can pass the y coord by ref
			int downY = range.Y + 1;

			for (int i = range.startX; i <= range.endX; i++) {
				// *Start Fill Upwards
				// if we're not above the top of the bitmap and the pixel above
				// this one is within the color tolerance
				if (range.Y > 0 && (!pixelsChecked[upPxIdx])
						&& CheckPixel(upPxIdx))
					LinearFill(i, upY);

				// *Start Fill Downwards
				// if we're not below the bottom of the bitmap and the pixel
				// below this one is within the color tolerance
				if (range.Y < (height - 1) && (!pixelsChecked[downPxIdx])
						&& CheckPixel(downPxIdx))
					LinearFill(i, downY);

				downPxIdx++;
				upPxIdx++;
			}
		}

		image.setPixels(pixels, 0, width, 1, 1, width - 1, height - 1);
	}

	// Finds the furthermost left and right boundaries of the fill area
	// on a given y coordinate, starting from a given x coordinate, filling as
	// it goes.
	// Adds the resulting horizontal range to the queue of floodfill ranges,
	// to be processed in the main loop.

	// int x, int y: The starting coords  TODO
	protected void LinearFill(int x, int y) {
		// ***Find Left Edge of Color Area
		int lFillLoc = x; // the location to check/fill on the left
		int pxIdx = (width * y) + x;
				
		while (true) {
			// **fill with the color   TODO
			pixels[pxIdx] = fillColor;				


			// **indicate that this pixel has already been checked and filled
			pixelsChecked[pxIdx] = true;

			// **de-increment
			lFillLoc--; // de-increment counter
			pxIdx--; // de-increment pixel index

			// **exit loop if we're at edge of bitmap or color area
			if (lFillLoc < 0 || (pixelsChecked[pxIdx]) || !CheckPixel(pxIdx)) {
				break;
			}
		}

		lFillLoc++;

		// ***Find Right Edge of Color Area
		int rFillLoc = x; // the location to check/fill on the left

		pxIdx = (width * y) + x;

		while (true) {
			// **fill with the color
			pixels[pxIdx] = fillColor;				

			// **indicate that this pixel has already been checked and filled
			pixelsChecked[pxIdx] = true;

			// **increment
			rFillLoc++; // increment counter
			pxIdx++; // increment pixel index

			// **exit loop if we're at edge of bitmap or color area
			if (rFillLoc >= width || pixelsChecked[pxIdx] || !CheckPixel(pxIdx)) {
				break;
			}
		}

		rFillLoc--;

		// add range to queue
		FloodFillRange r = new FloodFillRange(lFillLoc, rFillLoc, y);

		ranges.offer(r);
	}

	// Sees if a pixel is within the color tolerance range.
	protected boolean CheckPixel(int px) {
		int red = (pixels[px] >>> 16) & 0xff;
		int green = (pixels[px] >>> 8) & 0xff;
		int blue = pixels[px] & 0xff;

		return (red >= (startColor[0] - tolerance[0])
				&& red <= (startColor[0] + tolerance[0])
				&& green >= (startColor[1] - tolerance[1])
				&& green <= (startColor[1] + tolerance[1])
				&& blue >= (startColor[2] - tolerance[2]) && blue <= (startColor[2] + tolerance[2]));
	}

	// Represents a linear range to be filled and branched from.
	protected class FloodFillRange {
		public int startX;
		public int endX;
		public int Y;

		public FloodFillRange(int startX, int endX, int y) {
			this.startX = startX;
			this.endX = endX;
			this.Y = y;
		}
	}
}

아래 링크들은 참조한것들...

도움되었으면.. 로그인이 필요없는 추천 꾹~~

[이거 참조 하면 될듯]
http://stackoverflow.com/questions/9629299/android-how-to-fill-color-to-the-specific-part-of-the-image-only

http://stackoverflow.com/questions/8801047/how-to-fill-color-in-image-in-particular-area

http://aroundck.tistory.com/2592

[이건 빠른것]
http://www.codeproject.com/Articles/364413/Queue-Linear-Flood-Fill-A-Fast-Flood-Fill-Algorith
<copyImage 함수 있는곳>
http://stackoverflow.com/questions/8070401/android-flood-fill-algorithm

색칠하기 알고리즘 [링크 많음, 정리 잘되었음]
http://avaminzhang.wordpress.com/2013/10/17/flood-fill-algorithm/