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

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): Not Acceptable 。

我坚持的地方:

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

我想有没有办法以“自然”的几何方式来做？线的斜率(假设线不是垂直的)是已知的，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的相关值中找到的。