java - 在康威的生命游戏中将平滑的线条绘制到网格[二维数组]

Question

tl;dr 使用坐标点在数组中绘制平滑线的快速方法是什么？注意:阅读以下信息可能会提供一些急需的背景信息。

我目前正在致力于康威生命游戏的实现。我一次使用鼠标监听器 [mouseDragged，特别是] 到两个点，并将它们传递到此方法中:

     public void findIndexSmoothed(int x, int y, int nx, int ny)
    {
        int size1 = size / 2 + 1; // radius
        size1 *= brush;
        int searchMargin = 10; // how many squares are checked within a certain              
        double slope;
        // ((x/size) -50 >0) ? ((x/size) -50) : 0
        // Optimizes performance at the expense of function
        // UPDATE: a simple if/else reduced function loss to nominal levels
        if (x + 2.5 < nx)
        {
            slope = (((double) ny - y) / (nx - x));
            for (int i = 0; i < sY; i++)
            {
    for (int j = ((x / size) - searchMargin > 0) ? ((x / size)     - searchMargin) : 0; j <  
sX; j++)                {
                    for (double c = x; c <= nx; c += 1)
                    {
                        if ((valCoord[i][j][0] >= c - size1 && valCoord[i][j][0] <= c + size1)
                                && (valCoord[i][j][1] >= ((slope * (c - x)) + y) - size1 && valCoord[i][j][1] <= ((slope * (c - x)) + y)
                                        + size1))
                        {
                            flagVals[i][j] = true;
                            actualVals[i][j] = true;
                            cachedVals[i][j] = true;
                            cachedVals[i + 1][j + 1] = true;
                            cachedVals[i + 1][j] = true;
                            cachedVals[i + 1][j - 1] = true;
                            cachedVals[i][j + 1] = true;
                            cachedVals[i][j - 1] = true;
                            cachedVals[i - 1][j + 1] = true;
                            cachedVals[i - 1][j - 1] = true;
                            cachedVals[i - 1][j + 1] = true;
                        }
                    }
                }
            }
        }
        else if (x - 2.5 > nx)
        {
            slope = (((double) ny - y) / (nx - x));
            int d = ((x / size) + searchMargin < sX) ? ((x / size) + searchMargin) : sX;
            for (int i = 0; i < sY; i++)
            {
                for (int j = 0; j < d; j++)
                {
                    for (double c = nx; c <= x; c += 1)
                    {
                        if ((valCoord[i][j][0] >= c - size1 && valCoord[i][j][0] <= c + size1)
                                && (valCoord[i][j][1] >= ((slope * (c - x)) + y) - size1 && valCoord[i][j][1] <= ((slope * (c - x)) + y)
                                        + size1))
                        {
                            flagVals[i][j] = true;
                            actualVals[i][j] = true;
                            cachedVals[i][j] = true;
                            cachedVals[i + 1][j + 1] = true;
                            cachedVals[i + 1][j] = true;
                            cachedVals[i + 1][j - 1] = true;
                            cachedVals[i][j + 1] = true;
                            cachedVals[i][j - 1] = true;
                            cachedVals[i - 1][j + 1] = true;
                            cachedVals[i - 1][j - 1] = true;
                            cachedVals[i - 1][j + 1] = true;
                        }
                    }
                }
            }
        }
        else
        {
            if (ny > y)
            {
                for (int i = 0; i < sY; i++)
                {
                    for (int j = ((x / size) - searchMargin > 0) ? ((x / size) - searchMargin) : 0; j < sX; j++)
                    {
                        for (double c = y; c <= ny; c++)
                        {
                            if ((valCoord[i][j][0] >= x - size1 && valCoord[i][j][0] <= x + size1)
                                    && (valCoord[i][j][1] >= c - size1 && valCoord[i][j][1] <= c + size1))
                            {
                                flagVals[i][j] = true;
                                actualVals[i][j] = true;
                                cachedVals[i][j] = true;
                                cachedVals[i + 1][j + 1] = true;
                                cachedVals[i + 1][j] = true;
                                cachedVals[i + 1][j - 1] = true;
                                cachedVals[i][j + 1] = true;
                                cachedVals[i][j - 1] = true;
                                cachedVals[i - 1][j + 1] = true;
                                cachedVals[i - 1][j - 1] = true;
                                cachedVals[i - 1][j + 1] = true;
                            }
                        }
                    }
                }
            }
            else
            {
                for (int i = 0; i < sY; i++)
                {
                    for (int j = ((x / size) - searchMargin > 0) ? ((x / size) - searchMargin) : 0; j < sX; j++)
                    {
                        for (double c = ny; c <= y; c++)
                        {
                            if ((valCoord[i][j][0] >= x - size1 && valCoord[i][j][0] <= x + size1)
                                    && (valCoord[i][j][1] >= c - size1 && valCoord[i][j][1] <= c + size1))
                            {
                                flagVals[i][j] = true;
                                actualVals[i][j] = true;
                                cachedVals[i][j] = true;
                                cachedVals[i + 1][j + 1] = true;
                                cachedVals[i + 1][j] = true;
                                cachedVals[i + 1][j - 1] = true;
                                cachedVals[i][j + 1] = true;
                                cachedVals[i][j - 1] = true;
                                cachedVals[i - 1][j + 1] = true;
                                cachedVals[i - 1][j - 1] = true;
                                cachedVals[i - 1][j + 1] = true;
                            }
                        }
                    }
                }
            }
        }
    } 

