tl;dr 使用坐标点在数组中绘制平滑线条的非常快速的方法是什么？注意：阅读以下信息可能会提供一些急需的上下文。
我目前正在实施康威的生活游戏。我一次使用鼠标侦听器 [鼠标拖动，特别是] 到两个点，并将它们传递到此方法中：
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;
}
}
}
实现布雷森汉姆的直线算法 （http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm）。它非常简单，您可以直接使用数组索引作为坐标。