닫힌 모양을 채색하는 특정 알고리즘을 사용하는 StackOverflowError

Question

내 할당은 지정된 (x, y) 좌표에서 시작하여 닫힌 모양의 색상을 지정하고 모양의 테두리에 도달 할 때까지 재귀 호출을 통해 "확산"알고리즘을 구현하는 것입니다 . 내가 가지고 올 한 것을 지금까지이 :

private void color(int x, int y) { 
    g2d.draw(new Line2D.Double(x, y, x, y)); 
    if (!robot.getPixelColor(x - 1, y).equals(Color.BLACK) && 
      !robot.getPixelColor(x - 1, y).equals(Color.RED)) { 
     color(x - 1, y); 
    } else if (!robot.getPixelColor(x + 1, y).equals(Color.BLACK) && 
      !robot.getPixelColor(x - 1, y).equals(Color.RED)) { 
     color(x + 1, y); 
    } else if (!robot.getPixelColor(x, y - 1).equals(Color.BLACK) && 
      !robot.getPixelColor(x - 1, y).equals(Color.RED)) { 
     color(x, y - 1); 
    } else if (!robot.getPixelColor(x, y + 1).equals(Color.BLACK) && 
      !robot.getPixelColor(x - 1, y).equals(Color.RED)) { 
     color(x, y + 1); 
    } 
} 

로봇 클래스 'getPixelColor 내가 또 다른 getRGB를 것 알고까지 (주어진 픽셀의 색상을 얻을 수있는 유일한 방법입니다 만, 이미지 개체에서만 작동합니다). 모양의 바깥 라인이 확실히 검은 색으로 나의 이해에이 작동해야하고, 초기 x와 y 값은의 MouseListener에서 온, 그래서 그들은, 모양 내부에있는 그러나 나는 다음과 같은 오류 얻을 :

Exception in thread "AWT-EventQueue-0" java.lang.StackOverflowError 
    at sun.java2d.pipe.BufferedContext.validateContext(BufferedContext.java:110) 
    at sun.java2d.d3d.D3DRenderer.validateContextAA(D3DRenderer.java:42) 
    at sun.java2d.pipe.BufferedRenderPipe$AAParallelogramPipe.fillParallelogram(BufferedRenderPipe.java:445) 
    at sun.java2d.pipe.PixelToParallelogramConverter.drawGeneralLine(PixelToParallelogramConverter.java:264) 
    at sun.java2d.pipe.PixelToParallelogramConverter.draw(PixelToParallelogramConverter.java:121) 
    at sun.java2d.SunGraphics2D.draw(SunGraphics2D.java:2336) 
    at dline.DrawingSpace.color(DrawingSpace.java:87) 
    at dline.DrawingSpace.color(DrawingSpace.java:93) 
    at dline.DrawingSpace.color(DrawingSpace.java:90) 
    at dline.DrawingSpace.color(DrawingSpace.java:93) 
    at dline.DrawingSpace.color(DrawingSpace.java:90) 

을

(drawingSpace는 JPanel의 하위 클래스입니다.)

선생님은 메모리를 많이 사용한다고 말했지만, 작동하는 알고리즘으로되어있어 분명히 잘못되었습니다. 어떤 도움이 많이 appriciated 것입니다, 감사합니다.

Answer 1

이전에 방문한 픽셀로 되돌아 오는 것 같습니다. 방금 그린 픽셀은 색상에서 돌아올 때까지 robot에 표시되지 않으므로 이전 페인팅에서 빨간색으로 표시되지 않습니다.

java.awt.Shape에 대한 참조가 있으십니까? 로봇을 사용하는 것보다 훨씬 간단한 방법은 Shape.contains(Point)을 사용하여 그려야 할 모양인지 확인하는 것입니다.

기본 알고리즘은 depth-first traveral입니다. 가능한주기가있을 때 DFS를 수행하려면 이미 그린 픽셀을 기록 할 수 있습니다.

//java.awt.Point 
Set<Point> paintedPixels = new HashSet<Point>(); 
private void color(int x, int y) { 
    if (paintedPixels.contains(new Point(x, y))) { 
     //already painted 
     return; 
    } 
    paintedPixels.add(new Point(x, y)); 
    //... 
} 

이제는 매우 심한 검색이 발생할 수 있습니다. 대신 재귀가 아닌 breadth-first traveral을 사용하는 것이 좋습니다. Wikipedia article on Flood Fill을 참조하십시오.

Answer 2

당신은 스택의 크기 증가를 시도 할 수 있습니다

: How to increase the Java stack size?

아마 당신은 당신의 알고리즘에 버그가 있거나 모양이 너무 큽니다. 그래프 용지에 알고리즘을 '그리는'경우 도움이됩니다. 그렇게하면 알고리즘을 확인할 수 있습니다.

Answer 3

재귀 알고리즘으로 이것을 구현할 때 문제는 매우 큰 재귀 깊이가 (더 큰 이미지의 경우) 있다는 것입니다.

Java (및 대부분의 다른 명령형 프로그래밍 언어에서도 최대 재귀 깊이는 각 스레드에 대한 스택 공간의 양에 의해 제한됩니다. 각 메소드 호출에 대해 스택 프레임을 유지해야하기 때문입니다.

먼저 작은 이미지를 시도하고 -xss 매개 변수를 사용하여 스택 크기를 늘려보십시오.

---

편집 : 마크에 의해 지적 도면이 완료 될 때까지 자주 도면이 이중 버퍼링 (스윙 엔진은 사용자가 이미지를 먼저 칠 수 있습니다 즉이기 때문에, 로봇은, 모든 픽셀을받지 않습니다 및 그러면 전체 이미지가 화면에 그려집니다).

또한 조회를 위해 장치 (화면)와 사용자 (구성 요소) 좌표를 변환하지 않습니다.

당신이 쓴 :

The Robot class' getPixelColor is the only way I found to get the color of a given pixel (as far as I know another would be getRGB, but that only works on Image objects).

그래서, 당신은 왜 Image 객체를 사용하지 않는? 이미지를 그리는 동안 모양을 채운 다음 전체 이미지를 화면에 한 번에 그립니다.

---

그리고 당신은 재귀 호출 내부의 "이미 그려진"테스트를 전송하는 경우 방법은 훨씬 더 읽기 쉽게 만들 수 있습니다 :

private void color(int x, int y) { 
    // getPixel invokes something in the image - or replace it here. 
    Color org = getPixel(x,y); 
    if (org.equals(Color.BLACK)) { 
     // reached the border 
     return; 
    } 
    if (org.equals(Color.RED)) { 
     // already painted before 
     return; 
    } 
    g2d.draw(new Line2D.Double(x, y, x, y)); 
    color(x-1, y); 
    color(x+1, y); 
    color(x, y-1); 
    color(x, y-1); 
}