用网格去拟合一条线段
** 源代码: ** Draw-A-Line
前言
最开始是在(不记得那家公司)的笔试中,遇到了这个问题,说是给定一个线段的起点和终点,问这个线段经过了多少个网格?
如上图,这个线段经过了12个格子。
当时考场上自己想了个插值法,就是每隔固定的间距$\Delta$做一次判断,将该点所在的方格添加到线段经过的方格集合中。当然这个方法是一定有bug的啦,例如:
即便采样点多一些,依然会出现上图中间那种情况,同时无限制的增多采样点也会带来比较大的性能问题。
所以我们可以用类似bfs的思路去解决这个问题。不过这个其实不是今天的重点,今天的重点是拟合,也就是说我们不需要真的把线段穿过的网格都涂黑,我们是寻找一个比较优的思路去涂黑网格,来使得得到的图像与我们画的直线尽可能拟合。
插值法
插值法的思想很好理解,我们有起点(x1, y1)
和终点(x2, y2)
。那么我们就可以得到线段的长度length
了。随后假设我们要在线段上设置3个采样点,也就是起点,中点,终点啦,那么三个采样点的坐标都可以用着一个公式去计算:
$\begin{cases}x_i = x_1 + length \times \frac{i}{2} \\ y_i = y_1 + length \times \frac{i}{2} \end{cases} \ (i = 0, 1, 2)$
推广到n个采样点,公式如下:
$\begin{cases}x_i = x_1 + length \times \frac{i}{n - 1} \\ y_i = y_1 + length \times \frac{i}{n - 1} \end{cases} \ (i = 0, 1, 2 … n - 1)$
接下来就是插值法最重要的一个抉择了,到底选多少个采样点呢? 这里我们可以这样子思考,假设(x1 = 0, y1 = 0)
, (x2 = 5, y2 = 3)
。那么选择采样点数目2,3,4,5,8,10的效果如下图:
我们发现,在点数等于5的时候,我们得到了一个比较好的结果,即所有的格子都连起来了(上下左右或者对角线相邻)。小于5个点,得到的图像是中间有断点的,大于5个点,也没有明显更优(例如8个点时和5个点相同,10个点时倒是将线段经过的网格都显示出来了,但是计算量翻倍了呀)
最后其实得到的小结论就是用$Max(|x2 - x1|, |y2 - y1|)$作为采样点的个数最优,可以保证得到的结果是一个连续的图形,并且有着最少的计算次数。
证明的话,(说实话感觉画个图自己就明白了其实)
代码的话也比较简单:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
|
for (int i = 0; i < _pointCount; i++) { Vector2 pos = new Vector2(); pos.x = start.x + (_end.x - start.x) * i / (_pointCount - 1); pos.y = start.y + (_end.y - start.y) * i / (_pointCount - 1); var point = _pointList[i]; point.transform.position = pos; point.SetActive(true); }
|
扫描法(bfs)
扫描法,这个名字是我自己瞎起的,因为感觉像是从起点一点点扫到终点,核心思想是bfs。
首先将起点所在的格子添加到队列中(假设是格子(x,y)
),再假设线段终点在起点左上方时,则我们只需要去看一下格子(x + 1, y)
, (x + 1, y + 1)
, (x, y + 1)
是不是被该线段穿过,如果穿过了,则将其添加到队列中。这样不断地从队列中拿出格子来,对其右上三个格子做判断,并将符合条件的加入队列,直到走到了终点为止。这样我们就可以把线段穿过的所有格子都求到。
当然,起点和终点的位置关系不同时,要检查的格子是不同的,这里其实一共只有八种方向:
1 2 3 4 5 6 7 8 9
| x, y ( 1, 1) -> 左上 ( 1, 0) -> 左侧 ( 1, -1) -> 左下 ( 0, -1) -> 下侧 (-1, -1) -> 右下 (-1, 0) -> 右侧 (-1, 1) -> 右上 ( 0, 1) -> 上侧
|
对于方向(dirX, dirY)
,对于枚举出的格子(x, y)
需要去检查(x + dirX, y)
, (x + dirX, y + dirY)
, (x, y + dirY)
三个格子。
接下来就是处理,如何判断线段是否经过一个格子了,这里我采用的方法是,暴力(大雾)。即计算出直线一般表达式,带入格子四个顶点,如果值全大于等于0或者全小于等于0,说明不经过。如果有大于零有小于零,说明经过。
代码稍微长一点:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114
|
Vector2 dirVec = _curEnd - _curStart; if (dirVec.sqrMagnitude < 1) return;
Vector2Int dir = new Vector2Int(); dir.x = dirVec.x > 0 ? 1 : dirVec.x < 0 ? -1 : 0; dir.y = dirVec.y > 0 ? 1 : dirVec.y < 0 ? -1 : 0;
Queue<(int, int)> gridQ = new Queue<(int, int)>();
int startX = Mathf.FloorToInt(_curStart.x); int startY = Mathf.FloorToInt(_curStart.y); (int startGridX, int startGridY) = WorldPointToGrid(startX, startY); ColorAGrid(startGridX, startGridY); gridQ.Enqueue((startX, startY));
(int, int) endGrid = (Mathf.FloorToInt(_curEnd.x), Mathf.FloorToInt(_curEnd.y));
int layer = 0; while (true) { layer++; if (layer > 200) break;
(int x, int y) = gridQ.Dequeue();
if (x == endGrid.Item1 && y == endGrid.Item2) { (int gridX, int gridY) = WorldPointToGrid(x, y); ColorAGrid(gridX, gridY); break; }
int[,] worldPoints = new int[,] { {x + dir.x, y}, {x + dir.x, y + dir.y}, {x, y + dir.y} };
for (int i = 0; i < 3; i++) { int worldPointX = worldPoints[i, 0], worldPointY = worldPoints[i, 1]; if (IsLineThroughGrid(worldPointX, worldPointY)) { (int gridX, int gridY) = WorldPointToGrid(worldPointX, worldPointY);
if (gridX < 0 || gridX >= Row || gridY < 0 || gridY >= Column) continue;
if (_grids[gridX, gridY].color != Color.gray) { ColorAGrid(gridX, gridY); gridQ.Enqueue((worldPointX, worldPointY)); } } } }
private bool IsLineThroughGrid(int nextGridX, int nextGridY, bool careVertex = false) { float A = _curEnd.y - _curStart.y; float B = _curStart.x - _curEnd.x; float C = _curEnd.x * _curStart.y - _curStart.x * _curEnd.y;
int[,] vertexes = new int[,] { {nextGridX, nextGridY}, {nextGridX + 1, nextGridY}, {nextGridX, nextGridY + 1}, {nextGridX + 1, nextGridY + 1} };
float[] values = new float[4]; for (int i = 0; i < 4; i++) { values[i] = A * vertexes[i, 0] + B * vertexes[i, 1] + C; }
bool through; if (careVertex) { through = !((values[0] > 0 && values[1] > 0 && values[2] > 0 && values[3] > 0) || (values[0] < 0 && values[1] < 0 && values[2] < 0 && values[3] < 0)); } else { through = !((values[0] >= 0 && values[1] >= 0 && values[2] >= 0 && values[3] >= 0) || (values[0] <= 0 && values[1] <= 0 && values[2] <= 0 && values[3] <= 0)); }
return through; }
|
Extremely Fast Line Algorithm(EFLA)
困了,抽空补上,,
参考的Po-Han Lin的算法:
EFLA