다각형 채우기 알고리즘

다각형은 다음 그림과 같이 정렬 된 정점 목록입니다. 폴리곤을 특정 색상으로 채우려면 폴리곤 경계에있는 픽셀과 폴리곤 내부에있는 픽셀을 결정해야합니다. 이 장에서는 다양한 기술을 사용하여 다각형을 채우는 방법을 살펴 봅니다.

스캔 라인 알고리즘

이 알고리즘은 스캔 라인을 다각형 가장자리와 교차하여 작동하고 교차 쌍 사이의 다각형을 채 웁니다. 다음 단계는이 알고리즘의 작동 방식을 보여줍니다.

Step 1 − 주어진 다각형에서 Ymin과 Ymax를 찾으십시오.

Step 2− ScanLine은 Ymin에서 Ymax까지 다각형의 각 가장자리와 교차합니다. 다각형의 각 교차점에 이름을 지정합니다. 위에 표시된 그림에 따라 p0, p1, p2, p3으로 이름이 지정됩니다.

Step 3 − X 좌표의 오름차순으로 교차점을 정렬합니다. 즉 (p0, p1), (p1, p2) 및 (p2, p3).

Step 4 − 다각형 내부에있는 모든 좌표 쌍을 채우고 대체 쌍을 무시합니다.

채우기 알고리즘

때때로 우리는 영역과 경계를 다른 색상으로 채우려는 물체를 발견합니다. 경계 채우기 알고리즘에서와 같이 특정 경계 색상을 검색하는 대신 지정된 내부 색상으로 이러한 개체를 칠할 수 있습니다.

개체의 경계에 의존하는 대신 채우기 색상에 의존합니다. 즉, 개체의 내부 색상을 채우기 색상으로 대체합니다. 원래 내부 색상의 픽셀이 더 이상 존재하지 않으면 알고리즘이 완료됩니다.

다시 한 번이 알고리즘은 픽셀을 채우는 Four-connect 또는 8-connect 방법에 의존합니다. 그러나 경계 색상을 찾는 대신 내부의 일부인 인접한 모든 픽셀을 찾습니다.

경계 채우기 알고리즘

경계 채우기 알고리즘은 이름으로 작동합니다. 이 알고리즘은 개체 내부의 점을 선택하고 개체의 경계에 도달 할 때까지 채우기 시작합니다. 이 알고리즘이 작동하려면 경계의 색상과 채울 색상이 달라야합니다.

이 알고리즘에서는 경계의 색상이 전체 개체에 대해 동일하다고 가정합니다. 경계 채우기 알고리즘은 4 개 연결 픽셀 또는 8 개 연결 픽셀로 구현할 수 있습니다.

4- 연결 다각형

이 기술에서는 그림과 같이 4 개의 연결된 픽셀이 사용됩니다. 현재 픽셀의 위, 아래, 오른쪽 및 왼쪽에 픽셀을 배치하고이 프로세스는 다른 색상의 경계를 찾을 때까지 계속됩니다.

연산

Step 1 − 시드 포인트 (seedx, seedy), fcolor 및 dcol의 값을 초기화합니다.

Step 2 − 다각형의 경계 값을 정의합니다.

Step 3 − 현재 시드 포인트가 기본 색상인지 확인한 다음 경계 픽셀에 도달 할 때까지 4 단계와 5 단계를 반복합니다.

If getpixel(x, y) = dcol then repeat step 4 and 5

Step 4 − 시드 포인트의 채우기 색상으로 기본 색상을 변경합니다.

setPixel(seedx, seedy, fcol)

Step 5 − 4 개의 인접 지점으로 절차를 반복적으로 따릅니다.

FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)

Step 6 − 종료

이 기술에 문제가 있습니다. 우리가 전체 지역을 채우려 고 시도한 아래와 같은 경우를 고려하십시오. 여기에서는 이미지가 부분적으로 만 채워집니다. 이러한 경우 4 연결 픽셀 기술을 사용할 수 없습니다.

8 개 연결 다각형

