如何找到一条线上的所有网格？ [英] How to find all grid squares on a line?

问题描述

我试图在二维网格上实现视线算法。我知道它是如何在概念上工作的，但我想不出如何将它作为一种算法来实现。

基本思想非常简单。伪代码：

 函数LineOfSight（point1，point2）：布尔
 squares = GetListOfSquaresOnLine（point1，point2）
为每个广场的平方
如果square.IsOpaque然后返回false 
返回true 
  

（从概念上）将从点1的网格正方形的中心到点2的网格正方形的中心绘制一条直线，然后返回一个包含所有点的全部列表这条线穿过的正方形。但这是我不知道如何实现的部分。有人知道怎么做吗？ Delphi或C的例子是首选，但不是必需的。

解决方案

这两个答案到目前为止都指向维基百科的文章。

还有其他一些方法，在 this question 。

更新： < a href =http://playtechs.blogspot.ca/2007/03/raytracing-on-grid.html =noreferrer>这是另一个参考资料

I'm trying to implement a line-of-sight algorithm on a 2-dimensional grid. I know how it needs to work conceptually, but I can't think of how to implement it as an algorithm.

The basic idea is pretty simple. In pseudocode:

function LineOfSight(point1, point2): boolean
  squares = GetListOfSquaresOnLine(point1, point2)
  for each square in squares
    if square.IsOpaque then return false
  return true

GetListOfSquaresOnLine would (conceptually) draw a straight line from the center of the grid square at point1 to the center of the grid square at point2, and return a list of all squares that this line passes through. But that's the part I have no idea how to implement. Anyone know how to do this? Delphi or C examples preferred, but not required.

解决方案

Both of the answers so far point to a Wikipedia article on Bresenhams's algorithm. Here's the illustration the article gives, at full size. Notice that the line passes through grid squares that aren't highlighted, so Bresenham's algorithm only gives a subset of what you want.

Since you mention "line of sight", it sounds like you want an algorithm that enumerates all of the grid squares that the line goes through. This set is sometimes referred to as the super cover (of the line), and one algorithm is described here.

There are also some other approaches, given in the answers to this question.

Update: Here's another reference

这篇关于如何找到一条线上的所有网格？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！