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

问题描述

我正在尝试在二维网格上实现视线算法.我知道它在概念上需要如何工作，但我想不出如何将它作为一种算法来实现.

基本的想法很简单.在伪代码中:

function LineOfSight(point1, point2): boolean正方形 = GetListOfSquaresOnLine(point1, point2)对于正方形中的每个正方形如果 square.IsOpaque 则返回 false返回真

GetListOfSquaresOnLine 将(概念上)从 point1 的网格正方形的中心到 point2 的网格正方形的中心绘制一条直线，并返回这条线通过的所有正方形的列表.但那是我不知道如何实现的部分.有人知道怎么做吗?首选 Delphi 或 C 示例，但不是必需的.

解决方案

到目前为止，两个答案都指向维基百科关于 .

还有一些其他方法，在 这个问题.

更新: 这是另一个参考一个>

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屋！