이 기술에서는 그림과 같이 8 개의 연결된 픽셀이 사용됩니다. 우리는 4- 연결 기술에서했던 것처럼 현재 픽셀의 위, 아래, 오른쪽 및 왼쪽에 픽셀을 배치합니다.

이 외에도 현재 픽셀의 전체 영역을 덮도록 픽셀을 대각선으로 배치합니다. 이 과정은 다른 색의 경계를 찾을 때까지 계속됩니다.

연산

Step 1 − 시드 포인트 (seedx, seedy), fcolor 및 dcol의 값을 초기화합니다.

Step 2 − 다각형의 경계 값을 정의합니다.

Step 3 − 현재 시드 포인트가 기본 색상인지 확인한 다음 경계 픽셀에 도달 할 때까지 4 단계와 5 단계를 반복합니다.

If getpixel(x,y) = dcol then repeat step 4 and 5

Step 4 − 시드 포인트의 채우기 색상으로 기본 색상을 변경합니다.

setPixel(seedx, seedy, fcol)

Step 5 − 4 개의 인접 지점으로 절차를 반복적으로 따르십시오.

FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx, seedy + 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy - 1, fcol, dcol)

Step 6 − 종료

4 연결 픽셀 기술은 8 연결 기술에서는 발생하지 않는 다음 그림과 같이 영역을 채우지 못했습니다.

내부-외부 테스트

이 방법은 다음과 같이 알려져 있습니다. counting number method. 개체를 채우는 동안 특정 지점이 개체 내부에 있는지 외부에 있는지 식별해야하는 경우가 많습니다. 특정 지점이 개체 내부에 있는지 외부에 있는지 식별 할 수있는 두 가지 방법이 있습니다.

  • 홀수 짝수 규칙
  • 0이 아닌 권선 수 규칙

홀수 짝수 규칙

이 기술에서는 모든 점 (x, y)에서 무한대까지 선을 따라 교차하는 가장자리를 계산합니다. 상호 작용의 수가 홀수이면 점 (x, y)는 내부 점입니다. 상호 작용의 수가 짝수이면 점 (x, y)는 외부 점입니다. 다음 예는이 개념을 설명합니다.

위 그림에서 (x, y) 지점에서 왼쪽의 상호 작용 지점 수가 5이고 오른쪽의 상호 작용 지점 수가 3 인 것을 알 수 있습니다. 양쪽 끝에서 상호 작용 지점의 수가 홀수이므로 점은 객체 내에서 고려됩니다.

0이 아닌 권선 번호 규칙

이 방법은 또한 주어진 포인트가 내부인지 아닌지를 테스트하기 위해 단순 다각형과 함께 사용됩니다. 핀과 고무 밴드의 도움으로 간단하게 이해할 수 있습니다. 다각형 가장자리 중 하나에 핀을 고정하고 고무 밴드를 묶은 다음 다각형 가장자리를 따라 고무 밴드를 늘립니다.

폴리곤의 모든 가장자리가 고무줄로 덮여 있으면 테스트 할 지점에 고정 된 핀을 확인합니다. 지점에서 바람이 하나 이상 발견되면 다각형 내에서 고려합니다. 그렇지 않으면 지점이 다각형 내부에 없다고 말할 수 있습니다.

또 다른 방법으로 다각형의 모든 가장자리에 방향을 제공합니다. 테스트 할 지점에서 X 방향의 가장 왼쪽을 향해 스캔 라인을 그립니다.

  • 위쪽으로 향하는 모든 가장자리에 값 1을 지정하고 방향 값으로 다른 모든 -1을 지정합니다.

  • 스캔 라인이 지나가는 가장자리 방향 값을 확인하고 합산하십시오.

  • 이 방향 값의 총합이 0이 아니면 테스트 할이 점은 interior point, 그렇지 않으면 exterior point.

  • 위의 그림에서 스캔 라인이 지나가는 방향 값을 합산하면 합계가 1 – 1 + 1 = 1입니다. 0이 아닙니다. 따라서 포인트는 내부 포인트라고합니다.