홍수 채우기의 경계 사각형을 빨리 얻는 방법

Question

이미지 영역에 범람 채우기를 수행해야합니다. 그러나 실제로 결과 이미지가 필요하지는 않습니다. 홍수 채우기에 의해 변경 될 모든 픽셀을 포함하는 가장 작은 사각형을 알아야합니다.

전체 홍수 채우기보다이 사각형을 더 저렴하게 계산할 수있는 홍수 채우기 알고리즘의 변형이 있습니까?

예 입출력 (에만 적색 사각형이 필요)

Sample input image. The red dot is the start pixel. The area to be filled is the cyan Z-tetromino that contains the dot http://www.finnw.me.uk/ffinput.pngSample output. Only the position/width/height of the red rectangle is significant http://www.finnw.me.uk/ffoutput.png

---

편집 : 섬과 예 2 :
Example input with islands http://www.finnw.me.uk/ffinput2.png Example output http://www.finnw.me.uk/ffoutput2.png

예 # 3 :
Example of false island http://www.finnw.me.uk/ffinput3.png

---

편집

죄송합니다, 이미지는 하드 디스크 고장에 분실되었다. 처음 게시했을 때 이미지를 호스팅하지 않아서 내 서버에 보관했습니다.

Answer 1

기본적으로 가장 큰 X, 가장 큰 Y, 가장 작은 X 및 가장 작은 Y를 결정해야합니다.

당신은 바로 + 아래 가능한 한 색상의 내부까지 이동하여이 작업을 수행 할 수 있습니다

실제 가장자리의 오른쪽 하단 모서리를 찾아보십시오.

오른쪽 + 아래로 이동할 수 없을 때 섬의 구석에 갇혀 있지 않은지 확인해야합니다. 이것을 확인하려면 더 오른쪽 + 아래로 갈 기회를 찾고 전체 가장자리를 따라 가야합니다. 실제로 가장 큰 문제가있는 경우에 대비하여 (가장 큰 X, 가장 큰 Y, 가장 작은 X, 작은 Y)를 추적 할 수 있습니다.

섬이 실제로있는 경우 더 오른쪽 아래로 갈 수있는 가장자리가있는 곳을 결국 찾습니다.

더 오른쪽에서 아래로 이동할 기회가없고 출발점에 도달하면 실제 가장자리가 생깁니다. 그리고 당신은 (가장 큰 X, 가장 큰 Y, 가장 작은 X, 가장 작은 Y)를 계산했습니다.

Answer 2

가능한 한 가지 방법은 출발점에서 가능한 한 멀리 (왼쪽, 위, 아래로 오른쪽) 이동 한 다음 시계 방향 또는 시계 반대 방향으로 가장자리를 따라 이동하여 첫 번째 가장자리 지점 . 모서리를 따라갈 때 min (X, Y) 및 max (X, Y)를 추적하십시오.

채우기에 이상한 모양이 아니면 않는 한 더 적은 픽셀을 보도록해야합니다.