时间戳

首页 > 解决方案 > 某些文件上的堆栈溢出 - 查找精灵的位置

java - 某些文件上的堆栈溢出 - 查找精灵的位置

问题描述

首先，对不起我的英语不好，尤其是编程单词，英语不是我的第一语言。所以，我编写了一个软件，可以检测图像上的所有连续精灵并列出它们的调色板。该软件的完整解释在这里：https ://www.vg-resource.com/thread-33373.html

它工作正常，但是，如果精灵至少有 4300 像素，则会引发 stackoverflow 异常。

为了找到每个精灵的边界，首先我在表格中找到不是背景颜色的第一个像素。然后，我开始我的递归方法，验证每个相邻像素以查看它们是否没有背景颜色，然后在该位置调用自身，它们的位置记录在布尔矩阵中。递归方法：

 //pixelPosition > the position found of the current sprite, posX/posY > position of the current pixel being examined
public boolean[][] moveToNextPixel(boolean[][] pixelPosition, int posX, int posY)
{
    pixelPosition[posX][posY] = true;
    //If the next position isnt outside of the boundaries of the image AND if it hasnt already been recorded
    // AND if it isnt the color of the background, move to that position.
    if(posX + 1 < pixelPosition.length)
    {
        if(!pixelPosition[posX+1][posY] && !panBackgroundColor.isColorPresentInPalette(workingImage.getRGB(posX+1,posY)) )
        {
           moveToNextPixel(pixelPosition,posX+1,posY);
        }
    }
    if(posX - 1 >= 0)
    {
        if(!pixelPosition[posX-1][posY] &&  !panBackgroundColor.isColorPresentInPalette(workingImage.getRGB(posX-1,posY)))
        {
            moveToNextPixel(pixelPosition,posX-1,posY);
        }
    }
    if(posY + 1 < pixelPosition[0].length)
    {
        if(!pixelPosition[posX][posY+1] &&  !panBackgroundColor.isColorPresentInPalette(workingImage.getRGB(posX,posY+1)))
        {
            moveToNextPixel(pixelPosition,posX,posY+1);
        }
    }
    if(posY - 1 >= 0)
    {
        if(!pixelPosition[posX][posY-1] && !panBackgroundColor.isColorPresentInPalette(workingImage.getRGB(posX,posY-1)))
        {
            moveToNextPixel(pixelPosition,posX,posY-1);
        }
    }
    return pixelPosition;
}


//the method isColorPresentInPalette(int) check if the color in entry is in the background colors
public boolean isColorPresentInPalette( int colorRgb)
{
    boolean result = false;
    for( int i =0; i< backgroundPalette.length && !result;i++)
    {
        if(backgroundPalette[i] != null)
        {
            if(backgroundPalette[i].getRGB() == colorRgb)
            {
                result = true;    
            }
        }
    }
    return result;  
}

另外，如果我先加载一张带有正常大小精灵的表格，然后加载一张带有巨大精灵（4400+像素）的表格，它不会出现stackoverflow错误......所以，最后，我很困惑什么是正是问题。那么，递归方法真的是解决这类问题的正确方法吗？如果是这样，我该怎么做才能解决这个问题？否则，有人能找到一种方法来确定每个人的连续精灵及其位置吗？

标签： javarecursionstack-overflow

解决方案

编辑：最初我发布了一个递归解决方案，但没有意识到你正在这样做。我认为在仔细阅读之后，似乎递归可能不是最好的，因为在给定 4300 像素的情况下，您将添加如此多的调用。

在这种情况下，我只会在内存中进行 DFS。或者，您可以尝试 BFS（它将从中心向外搜索）。

内存中的 DFS 示例。这基本上与上面的递归执行相同的操作，除了不是将内容存储在缓冲区大小有限的调用堆栈上，而是存储内存：

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Stack;

public class FindNeedleInHaystack {

    String[][] haystack;

    class Coordinate {
        int x;
        int y;

        public Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Coordinate that = (Coordinate) o;
            return x == that.x &&
                    y == that.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    public FindNeedleInHaystack() {
        this.haystack = new String[10][10];
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                this.haystack[i][j] = "";
            }
        }
    }

    public void addNeedle(int a_x, int a_y) {
        this.haystack[a_y][a_x] = "needle";
    }

    public boolean hasNeedle() {
        boolean[][] visited = new boolean[10][10];
        return hasNeedleHelper(0, 0);

    }

    private List<Coordinate> neighbors(Coordinate coord, boolean[][] visited) {
        List<Coordinate> neighbors = new ArrayList<>();
        int x = coord.x;
        int y = coord.y;
        if (y + 1 < 10 && !visited[y+1][x]) neighbors.add(new Coordinate(x, y+1));
        if (y - 1 >= 0 && !visited[y-1][x]) neighbors.add(new Coordinate(x, y-1));
        if (x + 1 < 10 && !visited[y][x+1]) neighbors.add(new Coordinate(x + 1, y));
        if (x - 1 >= 0 && !visited[y][x-1]) neighbors.add(new Coordinate(x - 1, y));
        return neighbors;
    }

    private boolean hasNeedleHelper(int x, int y) {
        Stack<Coordinate> fringe = new Stack<>();
        boolean[][] visited = new boolean[10][10];

        fringe.push(new Coordinate(x, y));
        while(!fringe.isEmpty()) {
            Coordinate toVisit = fringe.pop();
            if (this.haystack[toVisit.y][toVisit.x].equals("needle")) {
                return true;
            } else {
                visited[toVisit.y][toVisit.x] = true;
                for(Coordinate coord : this.neighbors(toVisit, visited)) {
                    fringe.push(coord);
                }
            }
        }
        return false;
    }


    public static void main(String...args) {
        FindNeedleInHaystack hasNeedle = new FindNeedleInHaystack();
        hasNeedle.addNeedle(3, 4);
        System.out.println("Has a needle?: " + hasNeedle.hasNeedle());

        FindNeedleInHaystack doesntHaveNeedle = new FindNeedleInHaystack();
        System.out.println("Has a needle?: " + doesntHaveNeedle.hasNeedle());

    }
}

推荐阅读