Android 불규칙 폐쇄 영역 색상 채 우기 인 스 턴 스 코드

개술
지난 편의 서술 에서 우 리 는 그림 의 색 채 우기(상세 한 내용 은 도장:Android 불규칙 이미지 색상 채 우기 게임를 통 해 완성 하 였 으 나 착색 게임 에 서 는 경계 에 기반 한 이미지 채 우기 가 더 많 았 다.이 블 로 그 는 상세 하 게 설명 할 것 이다.
그림 의 충전 에는 두 가지 고전 알고리즘 이 있다.
하 나 는 피 드 충전 법 이다.
피 드 충전 법 이론 적 으로 임의의 구역 과 도형 을 채 울 수 있 지만 이런 알고리즘 은 대량의 반복 적 인 스 택 과 대규모 재 귀 가 존재 하여 충전 효율 을 낮 출 수 있다.
다른 하 나 는 스캐닝 라인 충전 법 이다.
메모:실제로 이미지 채 우 는 알고리즘 이 많 습 니 다.관심 이 있 으 면 Google 학술 지 를 찾 아 보 세 요.
ok,다음은 오늘 의 효과 도 를 살 펴 보 겠 습 니 다.

ok,이런 컬러 충전 이 전편 의 베이스 층 보다 소재 준비 에 있어 서 훨씬 쉬 운 것 을 볼 수 있 습 니 다~~~
원리 분석
먼저 원 리 를 약술 하고 우 리 는 클릭 할 때 클릭 점 의'색'을 얻 은 다음 에 우리 가 선택 한 알고리즘 에 따라 색 을 채 우 면 된다.
알고리즘 1:피 드 충전 법,4 연결/8 연결
알고리즘 소개:어떤 영역 을 빨간색 으로 채 우 겠 다 고 가정 합 니 다.
사용자 가 클릭 한 픽 셀 을 시작 으로 상하 좌우(8 연 결 된 왼쪽 위,왼쪽 아래,오른쪽 위,오른쪽 아래)로 색상 을 판단 하고 네 방향 에 있 는 색상 이 현재 클릭 한 픽 셀 과 일치 하면 색상 을 대상 색 으로 변경 합 니 다.그리고 이 과정 을 계속 하 겠 습 니 다.
ok,이것 은 재 귀적 인 과정 을 볼 수 있 습 니 다.1 개 에서 4 개,4 개 에서 16 개 까지 계속 연장 되 는 것 을 볼 수 있 습 니 다.만약 이러한 알고리즘 에 따른다 면,당신 은 이러한 코드 를 쓸 것 입 니 다.

/**
 * @param pixels     
 * @param w   
 * @param h   
 * @param pixel       
 * @param newColor    
 * @param i    
 * @param j    
 */
 private void fillColor01(int[] pixels, int w, int h, int pixel, int newColor, int i, int j)
 {
 int index = j * w + i;
 if (pixels[index] != pixel || i >= w || i < 0 || j < 0 || j >= h)
 return;
 pixels[index] = newColor;
 // 
 fillColor01(pixels, w, h, pixel, newColor, i, j - 1);
 // 
 fillColor01(pixels, w, h, pixel, newColor, i + 1, j);
 // 
 fillColor01(pixels, w, h, pixel, newColor, i, j + 1);
 // 
 fillColor01(pixels, w, h, pixel, newColor, i - 1, j);
 }

코드 는 간단 하지만 실행 하면 StackOverflow Exception 이상 이 발생 합 니 다.이 이상 은 주로 대량의 재 귀 로 인 한 것 입 니 다.간단 하지만 모 바 일 기기 에서 이 방법 을 사용 하면 안 된다.
그래서 저 는 이 방법 이 재 귀 깊이 가 너무 많은 것 이 아니 라 Stack 을 사용 하여 픽 셀 점 을 저장 하고 재 귀 깊이 와 횟수 를 줄 일 수 있다 고 생각 했 습 니 다.그래서 저 는 코드 를 다음 과 같은 방식 으로 바 꿀 수 있 습 니 다.

/**
 * @param pixels     
 * @param w   
 * @param h   
 * @param pixel       
 * @param newColor    
 * @param i    
 * @param j    
 */
 private void fillColor(int[] pixels, int w, int h, int pixel, int newColor, int i, int j)
 {
 mStacks.push(new Point(i, j));

 while (!mStacks.isEmpty())
 {
 Point seed = mStacks.pop();
 Log.e("TAG", "seed = " + seed.x + " , seed = " + seed.y);

 int index = seed.y * w + seed.x;

 pixels[index] = newColor;
 if (seed.y > 0)
 {
 int top = index - w;
 if (pixels[top] == pixel)
 {

 mStacks.push(new Point(seed.x, seed.y - 1));
 }
 }

 if (seed.y < h - 1)
 {
 int bottom = index + w;
 if (pixels[bottom] == pixel)
 {
 mStacks.push(new Point(seed.x, seed.y + 1));
 }
 }

 if (seed.x > 0)
 {
 int left = index - 1;
 if (pixels[left] == pixel)
 {
 mStacks.push(new Point(seed.x - 1, seed.y));
 }
 }

 if (seed.x < w - 1)
 {
 int right = index + 1;
 if (pixels[right] == pixel)
 {
 mStacks.push(new Point(seed.x + 1, seed.y));
 }
 }

 }
 }

방법의 사상 도 비교적 간단 하 다.현재 픽 셀 을 창고 에 넣 은 다음 에 창고 에서 착색 한 다음 에 각각 네 가지 방향 을 판단 하고 조건 에 부합 하면 창고 에 들어간다(창고 가 비어 있 지 않 으 면 지속 적 으로 운행 한다).ok,이 방법 은 저도 뛰 어 보 려 고 했 습 니 다.네,이번 에는 틀 리 지 않 을 겁 니 다.하지만 속도 가 너무 느 려 요~~느 려 서 받 아들 일 수 없습니다.관심 이 있 으 면 시도 해 보 세 요.ANR 이 라면 기 다 려 보 세 요).
이렇게 보면 첫 번 째 알고리즘 은 우리 가 고려 하지 않 고 사용 할 방법 이 없다.주요 원인 은 사각형 의 같은 색 구역 에 대해 모두 채 워 야 한다 고 가정 하 는 것 이 고 알고리즘 하 나 는 여전히 각종 스 택 이다.그래서 두 번 째 알고리즘 을 고려 합 니 다.
스캐닝 라인 충전 법
알고리즘 사상[4]:
피 드 점 을 저장 하기 위해 빈 스 택 을 초기 화하 고 피 드 점(x,y)을 스 택 에 넣 습 니 다.
스 택 이 비어 있 는 지 여 부 를 판단 합 니 다.스 택 이 비어 있 으 면 알고리즘 을 끝 냅 니 다.그렇지 않 으 면 스 택 꼭대기 요 소 를 현재 스 캔 라인 의 피 드 점(x,y)으로 꺼 내 고 y 는 현재 스 캔 라인 입 니 다.
피 드 점(x,y)에서 출발 하여 현재 스캐닝 라인 을 따라 왼쪽,오른쪽 두 방향 으로 경계 까지 채 웁 니 다.구간 의 왼쪽,오른쪽 점 좌 표를 각각 xLeft 와 xRight 로 표시 합 니 다.
현재 스 캔 라인 과 인접 한 y-1 과 y+1 두 개의 스 캔 라인 이 구간[xLeft,xRight]에 있 는 픽 셀 을 각각 검사 하고 xRight 부터 xLeft 방향 으로 검색 합 니 다.스 캔 구간 이 AAABAAC(A 는 피 드 점 색상)이 라 고 가정 하면 B 와 C 앞의 A 를 피 드 점 으로 스 택 에 누 른 다음(2)단계 로 돌아 갑 니 다.
상기 참고 문헌[4]을 참고 하여 수정 을 했 습 니 다.글[4]에서 알고리즘 을 설명 하고 테스트 에 문제 가 있어 서 수정 을 했 습 니 다.
이 알고리즘 을 볼 수 있 습 니 다.기본적으로 한 줄 한 줄 착색 되 어 있 습 니 다.그러면 큰 덩어리 에 착색 이 필요 한 구역 의 효율 이 알고리즘 보다 훨씬 높 습 니 다.
ok,알고리즘 에 대한 절차 가 모호 하 다 고 생각 합 니 다.잠시 후에 저희 코드 를 참조 할 수 있 습 니 다.알고리즘 을 선택 한 후 인 코딩 을 시작 합 니 다.
3.인 코딩 실현
우리 코드 에 경계 색 을 도 입 했 습 니 다.설정 하면 착색 경 계 는 이 경계 색 을 참고 합 니 다.그렇지 않 으 면 피 드 색 과 일치 하지 않 으 면 경계 색 이 됩 니 다.
(1)구조 방법 과 측정

