Android 다각형 영역 재 귀 피 드 충전 알고리즘 의 예제 코드

평면 영역 충전 알고리즘 은 컴퓨터 그래 픽 분야 의 중요 한 알고리즘 입 니 다.영역 충전 은 한 지역 의 경계(경계 가 없 을 수도 있 고 지정 한 색상 만 제시 할 수도 있 습 니 다)를 제시 하고 경계 범위 안의 모든 픽 셀 을 지정 한 색상 으로 수정 하 라 고 요구 합 니 다(그림 충전 일 수도 있 습 니 다).지역 충전 에서 가장 많이 사용 되 는 것 은 다각형 충전 색 입 니 다.본 고 에서 우 리 는 몇 가지 다각형 구역 충전 알고리즘 을 토론 합 니 다.
1.피 드 충전 알고리즘(Seed Filling)
채 울 영역 이 이미지 메타 데이터 로 제 시 된 경우 피 드 채 우기 알고리즘(Seed Filling)을 사용 하여 영역 채 우기 가 일반적 입 니 다.피 드 충전 알고리즘 은 이미지 데이터 의 영역 과 지역 내의 한 점 을 제시 해 야 합 니 다.이러한 알고리즘 은 인간 과 컴퓨터 의 상호작용 방식 으로 진행 되 는 이미지 충전 작업 에 적합 하고 컴퓨터 가 자동 으로 처리 하고 색상 을 판단 하 는 데 적합 하지 않 습 니 다.이미지 영역 경계 정의 방식 과 점 에 대한 색상 수정 방식 에 따라 피 드 충전 은 몇 가지 로 나 눌 수 있 습 니 다.예 를 들 어 주입 충전 알고리즘(Flood Fill Algorithm),경계 충전 알고리즘(Boundary Fill Algorithm)과 재 귀 와 스 택 횟수 를 줄 이기 위해 개 선 된 스캐닝 라인 피 드 충전 알고리즘 등 입 니 다.
모든 피 드 충전 알고리즘 의 핵심 은 재 귀 알고리즘 입 니 다.지정 한 피 드 점 부터 각 방향 으로 검색 하여 픽 셀 별로 처리 합 니 다.경계 에 부 딪 힐 때 까지 각종 피 드 충전 알고리즘 은 색상 과 경 계 를 처리 하 는 방식 만 다 릅 니 다.피 드 충전 알고리즘 을 소개 하기 전에 먼저 두 가지 개념 을 소개 하 는데 그것 이 바로'4-연결 알고리즘'과'8-연결 알고리즘'이다.검색 이 라면 검색 의 방향 과 관련 된 문제 이 므 로 지역 내 임 의 한 점 에서 출발 하여 위,아래,왼쪽,오른쪽 네 방향 으로 만 지역 내 임 의 픽 셀 을 검색 하면 이런 방법 으로 채 워 진 구역 을 4 연통 역 이 라 고 하 는데 이런 충전 방법 을'4-연통 알고리즘'이 라 고 한다.만약 에 구역 내 임 의 한 점 에서 출발 하여 위,아래,왼쪽,오른쪽,위,왼쪽,아래,오른쪽 위 와 오른쪽 아래 모두 8 개 방향 으로 구역 내의 임 의 픽 셀 에 도착 하면 이런 방법 으로 채 우 는 구역 을 8 연 통 역 이 라 고 하 는데 이런 채 우 는 방법 을'8-연결 알고리즘'이 라 고 한다.그림 1(a)에서 보 듯 이 중심 에 있 는 파란색 점 이 현재 처리 하 는 점 이 라 고 가정 하고'4-연결 알고리즘'이 라면 주변 파란색 표 지 를 처리 하 는 네 가지 점 만 검색 하고'8-연결 알고리즘'이 라면 위,아래,왼쪽,오른쪽 네 개의 파란색 표 지 를 처리 하 는 점 을 제외 하고 네 개의 빨간색 표 지 를 처리 하 는 점 도 검색 한다.두 가지 검색 알고리즘 의 충전 효 과 는 그림 1(b)과 그림 1(c)과 같다.모두 노란색 점 에서 채 우 면'4-연결 알고리즘'은 그림 1(b)과 같이 왼쪽 아래 만 채 우 는 구역 을 검색 하고'8-연결 알고리즘'은 그림 1(c)과 같이 왼쪽 아래 와 오른쪽 상단 의 구역 을 채 웠 다.

