Android 다각형 영역 스캐닝 라인 피 드 충전 알고리즘 예제

1.3 스캐너 피 드 충전 알고리즘
1.1 과 1.2 절 에 소 개 된 두 가지 피 드 충전 알고리즘 의 장점 은 매우 간단 하 다 는 것 이다.단점 은 재 귀 알고리즘 을 사용 한 것 이다.이것 은 대량의 스 택 공간 으로 인접 한 점 을 저장 해 야 할 뿐만 아니 라 효율 도 높 지 않다.알고리즘 중의 재 귀적 호출 을 줄 이 고 스 택 공간의 사용 을 절약 하기 위해 사람들 은 많은 개선 알고리즘 을 제 시 했 는데 그 중 하 나 는 스 캔 라인 피 드 충전 알고리즘 이다.스캐닝 라인 피 드 충전 알고리즘 은'4-연결'과'8-연결'의 인접 점 을 재 귀적 으로 처리 하지 않 고 수평 스캐닝 라인 을 따라 픽 셀 세그먼트 를 채 우 고'4-연결'과'8-연결'의 인접 점 을 한 단락 씩 처리 합 니 다.이러한 알고리즘 처리 과정 에서 모든 수평 픽 셀 세그먼트 의 시작 점 위 치 를 특수 한 스 택 에 눌 러 야 합 니 다.재 귀 알고리즘 처럼 현재 위치 주위 에 처리 되 지 않 은 모든 인접 점 을 스 택 에 눌 러 서 스 택 공간 을 절약 할 필요 가 없습니다.스 캔 라인 충전 알고리즘 은 재 귀 를 피하 고 효율 을 높이 는 사상 일 뿐 앞에서 언급 한 주입 충전 알고리즘 과 경계 충전 알고리즘 은 모두 스 캔 라인 충전 알고리즘 으로 개선 할 수 있 습 니 다.다음은 경계 충전 알고리즘 을 결합 한 스 캔 라인 피 드 충전 알고리즘 을 소개 합 니 다.
스캐닝 라인 피 드 충전 알고리즘 의 기본 과정 은 다음 과 같다.주어진 피 드 점(x,y)을 지정 할 때 먼저 왼쪽 과 오른쪽 두 방향 으로 피 드 점 이 있 는 스캐닝 라인 이 주어진 구역 에 있 는 한 구간 을 채 우 고 이 구간 의 범위[xLeft,xRight]를 기록 한 다음 에 이 구간 과 연 결 된 상하 두 스캐닝 라인 이 주어진 구역 내 에 있 는 구간 을 확인한다.순서대로 저장 합 니 다.충전 이 끝 날 때 까지 이 과정 을 반복 합 니 다.
스캐닝 라인 피 드 충전 알고리즘 은 다음 네 가지 절차 로 이 루어 집 니 다.
(1)빈 스 택 을 초기 화하 여 피 드 점(x,y)을 스 택 에 저장 합 니 다.
(2)스 택 이 비어 있 는 지 판단 하고 스 택 이 비어 있 으 면 알고리즘 을 끝 냅 니 다.그렇지 않 으 면 스 택 꼭대기 요 소 를 현재 스 캔 라인 의 피 드 점(x,y)으로 꺼 내 고 y 는 현재 스 캔 라인 입 니 다.
(3)피 드 점(x,y)에서 출발 하여 현재 스캐닝 라인 을 따라 왼쪽,오른쪽 두 방향 으로 경계 까지 채 웁 니 다.구간 의 왼쪽,오른쪽 점 좌 표를 각각 xLeft 와 xRight 로 표시 합 니 다.
(4)현재 스 캔 라인 과 인접 한 y-1 과 y+1 두 개의 스 캔 라인 이 구간[xLeft,xRight]에 있 는 픽 셀 을 각각 검사 하고 xLeft 부터 xRight 방향 으로 검색 합 니 다.경계 가 아 닌 채 워 지지 않 은 픽 셀 점 이 있 으 면 인접 한 픽 셀 점 중 가장 오른쪽 에 있 는 하 나 를 찾 아 피 드 점 으로 스 택 에 누 른 다음(2)단계 로 돌아 갑 니 다.
이 알고리즘 에서 가장 중요 한 것 은 제(4)단계 입 니 다.현재 스캐닝 라인 의 이전 스캐닝 라인 과 다음 스캐닝 라인 에서 새로운 피 드 점 을 찾 는 것 입 니 다.여기 서 이해 하기 어 려 운 점 은 왜 새로운 스캐닝 라인 구간[xLeft,xRight]의 픽 셀 만 검사 하 는 것 입 니까?만약 새 스캐닝 선의 실제 범위 가 이 구간 보다 크다 면 어떻게 처리 합 니까?나 는 컴퓨터 그래 픽 의 책 과 논문 을 많이 찾 아 보 았 는데 이것 에 대해 특별한 설명 을 한 적 이 없 는 것 같 아서 많은 사람들 이 이 과정 을 공부 할 때 이에 대해 흔 들 리 지 않 는 다 는 의혹 을 가지 게 되 었 다.'사람 을 망 치 는'꾸준 한 사상 에 근거 하여 본 고 는 수 다스 럽 게 설명 하고 여러분 의 의혹 을 풀 수 있 기 를 바 랍 니 다.
만약 에 새로운 스캐닝 라인 의 실제 점 구간 이 현재 스캐닝 라인 의[xLeft,xRight]구간 보다 크 고 연속 적 인 상황 에서 알고리즘 의 제(3)단 계 는 이런 상황 을 처리 했다.그림(4)에서 보 듯 이:
 