public class ColourImageView extends ImageView
{

 private Bitmap mBitmap;
 /**
 *      
 */
 private int mBorderColor = -1;

 private boolean hasBorderColor = false;

 private Stack<Point> mStacks = new Stack<Point>();

 public ColourImageView(Context context, AttributeSet attrs)
 {
 super(context, attrs);

 TypedArray ta = context.obtainStyledAttributes(attrs, R.styleable.ColourImageView);
 mBorderColor = ta.getColor(R.styleable.ColourImageView_border_color, -1);
 hasBorderColor = (mBorderColor != -1);

 L.e("hasBorderColor = " + hasBorderColor + " , mBorderColor = " + mBorderColor);

 ta.recycle();

 }

 @Override
 protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec)
 {
 super.onMeasure(widthMeasureSpec, heightMeasureSpec);

 int viewWidth = getMeasuredWidth();
 int viewHeight = getMeasuredHeight();

 //      ，     view   
 setMeasuredDimension(viewWidth,
 getDrawable().getIntrinsicHeight() * viewWidth / getDrawable().getIntrinsicWidth());
 L.e("view's width = " + getMeasuredWidth() + " , view's height = " + getMeasuredHeight());

 //  drawable，      view     bitmap
 BitmapDrawable drawable = (BitmapDrawable) getDrawable();
 Bitmap bm = drawable.getBitmap();
 mBitmap = Bitmap.createScaledBitmap(bm, getMeasuredWidth(), getMeasuredHeight(), false);
 }

