알고리즘, 홍수 채우기 (깊이 우선 검색)

Java로 작업하고 있습니다.
"페인트 캔"도구가 Flood Fill 알고리즘을 사용하는 페인트 프로그램을 개발하고 있지만 너무 비쌉니다.알고리즘, 홍수 채우기 (깊이 우선 검색)

이

private int[] dx = { -1, 0, 1, 0 }; 
private int[] dy = { 0, 1, 0, -1 }; 

public void floodFill(int x, int y, Color target_color, Color replacement_color) { 
    Stack<Integer[]> stack = new Stack<Integer[]>(); 
    if (imageBuffer.getRGB(x, y) == replacement_color.getRGB()) 
     return; 
    stack.push(new Integer[] { x, y }); 
    while (!stack.isEmpty()) { 
     Integer[] aux = stack.peek(); 
     imageBuffer.setRGB(aux[0], aux[1], replacement_color.getRGB()); 
     stack.pop(); 
     for (int i = 0; i < 4; i++) { 
      if (imageBuffer.getRGB(aux[0] + dx[i], aux[1] + dy[i]) == target_color.getRGB()) 
       stack.push(new Integer[] { aux[0] + dx[i], aux[1] + dy[i] }); 
     } 

    } 
}

누군가가 나에게이보다 효율적으로 도울 수있다 : 여기

코드인가?

(1020x700 픽셀 이미지의 경우) 약 1200ms가 실행됩니다.

출처

2011-11-03 mastergoo

나는 중요한 점은 더 나은 알고리즘이 필요하다고 생각합니다. http://en.wikipedia.org/wiki/Flood_fill은 좋은 자료입니다. 당신이 만들 수있는 몇 가지 마이크로 최적화가 있습니다 (예를 들어,'replacement_color.getRGB()'가 매번 평가됩니다,'target_color.getRGB()'처럼) 그러나 나는 이것이 큰 차이를 만들 것이라고 상상하지 못합니다. –

대기열 알고리즘을 사용하는 기본적인 아이디어는 here (+ 예)입니다.

아마도 다른 최적화 및 구현을 찾을 수 있지만이 중 하나는 Queue-Linear Flood Fill입니다. 너는 너 자신 일을해야한다.

출처

2011-11-03 13:25:42 hovanessyan

스택을 ArrayDeque로 대체하는 것이 쉽고 빠른 (아마도 작은) 개선이 될 것입니다.

이렇게하면 초기 용량을 지정하고 코드를 최신 상태로 유지할 수 있습니다. floodFill 영역에 많은 픽셀이 포함되어 있으면 Stack을 Underlpinning하는 Vector를 여러 번 확장해야합니다. 이것은 낭비입니다. 그러나 값 비싼 것은 아닙니다.

출처

2011-11-03 13:34:46 Ivan

약 1 년 전 꽤 오래 floodfill 알고리즘을 구현하려고했습니다. 나는 처음에는 내 자신의 솔루션을 시도하고, 그들이 충분히 performant되지 않았을 때, 나는 인터넷에 가서 this implementation을 발견.

QuickFill (실제 알고리즘은 페이지 중간 정도에서 시작됩니다) 알고리즘이 잘 작동했습니다. 내 droid 이정표의 스크린 (480x854)을 0.5 초 안에 채울 것입니다. 새로운 하드웨어 (또는 심지어 데스크탑 하드웨어)를 사용하면 아마도 그보다 더 빨리 작동 할 것입니다. 물론 자바로 이식해야하지만 너무 어렵지 않아야합니다. 특히 할 수 있다면 더욱 그렇습니다!

출처

2011-11-03 13:36:36

저는 많은 메모리 할당이 이루어지고 있다고 말하고 싶습니다. 모든 픽셀에 대해 새 Integer[]을 할당합니다. 나는 x과 y을 처리하기 위해 적어도 두 개의 스택 프리미티브 (예 : trove4j에있는 배열 목록)를 처리하거나 적어도 Integer[]을 int[]으로 바꿉니다.

충분하지 않다면 scanline 알고리즘이 도움이 될 것입니다.

출처

2011-11-03 13:45:37 Vlad

알고리즘, 홍수 채우기 (깊이 우선 검색)

답변

관련 문제