그림(4)새 스캐닝 라인 구간 이 커지 고 연속 적 인 상황
현재 처 리 된 스캐닝 라인 이 노란색 점 이 있 는 일곱 번 째 줄 이 라 고 가정 하면 세 번 째 처 리 를 거 쳐 한 구간[6,10]을 얻 을 수 있다.그리고 네 번 째 작업 은 인접 한 여섯 번 째 줄 과 여덟 번 째 줄 두 개의 스캐닝 라인 의 여섯 번 째 열 에서 오른쪽으로 검색 하여 빨간색 의 두 점 이 각각 여섯 번 째 줄 과 여덟 번 째 줄 의 피 드 점 임 을 확인 하고 순서대로(6,10)과(8,10)두 피 드 를 스 택 에 입력 합 니 다.다음 순환 은(8,10)이 피 드 점 을 처리 합 니 다.알고리즘 3 단계 설명 에 따라(8,10)부터 왼쪽 과 오른쪽으로 채 웁 니 다.중간 에 경계 점 이 없 기 때문에 경 계 를 만 날 때 까지 채 웁 니 다.그래서 8 줄 의 실제 구역 은 7 줄 의 구역 간[6,10]보다 크 지만 정확 한 채 워 집 니 다.
 새 스캐닝 라인 의 실제 점 구간 이 현재 스캐닝 라인 의[xLeft,xRight]구간 보다 크 고 중간 에 경계 점 이 있 는 경우 알고리즘 은 어떻게 처리 합 니까?알고리즘 설명 에 서 는 이러한 상황 에 대한 처리 방법 이 명확 하지 않 지만 4 단계 에 서 는 상하 인접 스캐닝 라인 의 피 드 점 을 확정 하 는 방법 과 오른쪽 에서 점 을 취 하 는 원칙 은 실제 적 으로 인접 스캐닝 라인 에서 장애 점 을 돌아 가 는 방법 을 내포 하고 있다.다음은 그림(5)을 예 로 들 어 설명 한다.
 
그림(5)새 스캐닝 라인 구간 이 커지 고 연속 되 지 않 는 상황
알고리즘 3 단계 에서 5 행 을 처리 한 후 구간[7,9]을 확 정 했 습 니 다.인접 한 4 행 은 실제 범 위 는 구간[7,9]보다 크 지만(4,6)이라는 경계 점 에 의 해 방해 되 어 피 드 점(4,9)을 확정 한 후 왼쪽으로 채 우 면 오른쪽 7 열 에서 10 열 사이 의 구역 만 채 울 수 있 고 왼쪽 3 열 에서 5 열 사이 의 구역 은 채 워 지지 않 았 습 니 다.다섯 번 째 줄 의 인접 줄 로 서 첫 번 째 네 번 째 줄 에 대한 스 캔 은 오른쪽 원칙 에 따라(4,9)하나의 피 드 점 만 확정 되 었 다.그러나 세 번 째 줄 을 처리 한 후 네 번 째 줄 의 왼쪽 부분 은 세 번 째 줄 아래 의 인접 줄 로 다시 스 캔 할 기 회 를 얻 었 다.세 번 째 줄 의 구간 은[3,9]로 6 열 이라는 장애물 을 왼쪽으로 넘 었 고,두 번 째 줄 을 스 캔 할 때 3 열 부터 오른쪽으로 찾 으 면 씨앗 점(4,5)을 확인 할 수 있다.이렇게 네 번 째 줄 에 두 개의 씨앗 점 이 있 으 면 완전히 채 울 수 있다.
 이 를 통 해 알 수 있 듯 이 장애 점 이 있 는 줄 에 대해 인접 한 관 계 를 통 해 장애 점 을 뛰 어 넘 을 수 있 고 여러 번 스 캔 을 통 해 완전한 충전 을 얻 을 수 있 으 며 알고리즘 은 이러한 상황 에 대한 처 리 를 포함 하고 있다.이 절 에서 정리 한 네 가지 절차 에 따라 스캐닝 라인 피 드 충전 알고리즘 은 다음 과 같다.