이미지 뷰 계승 을 선택 한 것 을 볼 수 있 습 니 다.그림 을 src 로 설정 하면 됩 니 다.
구조 방법 에서 사용자 정의 경계 색 을 가 져 옵 니 다.당연히 설정 하지 않 아 도 됩 니 다~~
재 작성 측정 의 목적 은 View 와 같은 크기 의 Bitmap 를 얻 기 위해 서 입 니 다.
이제 클릭 입 니 다.
(2)onTouchEvent

@Override
 public boolean onTouchEvent(MotionEvent event)
 {
 final int x = (int) event.getX();
 final int y = (int) event.getY();
 if (event.getAction() == MotionEvent.ACTION_DOWN)
 {
 //  
 fillColorToSameArea(x, y);
 }

 return super.onTouchEvent(event);
 }

 /**
 *   x,y      ，    
 *
 * @param x
 * @param y
 */
 private void fillColorToSameArea(int x, int y)
 {
 Bitmap bm = mBitmap;

 int pixel = bm.getPixel(x, y);
 if (pixel == Color.TRANSPARENT || (hasBorderColor && mBorderColor == pixel))
 {
 return;
 }
 int newColor = randomColor();

 int w = bm.getWidth();
 int h = bm.getHeight();
 //   bitmap     
 int[] pixels = new int[w * h];
 bm.getPixels(pixels, 0, w, 0, 0, w, h);
 //  
 fillColor(pixels, w, h, pixel, newColor, x, y);
 //    bitmap
 bm.setPixels(pixels, 0, w, 0, 0, w, h);
 setImageDrawable(new BitmapDrawable(bm));

 }

볼 수 있 습 니 다.우 리 는 onTouchEvent 에서(x,y)를 얻 은 다음 에 변 경 된 좌 표를 얻 을 수 있 습 니 다.
클릭 점 색상 을 획득 하여 전체 bitmap 의 픽 셀 그룹 을 획득 합 니 다.
이 배열 의 색 을 바 꿉 니 다.
그리고 bitmap 에 다시 설정 하고 ImageView 에 다시 설정 합 니 다.
포 인 트 는 fillColor 를 통 해 배열 의 색 을 바 꾸 는 것 입 니 다.

/**
 * @param pixels     
 * @param w   
 * @param h   
 * @param pixel       
 * @param newColor    
 * @param i    
 * @param j    
 */
 private void fillColor(int[] pixels, int w, int h, int pixel, int newColor, int i, int j)
 {
 //  1：    (x, y)  ；
 mStacks.push(new Point(i, j));

 //  2：       ，
 //           ，                   (x, y)，
 // y       ；
 while (!mStacks.isEmpty())
 {


 /**
 *   3：    (x, y)  ，        、       ，
 *     。        、      xLeft xRight；
 */
 Point seed = mStacks.pop();
 //L.e("seed = " + seed.x + " , seed = " + seed.y);
 int count = fillLineLeft(pixels, pixel, w, h, newColor, seed.x, seed.y);
 int left = seed.x - count + 1;
 count = fillLineRight(pixels, pixel, w, h, newColor, seed.x + 1, seed.y);
 int right = seed.x + count;


 /**
 *   4：
 *              y - 1 y + 1        [xLeft, xRight]    ，
 *  xRight   xLeft    ，        AAABAAC（A      ），
 *    B C   A         ，     （2） ；
 */
 // y-1   
 if (seed.y - 1 >= 0)
 findSeedInNewLine(pixels, pixel, w, h, seed.y - 1, left, right);
 // y+1   
 if (seed.y + 1 < h)
 findSeedInNewLine(pixels, pixel, w, h, seed.y + 1, left, right);
 }

 }

