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);
    }
}

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 类）

老师确实告诉我们这很消耗内存，但它应该是一个有效的算法，所以显然我做错了一些事情。任何帮助将非常感激，谢谢。

Answer 1

您可以尝试增加堆栈大小：如何增加 Java 堆栈大小？< /a>

可能您的算法有错误，或者形状太大。如果您在一张方格纸上“画”出您的算法，会有什么帮助呢？这样你就可以检查你的算法。

Answer 2

我猜您正在回溯到以前访问过的像素。在您从颜色返回之前，您刚刚绘制的像素可能不会对机器人可见，因此它不会在之前的绘制中显示为红色。

您有 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));
    //...
}

现在，这仍然可能导致非常深入的搜索。您可以考虑使用非递归广度优先遍历。请参阅有关洪水填充的维基百科文章。

Answer 3

将其实现为递归算法的问题在于它（对于较大的图像）具有非常高的递归深度。

在 Java（以及大多数其他命令式编程语言）中，最大递归深度受到每个线程的堆栈空间量的限制，因为它必须为每个方法调用保留一个堆栈帧。

您可以先尝试较小的图像，然后尝试使用 -xss 参数增加堆栈大小。

---

编辑：正如 Mark 所指出的，在您的绘图完成之前，机器人不会获得任何像素，因为您的绘图通常是双缓冲的（即 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);
}