无需排序即可找到线网格交点？

Question

我试图在不排序的情况下找到线网格交点。下图：

已知：

边界上的两个交点：(x0 y0)和(xN,yN) 是已知的。
每条网格线的位置已知。 [-R R] 是网格的跨度。
网格对称地以笛卡尔原点为中心。

我想要的：

我想根据每个点到起点 (x0,y0) 或终点 (xN,yN) 的距离，按升序或降序获取所有交点的数组.

例如：

(x0 y0), (x1,y1),(x2,y2)..., (xN,yN): 可接受

(xN yN), (xN-1,yN-1),(xN-2,yN-2)..., (x0,y0)：可以接受。

(x0 y0), (x3,y3),(x1,y1)..., (xN,yN): 不可接受。

我卡在什么地方：

我知道我至少可以用 for 循环计算每个交点，但我不知道如何在不排序的情况下按照上面提到的顺序保存交点（气泡示例）。比方说，我从 (x0,y0) 开始，那么要走哪条路才能找到我的第一个路口？特别是，我应该沿着 x 方向走，还是应该沿着 y 方向走，这样我才能到达第一个十字路口？下一步我的第二个怎么样？

我想有没有办法用 "natural" 几何方式来做？线的斜率（假设线不是垂直的）是已知的，meshgrid 是已知的，那么我们可以在这里玩什么技巧吗？非常感谢

另外：

如果我想并行处理所有交叉路口怎么办？比如说，在 CUDA 中。

Answer 1

假设单位瓦片大小，交点坐标分别在x = i和y = j处找到，用于增加索引。

使用参数线方程x = X + t U, y = Y + t V，交点出现在t = (i - X) / U和t = (j - Y) / V，为方便起见，我们将其重写为U V t = V (i - X)、U V t = U (j - Y)。

这两个序列是自然排序的，它们遵循两个公差V和U的等差数列以及初始索引i = Ceil(X)、j = Ceil(Y)。那么你需要做的就是将这两个序列合并。

# Initialize
i= Ceil(X), j= Ceil(Y)
Tx= V (i - X), Ty= U (j - Y)

# Loop until the final point
while i < XX and j < YY:
    # Move to the next intersection
    if Tx + V < Ty + U:
      Increment i, Tx+= V
    elif Tx + V > Ty + U:
      Increment j, Ty+= U
    else:
      Increment both i and j, Tx+= V, Ty+= U

交点的第二个坐标由T的相关值求得。

无需排序即可找到线网格交点？

Find line-meshgrid intersections without sorting?

c++

algorithm

sorting

graphics

geometry