0

我需要一种有效的方法来获取由两条线定义的区域中的所有整数点。

我从由两点 Pt1 和 Pt2 定义的线开始。然后移动这条线，得到两个新点 Pt1new 和 Pt2new。然后，我需要找到由线条移动产生的区域中的所有欧拉点。

对于简单的情况，这没有问题，因为我只会在最小 x 和 y 值与最大 x 和 y 值之间生成一个矩形区域。然后检查与欧拉网格建立的交点是否实际上在我的点生成的区域内。（通过顺时针方向的点并检查点是否始终在右侧）

但是对于第二个问题（图像中较低的问题），这似乎不起作用，因为我无法轻松检查该点是否实际上在该区域内。我怎样才能以一种快速简单的方式找到所有这些点。

在图形中，我有兴趣找到绿点。它位于欧拉网格上（例如 x 和 y 坐标是整数值）。

问题图片

4

2 回答 2

3

如果两条线 Pt1-Pt2 和 Pt1new-Pt2new 相交于点 P0，则求三角形 Pt1-Pt1new-P0 和 Pt2-Pt2new-P0 中的所有欧拉点。

最简单的方法与您用于四边形的方法相同。计算边界框并测试里面的每个欧拉点。您可能需要使用重心坐标来检查这一点。

作为进一步的概括，您可能希望始终使用三角形：正常的 Pt1-Pt2-Pt1new + Pt2-Pt2new-Pt1new 和退化的 Pt1-Pt1new-P0 + Pt2-Pt2new-P0。

于 2012-11-19T13:37:17.370 回答
1

我认为您需要更改您的参考。

想象一下，您的原点锚定在您的线上，而实际上是网格在移动。您可以清楚地看到，首先突出显示的网格点已向上移动到线上。在第二种情况下，网格旋转了，只有突出显示的点移到了线上。

由于一切都是线性的（这里没有曲线），如果一个点在转换之前“低于”这条线，然后在它之下，那么它从未穿过它。

定义，然后衡量一个点是低于还是高于该线。如果您的线的最远任一端移动了 3 个单位，那么我们只需要考虑距离线最多 3 个单位的网格点。对于这些点中的每一个，测试它在转换前后是低于还是高于该线。如果它的状态改变了，那么这条线就通过了。如果没有，那么它没有。

那么，上面/下面的措施。该线由以下定义

y = mx + c。

如果点 p (px,py) 位于直线上方

py > m.py + c。

在矩阵中，我们可以首先将线 AB (ax,ay 到 bx,by) 和点 (px,py) 都转换为将 A 置于原点：

Q' = Q + | -ax |
         | -ay |

然后我们可以旋转它以使轴与线对齐。由于线与 x 轴之间的角度由 sin(θ) = (dy / d) 和 cos(θ) = (dx / d) 给出：

d = sqrt((by-ay)^2 + (bx-ax)^2)
s = (by-ay)/d
c = (bx-ax)/d

角度的旋转矩阵在这个维基百科页面中给出，使用 s 和 c 我们得到：

R = |  c  s |
    | -s  c |

对线应用平移然后旋转，使谎言沿 x 轴，从原点到 x=d。然后该点将具有正或负 y 值。因此将其应用于点 p：

q = R(p+T) = |  c  s | ( |px| + |-ax|  
             | -s  c |   |py|   |-ay|  )

p'x = px - ax
p'y = py - ay
qx =  c * p'x + s * p'y
qy = -s * p'x + c * p'y

假设我们在点 P 上针对两条不同的线 AB 和 CD 执行此操作。我们将得到两个点 F 和 G（之前和之后的变换点）。如果：

if( signof(fy) != signof(gy) ) {
    // crossed the origin
}

但请注意，这仅测试 y。如果线太短而无法到达该点，则该点可能只是通过该线。因此，测试 x 值是否也发生了变化：

if( (fx < 0) && (gx < 0) ||
    (fx > d) && (gx > d) ) {
    // whooshed past
}

因此，如果您同时测试这两个，您就会知道该点是否越过界限而没有飞过。

希望这很清楚...

于 2012-11-19T13:37:36.723 回答