그림(1)"4-연결"과"8-연결"충전 효과
그림 1 의 충전 효과 만으로'8-연결 알고리즘'이'4-연결 알고리즘'보다 낫다 고 생각 할 수 는 없고 응용 환경 과 실제 수요 에 따라 연결 검색 방식 을 선택해 야 한다.많은 상황 에서'4-연결 알고리즘'만 정확 한 결 과 를 얻 을 수 있다.
1.1 주입 충전 알고리즘(Flood Fill Algorithm)
 주입 충전 알고리즘 은 지역 의 경 계 를 특별히 강조 하지 않 습 니 다.지정 한 위치 부터 모든 연결 영역 에서 지정 한 색상 의 점 을 다른 색상 으로 바 꾸 어 충전 효 과 를 실현 합 니 다.충전 알고리즘 을 주입 하면 색상 교체 와 같은 기능 을 실현 할 수 있 는데 이것 은 이미지 처리 소프트웨어 에서 광범 위 하 게 응용 되 었 다.주입 충전 알고리즘 의 실현 은 매우 간단 하 다.핵심 은 귀속 과 검색 이다.다음은 주입 충전 알고리즘 의 실현 이다.

 void FloodSeedFill(int x, int y, int old_color, int new_color)
{
 if(GetPixelColor(x, y) == old_color)
 {
 SetPixelColor(x, y, new_color);
 for(int i = 0; i < COUNT_OF(direction_8); i++)
 {
 FloodSeedFill(x + direction_8[i].x_offset,
  y + direction_8[i].y_offset, old_color, new_color);
 }
 }
}
 for 순환 은 8 개의 연결 방향 으로 재 귀 검색 을 실 현 했 습 니 다.비밀 은 direction 에 있 습 니 다.8 의 정의:

 typedef struct tagDIRECTION
 {
 int x_offset;
 int y_offset;
 }DIRECTION;
DIRECTION direction_8[] = { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} };
이것 은 검색 클래스 알고리즘 에서 자주 사용 하 는 기술 입 니 다.너무 많은 설명 을 할 필요 가 없습니다.사실은 다음 direction 로 바 꾸 기만 하면 됩 니 다.4 의 정 의 는 알고리즘 을 4 개의 연결 방향 충전 알고리즘 으로 바 꿀 수 있 습 니 다.
80 DIRECTION direction_4[] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
그림 2 는 본 알고리즘 을 응용 하여 실 현 된'4-연결'과'8-연결'충전 효과 이다.

그림(2)주입 충전 알고리즘 구현
1.2 경계 채 우기 알고리즘(경계 채 우기 알고리즘)
 경계 충전 알고리즘 과 주입 충전 알고리즘 의 본질은 똑 같 습 니 다.모두 재 귀 와 검색 입 니 다.차이 점 은 경계 에 대한 확인,즉 재 귀 의 종료 조건 이 다 릅 니 다.주입 충전 알고리즘 은 경계 개념 이 없고 연결 영역 에서 지정 한 색상 만 교체 할 뿐 경계 충전 알고리즘 은 경계 가 존재 하 는 것 을 강조 합 니 다.경계 안의 점 이 라면 어떤 색 이 든 지 지정 한 색 으로 교체 합 니 다.경계 충전 알고리즘 은 응용 에 있어 서도 매우 광범 위 하 다.그림 그리 기 소프트웨어 의'페인트 통'기능 은 바로 경계 충전 알고리즘 의 예 이다.다음은 경계 충전 알고리즘 의 실현 입 니 다.

 void BoundarySeedFill(int x, int y, int new_color, int boundary_color)
{
 int curColor = GetPixelColor(x, y);
 if( (curColor != boundary_color)
 && (curColor != new_color) )
 {
 SetPixelColor(x, y, new_color);
 for(int i = 0; i < COUNT_OF(direction_8); i++)
 {
 BoundarySeedFill(x + direction_8[i].x_offset,
  y + direction_8[i].y_offset, new_color, boundary_color);
 }
 }
}
direction 에 대하 여8 의 설명 은 지난 절 을 참고 하 십시오.그림 3 은 본 알고리즘 을 응용 하여 실 현 된'4-연결'과'8-연결'충전 효과 입 니 다(그 중에서 색상 값 이 1 인 점 은 지정 한 경계 입 니 다).

그림(3)경계 충전 알고리즘 구현
이상 은 본 고의 모든 내용 입 니 다.본 고의 내용 이 여러분 의 학습 이나 업무 에 대해 어느 정도 참고 학습 가 치 를 가지 기 를 바 랍 니 다.궁금 한 점 이 있 으 시 면 댓 글 을 남 겨 주 셔 서 저희 에 대한 지지 에 감 사 드 립 니 다.

좋은 웹페이지 즐겨찾기