void SearchLineNewSeed(std::stack<Point>& stk, int xLeft, int xRight,
 int y, int new_color, int boundary_color)
 {
 int xt = xLeft;
 bool findNewSeed = false; 
 while(xt <= xRight)
 {
 findNewSeed = false;

 while(IsPixelValid(xt, y, new_color, boundary_color) && (xt < xRight))
 {
 findNewSeed = true;
 xt++;
 }
 if(findNewSeed)
 {
 if(IsPixelValid(xt, y, new_color, boundary_color) && (xt == xRight))

 stk.push(Point(xt, y));
 else
 stk.push(Point(xt - 1, y));
 }
 
 /*          （             ）*/
 int xspan = SkipInvalidInLine(xt, y, xRight, new_color, boundary_color);
 xt += (xspan == 0) ? 1 : xspan;
 /*      ,   while(x<=xright)  */
 }
}

FillLine Right()와 FillLine Left()두 함 수 는 피 드 점 에서 각각 오른쪽 과 왼쪽으로 색 을 채 우 고 경계 점 을 만 날 때 까지 채 워 진 점 의 개 수 를 되 돌려 주 는 것 입 니 다.이 두 함수 가 충전 점 의 개 수 를 되 돌려 주 는 것 은 현재 피 드 점 이 있 는 스캐닝 라인 의 구간[xLeft,xRight]을 정확하게 조정 하기 위해 서 입 니 다.
SearchLine NewSeed()함수 완성 알고리즘 4 단계 에서 설명 한 작업 은 새 스캐닝 라인 에서 피 드 점 을 찾 고 피 드 점 을 스 택 에 넣 는 것 입 니 다.새 스캐닝 라인 의 구간 은 xLeft 와 xRight 매개 변수 로 확 정 됩 니 다.

void SearchLineNewSeed(std::stack<Point>& stk, int xLeft, int xRight,
 int y, int new_color, int boundary_color)
 {
 int xt = xLeft;
 bool findNewSeed = false; 
 while(xt <= xRight)
 {
 findNewSeed = false;

 while(IsPixelValid(xt, y, new_color, boundary_color) && (xt < xRight))
 {
 findNewSeed = true;
 xt++;
 }
 if(findNewSeed)
 {
 if(IsPixelValid(xt, y, new_color, boundary_color) && (xt == xRight))

 stk.push(Point(xt, y));
 else
 stk.push(Point(xt - 1, y));
 }
 
 /*          （             ）*/
 int xspan = SkipInvalidInLine(xt, y, xRight, new_color, boundary_color);
 xt += (xspan == 0) ? 1 : xspan;
 /*      ,   while(x<=xright)  */
 }
}

가장 바깥쪽 의 while 순환 은 구간[xLeft,xRight]오른쪽 끝 이 장애 점 에 의 해 여러 단락 으로 구 분 된 상황 을 정확하게 처리 할 수 있 도록 하기 위해 서 입 니 다.바깥쪽 while 순환 을 통 해 각 단락 에 하나의 피 드 점 을 찾 을 수 있 도록 확보 할 수 있 습 니 다(장애 점 이 구간 왼쪽 끝 에 있 는 경우 그림(5)에서 보 여 준 사례 의 해석 은 알고리즘 에 포함 되 어 있 습 니 다).내부 의 while 순환 은 모든 단락 의 가장 오른쪽 끝 에 있 는 충전 점 을 피 드 점 으로 찾기 위해 서 입 니 다.SkipInvalidInLine()함수 의 역할 은 구간 내의 장애 점 을 뛰 어 넘 고 다음 구간 의 시작 위 치 를 확인 하 는 것 입 니 다.순환 안의 마지막 줄 코드 는 좀 이상 하 다.사실은 작은'계략'을 사용 하여 진정한 경계 점 을 만 났 을 때 순환 이 정확하게 빠 질 수 있 도록 확보 했다.이것 은 칭찬 할 만 한 방법 이 아니 라 이런 소프트웨어 통 제 를 실현 하 는 데 더 좋 은 방법 이 있다.본 고 는 코드 를 짧게 하고 독자 로 하여 금 알고리즘 처리 논리 에 집중 하 게 하 는 것 이지 복잡 하고 어 려 운 순환 통제 조건 에 집중 하 게 하 는 것 이 아니다.
알고리즘 의 실현 은 사실 ScanLine Seed Fill()과 SearchLine NewSeed()두 함수 에서 신비 한 스캐닝 라인 피 드 충전 알고리즘 도 복잡 하지 않 습 니 다.그 렇 죠?이로써 피 드 충전 알고리즘 의 몇 가지 흔 한 알고리즘 이 모두 소개 되 었 습 니 다.그 다음 에 벡터 그래 픽 영역 충전 에 적합 한 충전 알고리즘 두 가 지 를 소개 하 겠 습 니 다.각각 스캐닝 라인 알고리즘 과 사 이 드 로고 충전 알고리즘 입 니 다.벡터 그래 픽 에 적합 한 스캐닝 라인 충전 알고리즘 은 가끔'질서 있 는 사 이 드 시트 법'이 라 고도 부 르 는데 스캐닝 라인 피 드 충전 알고리즘 과 차이 가 있 습 니 다.