1

我有一条线，由参数定义m, h，其中

y = m*x + h

这条线穿过一个网格（即像素）。对于网格的每个正方形(a, b)（即 square [a, a+1] x [b, b+1]），我想确定给定的线是否穿过这个正方形，如果是，那么正方形中线段的长度是多少。

最终，我希望能够同时使用多行（即m和h是向量，matlab 样式），但我们现在可以专注于“简单”的情况。

我想出了如何确定线是否穿过正方形：

  1. 计算直线与垂直线x = a和x = a + 1以及水平线 和 的y = b交点y = b + 1
  2. 检查这 4 个点中的 2 个是否在正方形边界上（即a <= x < a + 1和b <= y < b + 1）

如果这些点上的两个在正方形上，则线穿过它。然后，要计算长度，只需减去两个点，并使用勾股定理。

我的问题更多在实施方面：我怎样才能很好地实施（尤其是在选择要减去的 2 个点时）？

4

3 回答 3

2

让正方形由角点(a,b), (a+1,b), (a,b+1), (a+1,b+1)定义。

第1步：检查线是否与正方形相交...

(a) 将 4 个角点的坐标分别代入y - mx - h。如果此评估的符号包括正项和负项，则转到步骤 b。否则，线不与正方形相交。

(b) 现在有两个子情况：

(b1)案例 1：在步骤 (a) 中，您有三个点，其中y - mx - h评估为一个符号，第四个点评估为另一个符号。让这第四点是一些(x*,y*)。那么交点是(x*,mx*+h)和((y*-h)/m,y*)。

(b2) 情况 2：在步骤 (a) 中，您有两个点y - mx - h评估为一个符号，另外两个点评估为另一个符号。选择评估为相同符号的任意两个点，例如(x*,y*)和(x*+1, y*)。那么交点是(x*, mx* + h)和(x*+1,m(x*+1) + h)。

您将不得不考虑一些退化的情况，其中线恰好接触四个角点之一，以及线恰好位于正方形的一侧的情况。

于 2010-12-07T18:10:28.593 回答
0

m当为 0 时（尝试计算与 的交集时） ，您提出的方法可能会在步骤 (1) 中遇到问题y = k。

如果m为0，则很容易（线段长度为1或0，取决于是否b <= h <= b+1）。

否则，您可以通过替换找到与 和 的交集，x = a例如a+1。然后，将 and 夹在and之间（例如，and ，即与 类似），并使用比例。y_ay_{a+1}y_ay_{a+1}bb+1y1y2y1 = min(b+1, max(b, y_a))y2abs((y1-y2)/m) * sqrt(m^2+1)

这利用了 和 之间的线段 ， 和 之间x=k的x=k+1差异，sqrt(m^2+1)和相似性这一事实。ym

于 2010-12-07T18:14:31.683 回答
0

你可以这样做：首先找到正方形的中心，然后找到对角线的长度。如果正方形中心到直线的距离小于对角线的长度，那么直线将与正方形相交。一旦你知道这条线会相交，你就可以很容易地找到相交的线段。我认为您正在尝试为代数重建技术制作权重矩阵。我希望这是正确的答案。这是我在堆栈流中的第一个答案。:)

于 2014-09-26T05:26:29.527 回答