StackOverflowError с определенным алгоритмом для окраски замкнутой фигуры - PullRequest
Новая
       5

StackOverflowError с определенным алгоритмом для окраски замкнутой фигуры

1 голос
/ 01 марта 2011

Мое назначение - реализовать алгоритм для окраски замкнутой фигуры, начиная с заданной координаты (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);
    }
}

Класс Robot 'getPixelColor - единственный способ, которым я нашел, чтобы получить цвет данного пикселя (насколько я знаю, другой будет getRGB, но он работает только на объектах Image). Насколько я понимаю, это должно сработать, поскольку внешние линии фигуры определенно черные, а начальные значения 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)

Учитель сказал нам, что это потребляет память, однако это должен быть рабочий алгоритм, поэтому я, очевидно, что-то делаю не так. Любая помощь будет очень ценной, спасибо.

Ответы [ 3 ]

0 голосов
/ 01 марта 2011

Вы можете попытаться увеличить размер стека: Как увеличить размер стека Java?

Возможно, у вас ошибка в алгоритме или слишком большая фигура. Что поможет, если вы «нарисуете» свой алгоритм на листе миллиметровки. Таким образом, вы можете проверить свой алгоритм.

0 голосов
/ 01 марта 2011

Проблема с реализацией этого как рекурсивного алгоритма состоит в том, что он имеет (для больших изображений) очень высокую глубину рекурсии.

В Java (и в большинстве других императивных языков программирования тоже) максимальная глубина рекурсии ограничена объемом стекового пространства для каждого потока, так как он должен сохранять кадр стека для каждого вызова метода.

Вы можете сначала попробовать изображения меньшего размера и увеличить размер стека с помощью параметра -xss.

Редактировать: Как отметил Марк, робот не будет получать пиксели до тех пор, пока ваш рисунок не будет завершен, поскольку зачастую ваш рисунок имеет двойную буферизацию (т.е. механизм Swing позволяет вам сначала рисовать на изображении, а затем рисует полностью изображение на экран).

Кроме того, вы не выполняете преобразование координат устройства (экрана) и пользователя (компонента) для поиска.

Вы писали:

Класс Robot 'getPixelColor - единственный способ, которым я нашел, чтобы получить цвет данного пикселя (насколько я знаю, другой будет getRGB, но он работает только на объектах Image).

Итак, почему бы вам не использовать объект 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);
}
0 голосов
/ 01 марта 2011

Я предполагаю, что вы возвращаетесь к ранее посещенным пикселям. Пиксель, который вы только что нарисовали, вероятно, не будет виден robot до тех пор, пока вы не вернетесь из цвета, поэтому он не будет отображаться красным от предыдущей картины.

У вас есть ссылка на java.awt.Shape? Намного проще, чем использовать робота, было бы использовать Shape.contains(Point), чтобы увидеть, находится ли он в форме, которую вы должны нарисовать.

Базовый алгоритм в любом случае: путешествие в глубину . Чтобы выполнить 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));
    //...
}

Теперь это может привести к очень глубокому поиску. Вместо этого вы можете рассмотреть возможность использования нерекурсивного путешествия в ширину . См. Статью Википедии о заливке Наводнения .

...