好吧，如果你的眼睛还没有流血，请允许我解释一下这个庞然大物到底做了什么。首先，它计算鼠标拖动的方向。假设一切进展顺利。然后计算两点形成的直线的斜率，并遍历这三个嵌套的 for 循环。

            for (int i = 0; i < sY; i++)
            {
    for (int j = ((x / size) - searchMargin > 0) ? ((x / size)     - searchMargin) : 0; j <  
sX; j++)                {
                    for (double c = x; c <= nx; c += 1)
                    {
                        if ((valCoord[i][j][0] >= c - size1 && valCoord[i][j][0] <= c + size1)
                                && (valCoord[i][j][1] >= ((slope * (c - x)) + y) - size1 && valCoord[i][j][1] <= ((slope * (c - x)) + y)
                                        + size1))
                        {
                            flagVals[i][j] = true;
                            actualVals[i][j] = true;
                            cachedVals[i][j] = true;
                            cachedVals[i + 1][j + 1] = true;
                            cachedVals[i + 1][j] = true;
                            cachedVals[i + 1][j - 1] = true;
                            cachedVals[i][j + 1] = true;
                            cachedVals[i][j - 1] = true;
                            cachedVals[i - 1][j + 1] = true;
                            cachedVals[i - 1][j - 1] = true;
                            cachedVals[i - 1][j + 1] = true;
                        }
                    }
                }

它完全循环遍历数组的垂直部分，并水平遍历数组的一部分。最后一个 for 循环遍历两点之间的每个 X 坐标。 if 语句将该 X 值插入到直线方程中，找到相应的 Y 值，并检查坐标点数组是否匹配。如果找到一个，它就会在该位置将用于处理的数组[及其对应项]设置为 true。 (您可以忽略cachedVals，这是网格优化的一部分，与问题并不真正相关)

在相当小的网格(例如 100x100)上，这效果非常好，几乎为 0 延迟。然而，我使用的是更大的网格 [大约 3000x2500]，它可以包含多达 700 万个位置。关于如何优化[或完全改变]这段代码有什么想法吗？

编辑:所以我不久前就开始工作了，但我忘了将其发布在这里。如果其他人也有类似的问题，这是我的实现:

public void findIndexSmoothedII(int x, int y, int nx, int ny) // A custom implementation of Bresenham's Line
                                                                // Algorithm
{
    // preliminary brush size and super-sampling calculations
    int use = (size / 2 + 1) * brush / size;
    int shift = superSampled ? 1 : 0;
    // Determine distance between points in the X and Y axes, regardless of direction
    int dx = Math.abs(nx - x), dy = Math.abs(ny - y);
    // Determine what type of movement to take along line, based on direction
    int sx = x < nx ? 1 : -1, sy = y < ny ? 1 : -1;
    // threshold of offset before incrementing
    int err = (dx > dy ? dx : -dy) / 2;
    // The (sX,sY) values converted from the raw coordinates
    int xS, yS;
    while (true)
    {
        // if Both x and y have been incremented to the location of the second point, line is drawn and the algorithim
        // can end
        if (x == nx && y == ny)
            break;
        // Determine where cursor is in terms of (sY,sX) and handle border cases for X-Axis
        if ((x / size) - use > 0 && (x / size) + use < sX)
            xS = x / size;
        else if ((x / size) - use > 0 && (x / size) + use >= sX)
            xS = 5000;
        else
            xS = -5000;
        // Determine where cursor is in terms of (sY,sX) and handle border cases for Y-Axis
        if ((y / size) - use > 0 && (y / size) + use < sY)
            yS = y / size;
        else if ((y / size) - use > 0 && (y / size) + use >= sY)
            yS = 5000;
        else
            yS = -5000;
        // Below loops are responsible for array access and accounting for brush size
        for (int j = yS - (use << shift); j < yS + (use << shift); j++)
        {
            for (int i = xS - (use << shift); i < xS + (use << shift); i++)
            {
                if (i < sX - 3 && i > 2 && j > 2 && j < sY - 3)
                {
                    flagVals[j][i] = true;
                    actualVals[j][i] = true;
                    cachedVals[j][i] = true;
                    cachedVals[j + 1][i + 1] = true;
                    cachedVals[j + 1][i] = true;
                    cachedVals[j + 1][i - 1] = true;
                    cachedVals[j][i + 1] = true;
                    cachedVals[j][i - 1] = true;
                    cachedVals[j - 1][i + 1] = true;
                    cachedVals[j - 1][i - 1] = true;
                    cachedVals[j - 1][i + 1] = true;
                }
            }
        }
        // determine where to point to next
        int e2 = err;
        if (e2 > -dx)
        {
            err -= dy;
            x += sx;
        }
        if (e2 < dy)
        {
            err += dx;
            y += sy;
        }
    }
}

Answer 1

实现 Bresenham 直线算法 ( http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm )。非常简单，您可以直接使用数组索引作为坐标。