내 가 이 알고리즘 의 네 가지 절 차 를 이 방법 에 명확 하 게 표시 한 것 을 볼 수 있다.자,마지막 으로 의존 하 는 세부 적 인 방법 입 니 다.

 /**
 *         
 *
 * @param pixels
 * @param pixel
 * @param w
 * @param h
 * @param i
 * @param left
 * @param right
 */
 private void findSeedInNewLine(int[] pixels, int pixel, int w, int h, int i, int left, int right)
 {
 /**
 *          
 */
 int begin = i * w + left;
 /**
 *          
 */
 int end = i * w + right;

 boolean hasSeed = false;

 int rx = -1, ry = -1;

 ry = i;

 /**
 *  end begin，        （AAABAAAB， B  A     ）
 */
 while (end >= begin)
 {
 if (pixels[end] == pixel)
 {
 if (!hasSeed)
 {
 rx = end % w;
 mStacks.push(new Point(rx, ry));
 hasSeed = true;
 }
 } else
 {
 hasSeed = false;
 }
 end--;
 }
 }

 /**
 *     ，       
 *
 * @return
 */
 private int fillLineRight(int[] pixels, int pixel, int w, int h, int newColor, int x, int y)
 {
 int count = 0;

 while (x < w)
 {
 //    
 int index = y * w + x;
 if (needFillPixel(pixels, pixel, index))
 {
 pixels[index] = newColor;
 count++;
 x++;
 } else
 {
 break;
 }

 }

 return count;
 }


 /**
 *     ，        
 *
 * @return
 */
 private int fillLineLeft(int[] pixels, int pixel, int w, int h, int newColor, int x, int y)
 {
 int count = 0;
 while (x >= 0)
 {
 //     
 int index = y * w + x;

 if (needFillPixel(pixels, pixel, index))
 {
 pixels[index] = newColor;
 count++;
 x--;
 } else
 {
 break;
 }

 }
 return count;
 }

 private boolean needFillPixel(int[] pixels, int pixel, int index)
 {
 if (hasBorderColor)
 {
 return pixels[index] != mBorderColor;
 } else
 {
 return pixels[index] == pixel;
 }
 }

 /**
 *         
 *
 * @return
 */
 private int randomColor()
 {
 Random random = new Random();
 int color = Color.argb(255, random.nextInt(256), random.nextInt(256), random.nextInt(256));
 return color;
 }

ok,여기까지 코드 소개 완료~~~
마지막 으로 레이아웃 파일 을 붙 여 주세요~~

<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
 xmlns:tools="http://schemas.android.com/tools"
 xmlns:zhy="http://schemas.android.com/apk/res-auto"
 android:layout_width="match_parent"
 android:layout_height="match_parent"
 android:paddingLeft="@dimen/activity_horizontal_margin"
 android:paddingRight="@dimen/activity_horizontal_margin"
 android:paddingTop="@dimen/activity_vertical_margin"
 android:paddingBottom="@dimen/activity_vertical_margin"
 tools:context=".MainActivity">
 <com.zhy.colour_app_01.ColourImageView
 zhy:border_color="#FF000000"
 android:src="@drawable/image_007"
 android:background="#33ff0000"
 android:layout_width="match_parent"
 android:layout_centerInParent="true"
 android:layout_height="match_parent"/>

</RelativeLayout>


<?xml version="1.0" encoding="utf-8"?>
<resources>
 <declare-styleable name="ColourImageView">
 <attr name="border_color" format="color|reference"></attr>
 </declare-styleable>
</resources>

참조 링크
스캐너 피 드 충전 알고리즘 의 해석
이미지 처리 범 홍 충전 알고리즘(Flood Fill Algorithm) )
재 귀 피 드 충전 알고리즘
스캐닝 피 드 충전 알고리즘
이상 은 이 글 의 전체 내용 입 니 다.본 논문 의 내용 이 여러분 의 학습 이나 업무 에 어느 정도 참고 학습 가치 가 있 기 를 바 랍 니 다.궁금 한 점 이 있 으 시 면 댓 글 을 남 겨 주 셔 서 저희 에 대한 지지 에 감 사 드 립 니 다.