通过2D阵列检查一条线

我有一个2D boolean阵列（一个boolean[][]），我有两个点（(x, y)）。我想在这两点之间划一条线，看看这条线是否与具有true值的空间相交。通过2D阵列检查一条线

为了清楚起见，设想每个元素是1 unit x 1 unit。 boolean[][]将始终是矩形。我从指定点的中心进行光线投射。

我真的不知道从哪里开始，一些建议，将不胜感激。

2016-04-24 HyperNeutrino

要清楚，你正在绘制的线与1位网格在同一个坐标空间内，对吗？所以它只是找到表示线条的单元格的功能。 –

@BerinLoritsch是的。我有一种感觉，这很简单，但我想不出如何去做。 – HyperNeutrino

如果我理解正确你的问题，这听起来像你只是想计算其二进制点网格是由线的影响。最长的时间，计算机已使用Bresenham's line algorithm。它在以后几年被改编使用抗锯齿。既然你正在处理简单的开/关位，你可以使用简单的算法。该链接有更多的理论，以及该算法对其他线路问题的一些修改。

的伪代码看起来像这样的事情：

deltaX = p1.X - p0.X 
deltaY = p1.Y - p0.Y 
error = -1.0 

# NOTE: assuming deltaX is not 0 (vertical) 
slope = Abs(deltaY/deltaX) 
y = p0.Y 

for(x = p0.X; x < p1.X; x++) 
{ 
    check(x,y) # plot/check, this is the point of interest 

    error += slope 
    if(error >= 0.0) 
    { 
     y += 1 
     error -= 1 
    } 
}

一对夫妇的注意事项：

的一切，是不是一个坐标需要是浮点数（包括DELTAX和移动deltaY）
p0和p1是点（x，y）并且可以是整数

来源

2016-04-24 01:54:28

所以我只想澄清，'检查（X，Y）'是我做的每一点的东西就行了，对吗？ – HyperNeutrino

我猜是这样，因为这个解决方案有效。谢谢！ – HyperNeutrino

@AlexL。对不起，我周末很忙（我是一个新的爷爷）。是。从原始算法中，函数的名称是“plot（x，y）”。并没有问题。 –

通过2D阵列检查一条线

回答

相关问题