math - 计算交叉点的长度(通过二维网格)

Question

我有一条线，我必须对该线经过的每个网格方 block 进行计算。

我已经使用 Superline 算法得到所有这些网格方 block 。这为我提供了一个要检查的 X、Y 坐标数组。

现在，这就是我卡住的地方，我需要能够计算通过每个网格方 block 的距离...例如，在一条既不是 90 度角也不是 45 度角的线上，每个网格方 block 适应总行的不同“长度”。

Image example here, need 10 reputation to post images

如您所见，一些方 block 中的“线长”比其他方 block 多得多 - 这就是我需要找到的。

我如何为每个网格正方形计算出这个值？我已经有一段时间了，请求 Stack Overflowers 的帮助!

Answer 1

可能有一些聪明的方法可以更快更容易地做到这一点，但你总是可以像这样破解它:

你知道距离公式:s=sqrt((x2-x1)^2+(y2-y1)^2)。要应用这一点，您必须找到该线与每个网格单元的边缘相交的点的 x 和 y 坐标。为此，您可以将单元格边界的 x 和 y 坐标代入直线方程，并根据需要求解 x 或 y。

也就是说，每个单元格从某个点 (x0,y0) 延伸到 (x0+1,y0+1)。所以我们需要找到 y(x0)、y(x0+1)、x(y0) 和 x(y0+1)。对于其中的每一个，找到的 x 或 y 值可能在也可能不在该单元格的坐标范围内。具体来说，其中两个会，两个不会。两个对应的是直线穿过的边，两个不对应的是没有穿过的边。

好吧，也许这听起来很令人困惑，所以让我们通过一个例子来研究。

假设您的直线具有等式 x=2/3 * y。您想知道它与从 (1,0) 延伸到 (2,1) 的单元格边缘相交的位置。

代入 x=1 得到 y=2/3。 2/3 在 y 的合法范围内——0 到 1——所以 (1,2/3) 是直线与该单元格相交的边缘上的一个点。即，左边缘。

代入 x=2 得到 y=4/3。 4/3 在 y 的范围之外。所以这条线没有穿过右边缘。

代入 y=0，你得到 x=0。 0 不在 x 的范围内，因此该线不通过底部边缘。

代入 y=1，你得到 x=3/2。 3/2 在 x 的合法范围内，因此 (3/2,1) 是另一个交点，在上边缘。

因此，直线与单元格边缘相交的两个点是 (1,2/3) 和 (3/2,1)。将这些代入距离公式，您将得到通过该单元格的线段的长度，即 sqrt((1-3/2)^2+(2/3-1)^2)=sqrt(1/4 +1/9)=平方(13/36)。您可以将其近似到任何所需的精度水平。

要在程序中执行此操作，您需要类似以下内容:(我将使用伪代码，因为我不知道您使用的是什么语言)

// Assuming y=mx+b

function y(x)
  return mx+b

function x(y)
  return (y-b)/m

// cellx, celly are co-ordinates of lower left corner of cell
// Upper right must therefore be cellx+1, celly+1
function segLength(cellx, celly)
  // We'll create two arrays pointx and pointy to hold co-ordinates of intersect points
  // n is index into these arrays
  // In an object-oriented language, we'd create an array of point objects, but whatever
  n=0
  y1=y(cellx)
  if y1>=celly and y1<=celly+1
    pointx[n]=cellx
    pointy[n]=y1
    n=n+1
  y2=y(cellx+1)
  if y2>=celly and y2<=celly+1
    pointx[n]=cellx+1
    pointy[n]=y2
    n=n+1
  x1=x(celly)
  if x1>=cellx and x1<=cellx+1
    pointx[n]=x1
    pointy[n]=celly
    n=n+1
  x2=x(celly+1)
  if x2>=cellx and x2<=cellx+1
    pointx[n]=x2
    pointy[n]=celly+1
    n=n+1
  if n==0
    return "Error: line does not intersect this cell"
  else if n==2
    return sqrt((pointx[0]-pointx[1])^2+(pointy[0]-pointy[1])^2)
  else
    return "Error: Impossible condition"

好吧，我相信您可以使代码更简洁一些，但就是这样。