Java - ошибка StackOverflow в методе рекурсивного двумерного логического массива, который не должен возникать

Question

Я работаю над исполняемым Java-апплетом, который имеет функцию заливки, очень похожую на метод заливки в таких программах рисования, как Microsoft Paint.

Вот как работает мой метод заполнения:

1. Апплет получает цвет, на который пользователь нажал, используя .getRGB

2. Апплет создает двумерный логический массив всех пикселей в окне со значением "true", если этот пиксель имеет тот же цвет, что и цвет, по которому щелкнули, или "false", если нет. Смысл этого шага состоит в том, чтобы исключить метод .getRGB из рекурсивного метода для предотвращения этой ошибки.

3. Апплет рекурсивно ищет двумерный массив логических значений, на котором щелкнул пользователь, и записывает каждую смежную точку, которая является «истинной» в ArrayList. Затем метод изменяет каждую записанную точку на false и продолжает.

4. Апплет закрашивает каждую точку, сохраненную в ArrayList, в выбранный пользователем цвет.

Все вышеперечисленные шаги работают ОТЛИЧНО, если пользователь щелкает в пределах небольшой области, где их цвет изменился всего на несколько тысяч пикселей. Однако если пользователь выбирает большую область (например, около 360 000 / размер окна апплета), апплет переходит в рекурсивную стадию и затем выводит эту ошибку:

Exception in thread "AWT-EventQueue-1" java.lang.StackOverflowError
 at java.util.ArrayList.add(ArrayList.java:351)
 at paint.recursiveSearch(paint.java:185)
 at paint.recursiveSearch(paint.java:190)
 at paint.recursiveSearch(paint.java:190)
 at paint.recursiveSearch(paint.java:190)
 at paint.recursiveSearch(paint.java:190)
 at paint.recursiveSearch(paint.java:190)
 at paint.recursiveSearch(paint.java:190)  
 (continues for a few pages) 

Вот мой рекурсивный код:

public void recursiveSearch(boolean [][] list, Point p){
    if(isValid(p)){
        if(list[(int)p.y][(int)p.x]){
            fillPoints.add(p);
            list[(int)p.y][(int)p.x] = false;

            recursiveSearch(list, new Point(p.x-1,p.y));//Checks to the left
            recursiveSearch(list, new Point(p.x,p.y-1));//Checks above
            recursiveSearch(list, new Point(p.x+1,p.y));//Checks to the right
            recursiveSearch(list, new Point(p.x,p.y+1));//Checks below
            }
        }
    }

Можно ли как-то обойти такую ​​ошибку? Я знаю, что цикл никогда не будет продолжаться вечно, просто это может занять много времени.

Answer 1

Вам нужен поиск в ширину. У вас будет очередь «необработанных» пикселей. Сначала очередь состоит из одного пикселя, по которому щелкнул пользователь. Теперь, когда очередь не пуста, повторите следующий шаг: возьмите следующий пиксель из очереди, обработайте его (закрасьте до нужного вам цвета или любого другого), и для каждого смежного не посещенного пикселя того же цвета отметьте его как посещенный добавить в очередь. Если область состоит из 360 000 пикселей, она должна быть запущена не за время.

Answer 2

Это должно произойти для большого изображения. Вы не должны использовать рекурсию. Может быть, что-то вроде этого:

LinkedList<Point> frontier = new ...
frontier.add(starting_point);

while(frontier is not empty)
    point = frontier.removeLast();
    point.state = (point.color == the_color)
    if(point.state==true)
       // expand frontier
       for(neighbor : neighbor_points)
           if(neighbor.visited==false)
               frontier.add(neighbor)
               neighbor.visited=true;

Answer 3

Из моего быстрого взгляда. Я думаю, что вы путешествуете по районам много-много раз. Вам следует обновить метод, указав, в каком направлении не следует проверять вызов. Как это:

public void recursiveSearch(boolean [][] list, Point p, String directionFrom){
    if(isValid(p)){
        if(list[(int)p.y][(int)p.x]){
            fillPoints.add(p);
            list[(int)p.y][(int)p.x] = false;
            //Add a check for which direction it came from and dont go that way.
            if (string.equals(right)){     
                 recursiveSearch(list, new Point(p.x,p.y-1),down);//Checks above
                 recursiveSearch(list, new Point(p.x+1,p.y),left);//Checks to the right
                 recursiveSearch(list, new Point(p.x,p.y+1),right);//Checks below
            }else if(string.equals(left){
              //... and so on
            }
        }
    }
}

Answer 4

Рекурсирование было бы хорошей идеей, если вы хотите избежать проверки всех пикселей в окне. я бы предложил изменить цвет выбранного пикселя и рекурсивно проверить, есть ли смежные пиксели, которые тоже нужно изменить, и вернуться назад, если нет, и так далее. Таким образом, избегая проверки каждого пикселя в окне. (Представьте себе окно размером 800 x 800 пикселей, и вам необходимо заполнить область размером 4 × 4 пикселя. Проверка того, что каждый пиксель будет излишним.)

Answer 5

Ваш алгоритм имеет смысл на бумаге, но, как вы узнали, он плохо масштабируется.

Я сомневаюсь, что любая графическая программа будет использовать этот метод.

Answer 6

Если вы хотите обрабатывать изображения произвольного размера, вам придется переписать это не рекурсивным способом.Нет другого способа гарантировать, что ваш стек будет достаточно большим.

Answer 7

Основная проблема в том, что вы проверяете слишком много для каждого пикселя.Я бы посоветовал добавить в метод параметр «level», который изначально равен 0, но увеличивается при рекурсивном вызове.Затем добавьте начальный оператор печати, показывающий уровень текущего рекурсивного вызова.

Я думаю, вы будете удивлены, насколько глубоко вы закончите в своем коде!

Answer 8

Я вообще не понимаю, почему вы возвращаетесь.Было бы одно, если бы вы когда-нибудь изменили какие-либо точки в list обратно на true, но, очевидно, вы этого не сделаете.Так почему бы просто не повторить?

На самом деле, вы потенциально проверяете каждую точку много раз, при проверке каждой точки достаточно одного раза.

Еще одна мысль: если я не ошибаюсьваш алгоритм не добавит любых точек к вектору fillPoints, если только list[0, 0] == true.Это то поведение, которое вам нужно?

---

РЕДАКТИРОВАТЬ : Хорошо, теперь у меня есть лучшее представление о том, что вы пытаетесь сделать.Я предлагаю вам взглянуть на эту часть страницы Википедии по Flood Fill алгоритмам.

Answer 9

Вы можете увеличить пространство стека для вашего Java-процесса, например:

java -Xss10m MyProgram

даст 10 мегабайт в стек потока.Однако я бы посоветовал против этого и рассмотрел бы написание итеративной версии вашего алгоритма, особенно если число рекурсивных вызовов зависит от какого-либо поведения, управляемого пользователем.

РЕДАКТИРОВАТЬ: Для апплетов я недумаю, вы можете указать -X значения флага.