以角度遍历2D阵列

Question

通常我们按行或列遍历数组,但在这里我想以一个角度遍历它.我会试着解释一下我的意思,所以让我们说如果角度是45度而不是逐行,它会搜索为(0,0)然后(0,1)(1,0)然后(0,2) ,(1,1),(2,0)等...(抱歉无法上传图像,因为我是新用户而且不允许这样做,可能会尝试想象/绘制一个有助于获取的数组我想说的是)但是如果用户输入20度的角度会发生什么,我们如何确定如何搜索阵列.

我只是想知道是否有任何算法可以做类似的事情？编程语言不是问题我想这个问题更多的是algoritham排序.任何想法都会受到欢迎.如果我无法清楚地解释我在寻找什么,请随时询问.

多谢你们.

Answer 1

简单.采取一个角度(让我们说45).这对应v=(1, 1)于您的案例中的向量.(这可以归一化为单一向量(sqrt(2)/2, sqrt(2)/2),但这不是必需的)

对于数组中的每个点,您都有自己的坐标(x, y).只需使用向量执行这些坐标的标量积.我们打电话吧f(x, y) = scalarProduct((x, y), v)

对价值进行排序f(x, y),你就得到了你正在寻找的"遍历"!

一个真实的例子.你的矩阵是3x3标量产品是:

(0,0).(1,1)= 0

(0,1).(1,1)= 1

(0,2).(1,1)= 2

(1,0).(1,1)= 1

(1,1).(1,1)= 2

(1,2).(1,1)= 3

(2,0).(1,1)= 2

(2,1).(1,1)= 3

(2,2).(1,1)= 4

如果您按升序订购这些标量产品,您将获得订购(0,0),(1,0),(1,0),(2,0),(1,1),(0,2), (2,1)...

如果你想用角20做,代替出现的所有v=(1, 1)同v=(cos(20), sin(20))

这是几何解释的例证.标量积对应于矢量v(红色)与蓝线的交点.